TỔNG QUAN HỌC THUẬT: GIÁO TRÌNH THỰC HÀNH LÝ THUYẾT ĐỒ THỊ (HUTECH)

Tổng quan về giáo trình

Giáo trình Thực hành Lý thuyết đồ thị (mã học phần: 1.CMP3014) là tài liệu học tập chính thức do Trường Đại học Công nghệ TP.HCM (HUTECH) phát hành, được biên soạn bởi ThS. Nguyễn Kim Hưng và TS. Huỳnh Quốc Bảo. Tài liệu tiếp nhận phản hồi học thuật thông qua hộp thư của ban biên tập tại địa chỉ tailieuhoctap@hutech.vn. Trong chương trình đào tạo kỹ sư và cử nhân thuộc khối ngành Công nghệ thông tin và Kỹ thuật phần mềm, học phần này giữ vai trò cầu nối chuyên môn giữa cơ sở toán học rời rạc và kỹ năng lập trình giải thuật trên các cấu trúc phi tuyến tính.

Mục tiêu học tập của tài liệu tập trung vào việc chuẩn hóa các chuẩn đầu ra (learning outcomes) cụ thể: người học phân biệt được đồ thị có hướng, vô hướng, các thành phần khuyên/vòng; nắm vững phương pháp biểu diễn đồ thị thông qua ma trận kề; cài đặt thuật giải đệ quy để xác định tính liên thông; triển khai các thuật toán kinh điển như Fleury, tìm chu trình/đường đi Euler, tìm kiếm theo chiều sâu (DFS), tìm kiếm theo chiều rộng (BFS), thuật toán Prim và Kruskal cho bài toán cây khung nhỏ nhất, cùng hai thuật toán tìm đường đi ngắn nhất Dijkstra và Floyd.

Cấu trúc giáo trình được thiết kế gồm 5 bài học thực hành tương ứng với tiến trình môn học. Phương pháp tiếp cận đi từ việc hình thức hóa các khái niệm toán học (bậc của đỉnh, tính liên thông, chu trình), chuyển đổi sang mô hình dữ liệu trong bộ nhớ (struct DOTHI), cho đến bước cài đặt thuật toán hoàn chỉnh bằng ngôn ngữ lập trình C/C++.

Điểm đặc thù của tài liệu là tính thực nghiệm trực tiếp: mỗi thuật toán đều gắn liền với việc tổ chức tệp tin dữ liệu đầu vào chuẩn (chẳng hạn tệp văn bản C:/test.txt), các hàm kiểm tra tính hợp lệ dữ liệu, và bảng phân tích dấu vết trạng thái (trace table) qua từng vòng lặp.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Tài liệu được phân chia thành 5 bài học với hệ thống kiến thức có tính kế thừa logic:

  • Bài 1: Đồ thị, liên thông và biểu diễn ma trận kề: Định nghĩa đỉnh, cạnh, cung vô hướng và có hướng. Hướng dẫn biểu diễn đồ thị bằng ma trận kề $A = (a_{ij})$ kích thước $n \times n$. Phân tích tính chất đối xứng $a[i][j] = a[j][i]$ của đồ thị vô hướng, tính chất đường chéo chính $a[i][i] = 0$ khi không có khuyên. Hướng dẫn lập trình đọc tệp dữ liệu thông qua cấu trúc struct GRAPH { int n; int a[MAX][MAX]; } DOTHI;, kiểm tra tính hợp lệ qua hàm KiemTraMaTranKeHopLe và KiemTraDoThiVoHuong. Cung cấp thuật giải duyệt thành phần liên thông bằng mảng nhãn Nhan[] và hàm đệ quy DiTimCacDinhLienThong.
  • Bài 2: Đường đi và chu trình Euler: Trình bày định nghĩa chu trình Euler và đường đi Euler bắt nguồn từ bài toán 7 chiếc cầu Königsberg của Leonhard Euler thế kỷ 18. Phân tích điều kiện cần và đủ dựa trên bậc của đỉnh (bậc chẵn đối với đồ thị vô hướng, cân bằng bậc trong/bậc ngoài đối với đồ thị có hướng). Phân tích hạn chế của thuật toán Fleury khi kiểm tra cạnh cầu, từ đó hướng dẫn cài đặt thuật toán Find_tour sử dụng cấu trúc struct STACK (vận hành theo cơ chế LIFO) kết hợp cạnh giả (dummy edge).
  • Bài 3: Tìm kiếm đường đi trên đồ thị theo chiều sâu và chiều rộng: Định nghĩa đường đi đơn và chu trình đơn độ dài $k$. Cài đặt thuật toán DFS dạng đệ quy và thuật toán BFS sử dụng cấu trúc hàng đợi QUEUE. Hệ thống thuật toán quản lý tiến trình duyệt thông qua hai mảng trạng thái ChuaXet[] và LuuVet[], cho phép tái hiện đường đi từ đỉnh nguồn $S$ tới đỉnh đích $F$.
  • Bài 4: Xác định cây khung nhỏ nhất: Định nghĩa cây khung và cây khung có tổng trọng số các cạnh nhỏ nhất. Phân tích nguyên lý và hướng dẫn thi hành thuật toán Prim (phát triển cây từ đỉnh) và thuật toán Kruskal (chọn cạnh trọng số nhỏ nhất không tạo chu trình), kèm bảng so sánh chi tiết giữa hai giải thuật.
  • Bài 5: Các thuật toán tìm đường đi ngắn nhất: Triển khai bài toán tìm tuyến đường tối ưu trong mạng lưới trọng số; cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh nguồn và thuật toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị.

