Giáo trình đồ thị và các thuật toán

Dưới đây là tóm tắt các phần chính của giáo trình:

• Chương 0: Mở đầu: Giới thiệu về đồ thị, lịch sử hình thành (với Leonhard Euler và bài toán cầu Königsberg), tầm quan trọng và ứng dụng của lý thuyết đồ thị trong tin học và các lĩnh vực khác. Nhấn mạnh việc tiếp cận giáo trình từ góc độ cài đặt thuật toán trên máy tính.
• Chương 1: Các khái niệm cơ bản: Định nghĩa đồ thị (Graph) là cấu trúc rời rạc gồm các đỉnh (Vertices) và cạnh (Edges). Phân loại đồ thị thành đơn đồ thị, đa đồ thị, đồ thị vô hướng và đồ thị có hướng. Giới thiệu các khái niệm về cạnh liên thuộc, đỉnh kề, bậc của đỉnh (đối với đồ thị vô hướng) và bán bậc vào/ra (đối với đồ thị có hướng), cùng các định lý liên quan.
• Chương 2: Biểu diễn đồ thị trên máy tính: Trình bày ba phương pháp chính để biểu diễn đồ thị trong bộ nhớ máy tính:
  • Ma trận kề (Adjacency Matrix): Đơn giản, trực quan nhưng tốn không gian (O(n²)) và thời gian duyệt các đỉnh kề.
  • Danh sách cạnh (Edge List): Tiết kiệm không gian cho đồ thị thưa (O(2m)) và dễ duyệt tất cả các cạnh, nhưng khó duyệt các đỉnh kề.
  • Danh sách kề (Adjacency List): Khắc phục nhược điểm của hai phương pháp trên, dễ dàng duyệt các đỉnh kề và các cạnh, là phương pháp hiệu quả nhất về lý thuyết. Có hai cách cài đặt phổ biến là Forward Star và danh sách móc nối.
• Chương 3: Các thuật toán tìm kiếm trên đồ thị: Giới thiệu về bài toán tìm đường đi trên đồ thị và các thuật toán duyệt đỉnh:
  • Tìm kiếm theo chiều sâu (Depth First Search – DFS): Trình bày cả cài đặt đệ quy và không đệ quy (sử dụng ngăn xếp – Stack), kèm theo ví dụ minh họa và giải thích vết đường đi (Trace).
  • Tìm kiếm theo chiều rộng (Breadth First Search – BFS): Trình bày cài đặt sử dụng hàng đợi (Queue) và phương pháp loang (Flooding Algorithm), kèm theo ví dụ minh họa. Nhấn mạnh rằng BFS tìm được đường đi ngắn nhất (ít cạnh nhất).
  • Độ phức tạp tính toán của BFS và DFS: Phân tích chi phí thời gian của BFS và DFS tùy thuộc vào cách biểu diễn đồ thị (danh sách kề là tốt nhất O(n+m), ma trận kề O(n²), danh sách cạnh là tồi nhất O(n.m)).
• Chương 4: Tính liên thông của đồ thị:
  • Định nghĩa: Giới thiệu khái niệm liên thông và thành phần liên thông (đối với đồ thị vô hướng), đỉnh cắt/khớp, cạnh cắt/cầu. Đối với đồ thị có hướng, phân biệt liên thông mạnh và liên thông yếu.
  • Tính liên thông trong đồ thị vô hướng: Trình bày thuật toán cơ bản để liệt kê các thành phần liên thông.
  • Đồ thị đầy đủ và thuật toán Warshall: Định nghĩa đồ thị đầy đủ. Giới thiệu khái niệm bao đóng đồ thị và thuật toán Warshall (Stephen Warshall, 1960) để tìm bao đóng, từ đó kiểm tra tính liên thông. Cài đặt thuật toán Warshall và đếm số thành phần liên thông. Độ phức tạp của Warshall là O(n³).
  • Các thành phần liên thông mạnh: Phân tích các dạng cung trong cây DFS (cung ngược, cung xuôi, cung chéo). Giới thiệu thuật toán Tarjan (R.E.Tarjan – 1972) để liệt kê các thành phần liên thông mạnh, dựa trên việc xác định “chốt” của mỗi thành phần và sử dụng các giá trị Numbering và Low. Thuật toán này có độ phức tạp O(n+m) với danh sách kề.
• Chương 5: Vài ứng dụng của các thuật toán tìm kiếm trên đồ thị:
  • Xây dựng cây khung của đồ thị: Định nghĩa cây, rừng và các định lý tương đương về cây.

Tóm lại, giáo trình cung cấp kiến thức nền tảng vững chắc về lý thuyết đồ thị, các phương pháp biểu diễn đồ thị trên máy tính, các thuật toán tìm kiếm cơ bản (DFS, BFS), các thuật toán liên quan đến tính liên thông (Warshall) và tìm thành phần liên thông mạnh (Tarjan), cùng với độ phức tạp tính toán của từng thuật toán. Giáo trình cũng đưa ra các ví dụ và bài tập thực hành.