Bài giảng Toán rời rạc 2A: Chương 2 - Lê Thị Tuyết Nhung

Trong lĩnh vực Toán rời rạc và Khoa học máy tính, đồ thị là một cấu trúc dữ liệu mạnh mẽ được sử dụng để mô hình hóa và giải quyết nhiều bài toán phức tạp. Để có thể lưu trữ, xử lý hiệu quả và triển khai các thuật toán trên máy tính, việc lựa chọn phương pháp biểu diễn đồ thị phù hợp đóng vai trò then chốt. Tài liệu này giới thiệu về tầm quan trọng của việc biểu diễn đồ thị và các phương pháp cơ bản, giúp người học nắm vững nền tảng để tối ưu hóa việc thiết kế và phân tích các thuật toán đồ thị.

Sinh viên ngành Toán học, Tin học, Công nghệ thông tin đang học các môn liên quan đến Toán rời rạc, Cấu trúc dữ liệu và Giải thuật đồ thị.

Tài liệu đi sâu vào các phương pháp cốt lõi để biểu diễn đồ thị, một chủ đề thiết yếu trong Toán rời rạc và các ứng dụng Tin học. Bắt đầu với sự cần thiết của việc chuyển đổi cấu trúc đồ thị thành các cấu trúc dữ liệu máy tính, tài liệu trình bày chi tiết hai phương pháp chính: ma trận kề và danh sách cạnh (hay cung). Đối với ma trận kề, nội dung làm rõ cách thức biểu diễn đồ thị vô hướng và có hướng, cùng với các tính chất quan trọng như mối quan hệ giữa tổng các phần tử và số cạnh/cung, cũng như cách xác định bậc/bán bậc của đỉnh. Nhiều ví dụ minh họa và bài tập được cung cấp để củng cố hiểu biết. Tiếp theo, phương pháp danh sách cạnh được giới thiệu, đặc biệt hữu ích cho các đồ thị thưa, giải thích cách lưu trữ các cặp đỉnh đầu-cuối và yêu cầu bộ nhớ. Mục tiêu là trang bị cho người học khả năng lựa chọn cấu trúc dữ liệu biểu diễn đồ thị tối ưu, từ đó phát triển các thuật toán đồ thị hiệu quả và ứng dụng chúng vào giải quyết các bài toán thực tế trong khoa học máy tính và kỹ thuật.