Kiến thức nền tảng được xây dựng

Giáo trình thiết lập các khối kiến thức lý thuyết nền tảng:

  • Đại số tuyến tính ứng dụng trong cấu trúc dữ liệu: Mô hình hóa các quan hệ cạnh/cung thông qua ma trận vuông $A$. Bậc của đỉnh $i$ trong đồ thị vô hướng được xác định qua tổng các phần tử trên dòng hoặc cột của ma trận kề; đối với đồ thị có hướng, tổng phần tử trên dòng biểu thị bậc ngoài và trên cột biểu thị bậc trong.
  • Nguyên lý duyệt và lưu vết trạng thái: Cơ chế phân định trạng thái đỉnh bằng các mảng số nguyên một chiều (ChuaXet[i] = 0 hoặc 1, Nhan[i] lưu mã số thành phần liên thông, LuuVet[u] = v lưu đỉnh liền trước). Đây là nguyên lý cốt lõi của các bài toán liệt kê không lặp và không bỏ sót.
  • Lý thuyết cấu trúc dữ liệu trừu tượng: Cài đặt trực tiếp cấu trúc Ngăn xếp (STACK) và Hàng đợi (QUEUE) bằng mảng tĩnh, làm nền tảng cho việc điều khiển thứ tự duyệt theo chiều sâu (LIFO) và chiều rộng (FIFO).

Kỹ năng phát triển

