VNU-HUS MAT3500: Toán rời rạc Lý thuyết đồ thị I Giới thiệu, Biểu diễn đồ thị và sự đẳng cấu, Tính liên thông Hoàng Anh Đức Bộ môn Tin học, Khoa Toán-Cơ-Tin học Đại học KHTN, ĐHQG Hà Nội hoanganhduc@hus.vn Nội dung Lý thuyết đồ thị I Giới thiệu Hoàng Anh Đức Một số ví dụ Giới thiệu Định nghĩa và khái niệm Một số ví dụ Đồ thị mới từ đồ thị cũ Định nghĩa và khái niệm Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt Một số đơn đồ thị đặc biệt Đồ thị hai phần Đồ thị hai phần Biểu diễn đồ thị và sự đẳng cấu Biểu diễn đồ thị và sự đẳng cấu Danh sách kề Danh sách kề Ma trận kề Ma trận liên thuộc Ma trận kề Sự đẳng cấu giữa các đồ thị Ma trận liên thuộc Tính liên thông trong đồ thị Sự đẳng cấu giữa các đồ thị Đường đi Liên thông trong đồ thị vô Tính liên thông trong đồ thị hướng Liên thông trong đồ thị có Đường đi hướng Đường đi và sự đẳng cấu Liên thông trong đồ thị vô hướng Đếm số đường đi giữa các đỉnh Liên thông trong đồ thị có hướng Đường đi và sự đẳng cấu Đếm số đường đi giữa các đỉnh 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Hoàng Anh Đức Giới thiệu 2 Một số ví dụ Một đồ thị (graph) G bao gồm một tập các đỉnh (vertex) Định nghĩa và khái niệm hoặc nút (node) V và một tập cách cạnh E nối các (cặp) Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt đỉnh với nhau Đồ thị hai phần Biểu diễn đồ thị và sự Có nhiều loại đồ thị khác nhau (vô hướng, có hướng, đồ thị đẳng cấu Danh sách kề đơn giản, đa đồ thị, v.), mỗi loại có cách định nghĩa cụ Ma trận kề thể khác nhau, tùy thuộc vào việc các loại cạnh nào cần Ma trận liên thuộc Sự đẳng cấu giữa các đồ được xét thị Tính liên thông trong Điều này dẫn tới việc tồn tại nhiều thuật ngữ khác nhau (và đồ thị Đường đi thường không thống nhất) Liên thông trong đồ thị vô hướng Trước khi đi vào định nghĩa đồ thị một cách cụ thể, chúng Liên thông trong đồ thị có hướng ta xét một số ví dụ Đường đi và sự đẳng cấu Đếm số đường đi giữa các đỉnh 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Ví dụ 1 (Đơn đồ thị vô hướng (simple undirected Hoàng Anh Đức graph)) Giới thiệu 3 Một số ví dụ V = {v1 , v2 , v3 , v4 } Định nghĩa và khái niệm Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt E = {v1 v2 , v1 v4 , v2 v3 , v2 v4 } Đồ thị hai phần Biểu diễn đồ thị và sự đẳng cấu Danh sách kề v1 v2 Ma trận kề Ma trận liên thuộc Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng Liên thông trong đồ thị có hướng v4 v3 Đường đi và sự đẳng cấu Đếm số đường đi giữa các đỉnh Hình: Chỉ có các cạnh vô hướng; có nhiều nhất một cạnh nối hai đỉnh phân biệt bất kỳ; và không có khuyên (loop)—cạnh nối giữa một đỉnh và chính nó 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Hoàng Anh Đức Ví dụ 2 (Đồ thị có hướng (và có khuyên) (directed Giới thiệu graph (with loops))) 4 Một số ví dụ Định nghĩa và khái niệm Đồ thị mới từ đồ thị cũ V = {v1 , v2 , v3 , v4 } Một số đơn đồ thị đặc biệt Đồ thị hai phần E = {(v1 , v2 ), (v2 , v2 ), (v2 , v3 ), (v2 , v4 ), (v4 , v1 ), (v4 , v2 )} Biểu diễn đồ thị và sự đẳng cấu Danh sách kề v1 v2 Ma trận kề Ma trận liên thuộc Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng v4 v3 Liên thông trong đồ thị có hướng Đường đi và sự đẳng cấu Hình: Chỉ có các cạnh có hướng; có nhiều nhất một cạnh có hướng Đếm số đường đi giữa các nối từ một đỉnh bất kỳ sang một đỉnh khác bất kỳ; và có khuyên đỉnh 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Hoàng Anh Đức Ví dụ 3 (Đơn đồ thị có hướng (simple directed graph)) 5 Giới thiệu Một số ví dụ Định nghĩa và khái niệm V = {v1 , v2 , v3 , v4 } Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt Đồ thị hai phần E = {(v1 , v2 ), (v2 , v3 ), (v2 , v4 ), (v4 , v1 ), (v4 , v2 )} Biểu diễn đồ thị và sự đẳng cấu Danh sách kề v1 v2 Ma trận kề Ma trận liên thuộc Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng Liên thông trong đồ thị có v4 v3 hướng Đường đi và sự đẳng cấu Đếm số đường đi giữa các đỉnh Hình: Chỉ có các cạnh có hướng; có nhiều nhất một cạnh có hướng nối từ một đỉnh bất kỳ sang một đỉnh khác bất kỳ; và không có khuyên 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Ví dụ 4 (Đa đồ thị vô hướng (undirected multigraph)) Hoàng Anh Đức Giới thiệu V = {v1 , v2 , v3 , v4 } 6 Một số ví dụ Định nghĩa và khái niệm E = {v1 v2 , v1 v4 , v2 v3 , v2 v4 } Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt m(v1 v2 ) = 2, m(v2 v3 ) = 3 Đồ thị hai phần Biểu diễn đồ thị và sự m(v1 v4 ) = m(v2 v4 ) = 1 đẳng cấu Danh sách kề Ma trận kề Ma trận liên thuộc v1 v2 Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng Liên thông trong đồ thị có hướng Đường đi và sự đẳng cấu Đếm số đường đi giữa các v4 v3 đỉnh Hình: Chỉ có các cạnh vô hướng; có thể có nhiều cạnh nối giữa hai đỉnh bất kỳ; và không có khuyên 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Ví dụ 5 (Đa đồ thị vô hướng có khuyên (undirected Hoàng Anh Đức pseudograph)) Giới thiệu 7 Một số ví dụ V = {v1 , v2 , v3 , v4 } Định nghĩa và khái niệm Đồ thị mới từ đồ thị cũ E = {v1 v2 , v1 v4 , v2 v3 , v2 v4 , v4 v4 } Một số đơn đồ thị đặc biệt Đồ thị hai phần m(v1 v2 ) = 2, m(v2 v3 ) = 3 Biểu diễn đồ thị và sự đẳng cấu m(v1 v4 ) = m(v2 v4 ) = m(v4 , v4 ) = 1 Danh sách kề Ma trận kề Ma trận liên thuộc v1 v2 Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng Liên thông trong đồ thị có hướng v4 v3 Đường đi và sự đẳng cấu Đếm số đường đi giữa các đỉnh Hình: Chỉ có các cạnh vô hướng; có thể có nhiều cạnh nối giữa hai đỉnh bất kỳ; và có khuyên (có thể có nhiều khuyên tại một đỉnh) 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Ví dụ 6 (Đa đồ thị có hướng (directed multigraph)) Hoàng Anh Đức Giới thiệu V = {v1 , v2 , v3 , v4 } 8 Một số ví dụ Định nghĩa và khái niệm E = {(v1 , v2 ), (v2 , v3 ), (v2 , v4 ), (v4 , v1 ), (v4 , v2 )} Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt m(v1 , v2 ) = m(v2 , v3 ) = m(v2 , v4 ) = m(v4 , v1 ) = 1 Đồ thị hai phần m(v4 , v2 ) = 2 Biểu diễn đồ thị và sự đẳng cấu Danh sách kề v1 v2 Ma trận kề Ma trận liên thuộc Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng v4 v3 Liên thông trong đồ thị có hướng Đường đi và sự đẳng cấu Hình: Chỉ có các cạnh có hướng; có thể có nhiều cạnh nối giữa hai Đếm số đường đi giữa các đỉnh đỉnh bất kỳ; và không có khuyên (khác với định nghĩa trong sách của Rosen) 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Hoàng Anh Đức Ví dụ 7 (Đa đồ thị có hướng và có khuyên (directed Giới thiệu pseudograph)) 9 Một số ví dụ Định nghĩa và khái niệm V = {v1 , v2 , v3 , v4 } Đồ thị mới từ đồ thị cũ Một số đơn đồ thị đặc biệt Đồ thị hai phần E = {(v1 , v2 ), (v2 , v2 ), (v2 , v3 ), (v2 , v4 ), (v4 , v1 ), (v4 , v2 )} Biểu diễn đồ thị và sự m(v1 , v2 ) = m(v2 , v2 ) = m(v2 , v3 ) = m(v2 , v4 ) = m(v4 , v1 ) = 1 đẳng cấu m(v4 , v2 ) = 2 Danh sách kề Ma trận kề v1 v2 Ma trận liên thuộc Sự đẳng cấu giữa các đồ thị Tính liên thông trong đồ thị Đường đi Liên thông trong đồ thị vô hướng Liên thông trong đồ thị có v4 v3 hướng Đường đi và sự đẳng cấu Đếm số đường đi giữa các Hình: Chỉ có các cạnh có hướng; có thể có nhiều cạnh nối giữa hai đỉnh đỉnh bất kỳ; và có khuyên (có thể có nhiều khuyên tại một đỉnh) 60 Giới thiệu Một số ví dụ Lý thuyết đồ thị I Hoàng Anh Đức Giới thiệu 10 Một số ví dụ Loại Cạnh Có cạnh song song? Có khuyên?
Tổng quan về giáo trình
Tài liệu bài giảng MAT3500: Toán rời rạc – Phần Lý thuyết đồ thị I (Giới thiệu, Biểu diễn đồ thị và sự đẳng cấu, Tính liên thông) do TS. Hoàng Anh Đức biên soạn, trực thuộc Bộ môn Tin học, Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội (hoanganhduc@hus.vn). Trong khung chương trình đào tạo cử nhân các ngành Toán học, Toán tin, Khoa học máy tính và Công nghệ thông tin, học phần MAT3500 giữ vị trí nền tảng thuộc khối kiến thức cơ sở ngành, cung cấp các công cụ toán học rời rạc phục vụ trực tiếp cho việc thiết kế thuật toán, cấu trúc dữ liệu và mô hình hóa mạng lưới.
Mục tiêu học tập của phần này tập trung vào việc trang bị cho người học:
- Khả năng nhận diện, phân loại và định nghĩa chính xác các mô hình đồ thị vô hướng và có hướng theo ngôn ngữ lý thuyết tập hợp và quan hệ nhị phân.
- Kỹ năng biểu diễn đồ thị thông qua các cấu trúc dữ liệu cơ bản (danh sách kề) và đại số tuyến tính (ma trận kề, ma trận liên thuộc).
- Phương pháp phân tích tính chất cấu trúc của đồ thị: bậc của đỉnh, tính chất hai phần, sự đẳng cấu, tính liên thông và sự tồn tại đường đi đơn.
- Kỹ thuật chứng minh các định lý tổ hợp then chốt như Bổ đề bắt tay (Handshaking Lemma) và Định lý Hall (Hall's Marriage Theorem).
Giáo trình tiếp cận kiến thức theo phương pháp tiên đề và diễn dịch toán học hình thức: xuất phát từ ví dụ trực quan để xây dựng định nghĩa tổng quát, chuẩn hóa các phép toán trên đồ thị, sau đó đi sâu vào phát biểu định lý kèm theo chứng minh chi tiết và bài tập kiểm chứng. Điểm đặc sắc của tài liệu là tính chuẩn xác cao về mặt thuật ngữ, phân định rạch ròi 8 biến thể đồ thị, đồng thời làm rõ sự khác biệt giữa các hệ quy ước học thuật phổ biến (như giáo trình của Kenneth H. Rosen) và chỉ dẫn cụ thể về độ phức tạp tính toán của các bài toán đồ thị.
Nội dung kiến thức cốt lõi
Các chương/chủ đề chính
Nội dung bài giảng Lý thuyết đồ thị I được triển khai qua 5 chủ đề logic tuần tự:
-
Giới thiệu và Phân loại đồ thị:
- Xây dựng định nghĩa hình thức: Đồ thị vô hướng $G = (V, E)$ với $E \subseteq [V]^2$; đồ thị có hướng $G = (V, E)$ với $E \subseteq V \times V$ (quan hệ nhị phân).
- Bảng phân loại chuẩn hóa 8 mô hình đồ thị dựa trên tính chất cạnh (có hướng/vô hướng), sự tồn tại của cạnh song song và khuyên (loops):
- Đơn đồ thị vô hướng (Simple undirected graph)
- Đa đồ thị vô hướng (Undirected multigraph)
- Đa đồ thị vô hướng có khuyên (Undirected pseudograph)
- Đồ thị có hướng có khuyên (Directed graph with loops)
- Đơn đồ thị có hướng (Simple directed graph)
- Đa đồ thị có hướng (Directed multigraph)
- Đa đồ thị có hướng và có khuyên (Directed pseudograph)
- Đồ thị hỗn hợp (Mixed graph)
- Các đại lượng đỉnh: Tập láng giềng $N(v)$ và $N(A) = \bigcup_{v \in A} N(v)$; Bậc $\deg(v)$ (khuyên đóng góp 2 vào bậc); Đỉnh cô lập ($\deg = 0$), đỉnh treo ($\deg = 1$); Bậc vào $\deg^-(v)$ và bậc ra $\deg^+(v)$ trong đồ thị có hướng.
-
Các phép toán và Họ đơn đồ thị đặc biệt:
- Các phép toán tạo đồ thị mới: Đồ thị con $H = (W, F)$, đồ thị con thực sự, đồ thị con cảm sinh $H = G[W]$, phép xóa đỉnh $G - V'$, xóa cạnh $G - E'$, thêm cạnh $G + E'$, và phép co cạnh (contraction) $G/e$.
- Các họ đồ thị đặc biệt: Đồ thị đầy đủ $K_n$, Chu trình $C_n$ ($n \ge 3$), Đồ thị bánh xe $W_n$ ($n \ge 3$), và Khối $n$-chiều $Q_n$ ($2^n$ đỉnh, gán nhãn chuỗi nhị phân $n$-bit, kề nhau khi khác nhau đúng 1 bit).
-
Đồ thị hai phần và Lý thuyết ghép cặp:
- Định nghĩa đồ thị hai phần $G = (V_1 \cup V_2, E)$ và đồ thị hai phần đầy đủ $K_{m,n}$.
- Khái niệm ghép cặp (matching) $M \subseteq E$, ghép cặp cực đại (maximum matching), tập cạnh bao phủ (cover), ghép cặp đầy đủ (complete matching) bao phủ $V_1$, và ghép cặp hoàn hảo (perfect matching) bao phủ toàn bộ $V$.
- Phát biểu và chứng minh Định lý Hall (Hall’s Marriage Theorem): Điều kiện cần và đủ để tồn tại ghép cặp bao phủ $V_1$ là $|S| \le |N_G(S)|$ với mọi $S \subseteq V_1$.
-
Biểu diễn đồ thị và Sự đẳng cấu:
- Cấu trúc biểu diễn: Danh sách kề (Adjacency list), Ma trận kề (Adjacency matrix) kích thước $n \times n$ (lưu số cạnh bội $m_{ij}$), và Ma trận liên thuộc (Incidence matrix) kích thước $n \times m$ ($a_{ij} \in {0, 1}$).
- Khái niệm đẳng cấu $G_1 \simeq G_2$ thông qua sự tồn tại của song ánh $f: V_1 \to V_2$ bảo toàn quan hệ kề: $uv \in E_1 \iff f(u)f(v) \in E_2$.
- Phương pháp sử dụng bất biến đồ thị (graph invariant) như số lượng đỉnh, số cạnh, dãy bậc của đỉnh và cấu trúc láng giềng để chứng minh hai đồ thị không đẳng cấu; phân tích độ phức tạp khi kiểm tra $n!$ song ánh.
-
Tính liên thông trong đồ thị:
- Định nghĩa đường đi (path) độ dài $n$, chu trình (circuit/cycle), đường đi đơn (simple path - không lặp lại cạnh).
- Khái niệm đồ thị liên thông (connected) và không liên thông (disconnected); phép hợp đồ thị $G_1 \cup G_2$.
- Thành phần liên thông (connected component) là đồ thị con liên thông cực đại; Mệnh đề khẳng định giữa hai đỉnh bất kỳ trong đồ thị liên thông luôn tồn tại một đường đi đơn.
Kiến thức nền tảng được xây dựng
- Lý thuyết tập hợp và Quan hệ nhị phân: Nền tảng thiết lập cấu trúc cạnh dưới dạng tập con 2 phần tử $[V]^2$ hoặc tích Descartes $V \times V$.
- Các định lý đại số cơ bản trên đồ thị:
- Định lý bắt tay (Định lý 1): $\sum_{v \in V} \deg(v) = 2m$, dẫn đến hệ quả tổng bậc luôn chẵn.
- Định lý về đỉnh bậc lẻ (Định lý 2): Mọi đồ thị vô hướng luôn có một số chẵn các đỉnh có bậc lẻ.
- Định lý cân bằng bậc đồ thị có hướng (Định lý 3): $|E| = \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v)$.
- Phương pháp chứng minh quy nạp mạnh: Áp dụng trực tiếp trong chứng minh điều kiện đủ của Định lý Hall qua việc phân tách hai trường hợp $|N_G(S)| > |S|$ và tồn tại tập thực sự $|N_G(T)| = |T|$.
- Khung phân tích đại số tuyến tính: Chuyển đổi mô hình đồ họa sang các ma trận nhị phân và đối xứng để tính toán và lưu trữ.
Kỹ năng phát triển
- Kỹ năng kỹ thuật (Technical skills): Thiết lập chính xác danh sách kề, ma trận kề $n \times n$ cho cả đồ thị có hướng/vô hướng có cạnh bội, và ma trận liên thuộc $n \times m$.
- Kỹ năng phân tích (Analytical skills): Sử dụng các bất biến đồ thị để bác bỏ quan hệ đẳng cấu; kiểm tra điều kiện Hall trên các tập con $S \subseteq V_1$; phân tích tính liên thông và các thành phần liên thông cực đại.
- Kỹ năng suy luận toán học (Mathematical reasoning): Vận dụng nguyên lý bù trừ, phản chứng (như chứng minh đường đi ngắn nhất giữa hai đỉnh liên thông bắt buộc phải là đường đi đơn) và quy nạp cấu trúc.
Phương pháp giảng dạy và học tập
Tài liệu được xây dựng theo phương pháp sư phạm diễn dịch kết hợp trực quan hóa, phù hợp cho bài giảng lý thuyết chuẩn tại giảng đường đại học:
- Tiếp cận từng bước (Step-by-step exposition): Khái niệm luôn được giới thiệu qua các hình vẽ mô phỏng cụ thể (đồ thị có gán nhãn đỉnh ${v_1, v_2, \dots, v_n}$, cạnh $e_i$), sau đó mới trừu tượng hóa thành định nghĩa toán học tổng quát.
- Hệ thống ví dụ minh họa và phản ví dụ:
- Ví dụ 8, 9, 10: Minh họa cách tính bậc và áp dụng Bổ đề bắt tay để giải bài toán định lượng (đồ thị 10 đỉnh bậc 6 có 30 cạnh; bác bỏ sự tồn tại của đồ thị 5 đỉnh đều có bậc 3 vì tổng bậc bằng 15 là số lẻ).
- Ví dụ 13: Hướng dẫn phương pháp chứng minh hai đồ thị $G$ và $H$ không đẳng cấu thông qua việc phân tích cấu trúc láng giềng của các đỉnh bậc 2.
- Ví dụ 14, 15: Phân biệt đường đi và chu trình trên đồ thị vô hướng và có hướng.
- Bài tập rèn luyện tư duy chứng minh:
- Bài tập 1 & 3: Chứng minh đồ thị đầy đủ $K_n$ ($n \ge 3$) và đồ thị bánh xe $W_n$ ($n \ge 3$) không phải là đồ thị hai phần.
- Bài tập 2: Chứng minh tính chất di truyền: đồ thị con của một đồ thị hai phần cũng là đồ thị hai phần.
- Bài tập 4: Tìm đường đi, đường đi đơn và chu trình có độ dài $n$ cho trước trên đồ thị mẫu.
- Đánh giá và Tự học: Người học cần tự kiểm tra tính nhất quán của các định nghĩa bằng cách lập bảng ma trận, vẽ lại các thao tác biến đổi đồ thị ($G-v, G-e, G/e$), và tái hiện chứng minh quy nạp của Định lý Hall theo hai trường hợp độc lập.
Điểm nổi bật và cập nhật
Tài liệu thể hiện tính học thuật nghiêm ngặt thông qua các điểm xử lý nội dung chuyên sâu:
-
Chuẩn hóa và đối chiếu thuật ngữ quốc tế: Tài liệu chủ động làm rõ các điểm dị biệt trong định nghĩa giữa các trường phái học thuật. Cụ thể, tại Mục phân loại đồ thị, tác giả ghi chú rõ: Định nghĩa đa đồ thị có hướng (directed multigraph) trong bài giảng quy ước không có khuyên, khác với quy ước trong giáo trình kinh điển của Kenneth H. Rosen (Discrete Mathematics and Its Applications), nơi đa đồ thị có hướng có thể cho phép khuyên. Sự phân định này giúp người học tránh nhầm lẫn khi tra cứu tài liệu tham khảo chéo.
-
Bảng phân loại toàn diện 8 mô hình đồ thị: Thay vì chỉ nêu định nghĩa rời rạc, tài liệu tổng hợp thành bảng đối sánh 3 tiêu chí (Loại cạnh, Có cạnh song song, Có khuyên) cho 8 loại đồ thị, bao gồm cả mô hình đồ thị hỗn hợp (mixed graph) và giả đồ thị (pseudograph).
-
Gắn kết cấu trúc lý thuyết với độ phức tạp tính toán:
- Khi trình bày về sự đẳng cấu, bài giảng phân tích rõ độ phức tạp $n!$ của phép thử vét cạn song ánh và cập nhật tình trạng mở của bài toán: hiện chưa biết có hay không một thuật toán thời gian đa thức để kiểm tra tính đẳng cấu tổng quát giữa hai đồ thị.
- Khi chứng minh Định lý Hall, tài liệu lưu ý rõ ràng: Chứng minh bằng quy nạp mạnh là chứng minh phi kiến thiết (không cho thuật toán hiệu quả), đồng thời mở rộng thêm rằng tồn tại chứng minh khác cho phép xây dựng thuật toán tìm ghép cặp cực đại trong thời gian đa thức.
Đối tượng sử dụng giáo trình
- Sinh viên đại học: Phù hợp cho sinh viên năm thứ nhất và năm thứ hai theo học các ngành Toán học, Toán tin, Khoa học Máy tính, Công nghệ Thông tin, Kỹ thuật Phần mềm và Hệ thống Thông tin thuộc học phần Toán rời rạc (mã học phần MAT3500).
- Yêu cầu kiến thức tiên quyết (Prerequisites):
- Kiến thức Toán rời rạc cơ sở: Lý thuyết tập hợp (tập con, tích Descartes, hợp, giao), ánh xạ (đơn ánh, toàn ánh, song ánh), quan hệ nhị phân.
- Phương pháp suy luận toán học: Quy nạp toán học thông thường và quy nạp mạnh, phương pháp phản chứng.
- Đại số tuyến tính căn bản: Khái niệm ma trận, kích thước ma trận $n \times m$, và các phép toán chỉ số hàng/cột.
- Giảng viên và Nghiên cứu viên: Sử dụng làm đề cương bài giảng chuẩn, khung trình chiếu slide học thuật hoặc tài liệu tham khảo cho việc xây dựng ngân hàng đề thi, bài tập trắc nghiệm và tự luận phần lý thuyết đồ thị cơ sở.
- Tự học và Tham khảo: Dành cho lập trình viên cần củng cố nền tảng toán học của cấu trúc dữ liệu đồ thị và giải thuật mạng.
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ụ trực tiếp cho sinh viên đại học khối ngành Toán - Cơ - Tin học và Công nghệ thông tin theo học học phần MAT3500 (Toán rời rạc), cũng như người học cần tài liệu chuẩn hóa về cấu trúc dữ liệu đồ thị.
2. Cần chuẩn bị kiến thức nền tảng nào trước khi học?
Người học cần nắm vững các khái niệm cơ bản về lý thuyết tập hợp, quan hệ nhị phân, các phép toán ma trận trong đại số tuyến tính và kỹ thuật chứng minh quy nạp toán học mạnh.
3. Điểm khác biệt về thuật ngữ giữa tài liệu này và sách của Kenneth H. Rosen là gì?
Trong tài liệu của TS. Hoàng Anh Đức, đa đồ thị có hướng (directed multigraph) được định nghĩa là có cạnh song song nhưng không chứa khuyên; trường hợp có cả cạnh song song và khuyên được gọi là đa đồ thị có hướng và có khuyên (directed pseudograph). Trong sách của Rosen, đa đồ thị có hướng thường được gộp chung và cho phép chứa khuyên.
4. Phương pháp chứng minh Định lý Hall trong tài liệu có cho thuật toán tìm ghép cặp không?
Không. Chứng minh bằng quy nạp mạnh trong bài giảng khẳng định sự tồn tại của ghép cặp đầy đủ (chứng minh phi kiến thiết). Tài liệu lưu ý rằng cần sử dụng một hướng tiếp cận chứng minh khác (dựa trên đường tăng - augmenting paths) để xây dựng thuật toán tìm ghép cặp cực đại trong thời gian đa thức.
5. Có những dạng bài tập trọng tâm nào trong phần Lý thuyết đồ thị I?
Các dạng bài tập trọng tâm gồm: áp dụng Bổ đề bắt tay để tính số cạnh/bậc; biểu diễn đồ thị bằng ma trận kề và ma trận liên thuộc; chứng minh một đồ thị không phải là đồ thị hai phần; tìm bất biến đồ thị để chứng minh hai đồ thị không đẳng cấu; và xác định tính liên thông, chu trình, đường đi đơn.
Kết luận
Bài giảng VNU-HUS MAT3500: Toán rời rạc – Lý thuyết đồ thị I của TS. Hoàng Anh Đức là tài liệu học thuật chuẩn hóa, trình bày mạch lạc các khái niệm cốt lõi của lý thuyết đồ thị từ phân loại, biểu diễn đại số, tính hai phần cho đến tính liên thông và sự đẳng cấu.
Sau khi hoàn thành nội dung phần I, lộ trình học tập tiếp theo sẽ chuyển tiếp sang Lý thuyết đồ thị II, bao gồm các chủ đề chuyên sâu: Đồ thị Euler và Hamilton, Cây và Cây khung nhỏ nhất, Đồ thị phẳng và Tô màu đồ thị. Người học có thể tham khảo song song giáo trình Discrete Mathematics and Its Applications của Kenneth H. Rosen cùng các bài giảng chuyên đề của Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQG Hà Nội để mở rộng kiến thức thuật toán.