Thông qua các bài học, người học phát triển các nhóm kỹ năng cụ thể:

  • Kỹ năng kỹ thuật lập trình: Định nghĩa và quản lý cấu trúc dữ liệu phức hợp (struct GRAPH, struct STACK); thao tác đọc/ghi tệp tin thông qua con trỏ FILE*, các hàm chuẩn fopen, fscanf, fclose; xử lý mảng hai chiều có kích thước cố định (#define MAX 10).
  • Kỹ năng phân tích thuật toán: Đọc và giải thích mã giả, chuyển đổi từ thuật toán hình thức sang mã nguồn C/C++; phân tích chi phí kiểm tra cạnh cầu trong thuật toán Fleury; lựa chọn giải thuật phù hợp cho từng dạng đồ thị.
  • Kỹ năng gỡ lỗi và kiểm chứng: Sử dụng phương pháp bảng lần vết (trace table) từng bước thực thi để kiểm soát giá trị của biến và mảng trạng thái tại mỗi chu kỳ lặp, đối chiếu kết quả truy vết đường đi thực tế trên đồ thị.

Phương pháp giảng dạy và học tập

Giáo trình áp dụng phương pháp sư phạm cấu trúc từng bước (step-by-step modular teaching), kết hợp chặt chẽ giữa mô hình toán học và mã nguồn thực thi:

[Khái niệm toán học / Bậc / Cạnh] 
[Mô hình hóa dữ liệu (struct DOTHI)] 
[Bảng lần vết thủ công (Trace table)] 
[Cài đặt hàm chức năng & kiểm thử]

Mỗi bài học được tổ chức thành một quy trình thực hành đồng nhất gồm 5 giai đoạn:

  1. Chuẩn bị dữ liệu: Thiết lập tệp văn bản lưu trữ thông số đồ thị trên đĩa cứng (dòng 1 chứa số đỉnh $n$, các dòng tiếp theo chứa ma trận kề $n \times n$).
  2. Khai báo cấu trúc: Định nghĩa kiểu dữ liệu đồ thị, ngăn xếp hoặc hàng đợi tương ứng.
  3. Cài đặt hàm kiểm tra điều kiện: Viết các hàm xác định tính hợp lệ của dữ liệu đầu vào (KiemTraMaTranKeHopLe, hàm đếm bacDinh).
  4. Xây dựng giải thuật lõi: Cài đặt các hàm duyệt, tìm kiếm hoặc tối ưu (DFS, BFS, TimDuongDi, DiTimCacDinhLienThong).
  5. Tích hợp hệ thống: Ghép nối các hàm trong hàm main(), hiển thị kết quả kiểm tra và đường đi ra màn hình console.

Tài liệu cung cấp các hình vẽ đồ thị mẫu cùng bảng trạng thái chi tiết qua từng bước lặp. Điển hình như tại Bài 1, tiến trình phân rã 3 thành phần liên thông của đồ thị 9 đỉnh (từ đỉnh 0 đến đỉnh 8) được mô tả qua bảng theo dõi mảng Nhan[i] và biến SoThanhPhanLT. Tương tự, tại Bài 2 và Bài 3, trạng thái ngăn xếp Find_tour và mảng LuuVet, ChuaXet được trình bày rõ ràng qua từng đỉnh viếng thăm.

Đánh giá học phần được thiết lập theo tỷ lệ cân bằng giữa quá trình và thực hành:

  • Điểm quá trình (50%): Đánh giá mức độ chuyên cần tham gia các buổi học trên lớp và tính tích cực trong giải quyết bài tập lý thuyết.
  • Điểm thực hành (50%): Điểm trung bình cộng thu được từ các buổi lập trình thực tế tại phòng máy.
  • Điểm tổng kết học phần: Tính theo công thức: $$\text{Điểm học phần} = \text{Điểm quá trình} \times 50% + \text{Điểm thực hành} \times 50%$$

Điểm nổi bật và cập nhật

Nội dung giáo trình thể hiện rõ tính chuẩn hóa trong đào tạo thực hành công nghệ thông tin thông qua các điểm kỹ thuật cụ thể:

  • Liên kết lịch sử toán học với bài toán kỹ thuật hiện đại: Giáo trình mở đầu bằng việc phân tích bài toán 7 chiếc cầu Königsberg do Leonhard Euler giải quyết vào thế kỷ 18, từ đó khái quát hóa thành các ứng dụng hiện đại: mô hình mạng máy tính (xác định hai nút mạng có đường truyền thông kết nối hay không thông qua tính liên thông) và mô hình mạng lưới giao thông (tìm tuyến đường có trọng số nhỏ nhất giữa hai thành phố).
  • Phân tách rõ ràng giữa giải thuật lý thuyết và giải thuật thực thi: Tài liệu chỉ rõ nhược điểm vận hành của thuật toán Fleury khi tìm chu trình Euler—do chi phí xác định cạnh cầu phức tạp—để từ đó dẫn dắt người học tiếp cận thuật toán Find_tour dùng cấu trúc STACK. Cơ chế xử lý đường đi Euler bằng cách bổ sung "cạnh giả" (dummy edge) nối hai đỉnh bậc lẻ giúp thống nhất mã nguồn cài đặt cho cả hai trường hợp.
  • Thiết kế mã nguồn theo chuẩn module hóa: Mã nguồn C/C++ trong tài liệu được phân tách thành các hàm độc lập có trách nhiệm duy nhất (SRP), ví dụ: DocMaTranKe, XuatMaTranKe, KiemTraMaTranKeHopLe, KiemTraDoThiVoHuong. Cấu trúc này giúp người học dễ dàng cô lập lỗi, kiểm thử từng chức năng và tái sử dụng mã nguồn cho các bài học kế tiếp.

Đối tượng sử dụng giáo trình

Giáo trình được biên soạn phục vụ các nhóm đối tượng cụ thể trong môi trường đào tạo đại học:

  • Sinh viên chuyên ngành: Sinh viên năm thứ hai hoặc năm thứ ba ngành Công nghệ thông tin, Kỹ thuật phần mềm, Hệ thống thông tin, Mạng máy tính và An toàn thông tin đang theo học học phần Thực hành Lý thuyết đồ thị.
  • Yêu cầu kiến thức tiên quyết (Prerequisites):
    • Nắm vững kiến thức môn Toán rời rạc (lý thuyết tập hợp, quan hệ, logic mệnh đề).
    • Hoàn thành học phần Kỹ thuật lập trình trên các ngôn ngữ C/C++, Java hoặc Python; đặc biệt thành thạo kỹ thuật xử lý mảng tĩnh, cấu trúc con trỏ tệp, cấu trúc bản ghi (struct) và cơ chế đệ quy.
  • Giảng viên hướng dẫn thực hành: Tài liệu đóng vai trò đề cương bài tập mẫu (lab manual), hỗ trợ giảng viên chuẩn hóa nội dung kiểm tra tại phòng thực hành và định hướng sinh viên tuân thủ các quy tắc viết mã nguồn giải thuật.
  • Tự học và tham khảo: Dành cho người học cần củng cố kỹ năng chuyển đổi mô hình toán học rời rạc thành mã chương trình có khả năng thực thi, phục vụ các học phần nâng cao như Cấu trúc dữ liệu và giải thuật, Phân tích thiết kế giải thuật hoặc Trí tuệ nhân tạo.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng người học nào?

Tài liệu được biên soạn phục vụ sinh viên bậc đại học thuộc khối ngành Công nghệ thông tin của Trường Đại học Công nghệ TP.HCM (HUTECH) và người học cần tài liệu hướng dẫn thực hành lập trình giải thuật đồ thị.

2. Cần chuẩn bị những kiến thức nền tảng nào trước khi học?

Người học bắt buộc phải có kiến thức về Toán rời rạc (khái niệm đồ thị, tập hợp, logic) và kỹ năng lập trình căn bản (ngôn ngữ C/C++, Java hoặc Python), trong đó việc nắm vững cấu trúc struct, mảng hai chiều, đệ quy và kỹ thuật đọc tệp tin là yếu tố then chốt.

3. Điểm khác biệt giữa tài liệu này và các sách lý thuyết đồ thị thông thường là gì?

Tài liệu tập trung hoàn toàn vào kỹ năng thực hành và triển khai mã nguồn thực tế. Thay vì chỉ dừng lại ở các định lý toán học, giáo trình hướng dẫn chi tiết cách tổ chức dữ liệu từ tệp test.txt, cài đặt mã nguồn C/C++, và cung cấp các bảng lần vết biến trạng thái từng bước để kiểm chứng kết quả chạy chương trình.

4. Phương pháp tự học giáo trình này như thế nào để đạt hiệu quả cao?

Người học cần tuân thủ tiến trình 5 bước được thiết lập trong giáo trình: tự chuẩn bị tệp tin ma trận kề, nhập mã nguồn các hàm kiểm tra và giải thuật, chạy từng bước tương ứng với bảng trace mẫu trong tài liệu, sau đó mở rộng thử nghiệm với các bộ dữ liệu đồ thị có kích thước và cấu trúc khác nhau.

5. Giáo trình có cung cấp các công cụ hoặc tài liệu hỗ trợ nào không?

Giáo trình đi kèm cấu trúc tệp tin mẫu định dạng .txt, mã nguồn C/C++ hoàn chỉnh cho từng bài học, thang điểm đánh giá chi tiết và kênh tiếp nhận phản hồi đóng góp học thuật thông qua ban biên tập tại email: tailieuhoctap@hutech.vn.

Kết luận

Giáo trình Thực hành Lý thuyết đồ thị của ThS. Nguyễn Kim Hưng và TS. Huỳnh Quốc Bảo (Trường Đại học Công nghệ TP.HCM) là tài liệu học tập có tính hệ thống cao, kết hợp chặt chẽ giữa nền tảng lý thuyết cấu trúc rời rạc và kỹ năng lập trình giải thuật. Cấu trúc nội dung 5 bài học cung cấp lộ trình thực nghiệm tuần tự từ khâu biểu diễn đồ thị, phân tích liên thông, duyệt đồ thị chuyên sâu cho đến các bài toán tối ưu hóa cây khung và tìm kiếm đường đi ngắn nhất. Đây là tài liệu quy chuẩn giúp sinh viên ngành Công nghệ thông tin hoàn thiện năng lực triển khai thuật toán trên máy tính.