Ma trận kề là gì? Biểu diễn đồ thị bằng ma trận kề, danh sách kề

Ma trận kề là một trong những phương pháp quan trọng và phổ biến nhất để biểu diễn đồ thị trong Toán học rời rạc và Khoa học máy tính. Ma trận kề (Adjacency Matrix) là ma trận vuông dùng để biểu diễn mối quan hệ kề nhau giữa các đỉnh trong đồ thị, trong đó phần tử a[i][j] cho biết có cạnh nối từ đỉnh i đến đỉnh j hay không. Bài viết dưới đây sẽ giúp bạn hiểu rõ định nghĩa, cách xây dựng, tính chất và các ứng dụng của ma trận kề.

1. Ma trận kề là gì?

Ma trận kề (tiếng Anh: Adjacency Matrix) là cách biểu diễn đồ thị dưới dạng ma trận vuông, phản ánh mối quan hệ kề nhau giữa các đỉnh.

1.1. Định nghĩa ma trận kề

Định nghĩa: Cho đồ thị G = (V, E) có n đỉnh được đánh số từ 1 đến n (hoặc 0 đến n-1). Ma trận kề A của đồ thị G là ma trận vuông cấp n×n, trong đó:

\[ A = (a_{ij})_{n \times n} \]

Với:

\[ a_{ij} = \begin{cases} 1 & \text{nếu có cạnh nối đỉnh i và đỉnh j} \\ 0 & \text{nếu không có cạnh nối đỉnh i và đỉnh j} \end{cases} \]

1.2. Các khái niệm cơ bản

Thuật ngữ	Ký hiệu	Ý nghĩa
Đồ thị	G = (V, E)	Tập đỉnh V và tập cạnh E
Đỉnh (Vertex)	v ∈ V	Các nút trong đồ thị
Cạnh (Edge)	e ∈ E	Đường nối giữa hai đỉnh
Kề nhau (Adjacent)	–	Hai đỉnh có cạnh nối trực tiếp
Ma trận kề	A	Ma trận biểu diễn quan hệ kề

1.3. Ví dụ trực quan

Cho đồ thị G có 4 đỉnh {1, 2, 3, 4} với các cạnh: (1,2), (1,3), (2,3), (3,4)

Ma trận kề của đồ thị:

\[ A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \]

Giải thích: \( a_{12} = 1 \) vì có cạnh (1,2), \( a_{14} = 0 \) vì không có cạnh (1,4).

2. Ma trận kề của đồ thị vô hướng

Đồ thị vô hướng là đồ thị mà các cạnh không có chiều, tức là cạnh (u, v) cũng là cạnh (v, u).

2.1. Đặc điểm của ma trận kề đồ thị vô hướng

• Ma trận đối xứng: \( a_{ij} = a_{ji} \) với mọi i, j
• Đường chéo chính: \( a_{ii} = 0 \) (nếu không có khuyên) hoặc \( a_{ii} = 1 \) (nếu có khuyên)
• Tổng mỗi hàng/cột: Bằng bậc của đỉnh tương ứng

2.2. Công thức

Với đồ thị vô hướng đơn (không có khuyên, không có cạnh song song):

\[ a_{ij} = a_{ji} = \begin{cases} 1 & \text{nếu } (i, j) \in E \\ 0 & \text{nếu } (i, j) \notin E \end{cases} \]

2.3. Ví dụ

Đồ thị vô hướng với đỉnh {A, B, C, D} và cạnh {(A,B), (A,C), (B,D), (C,D)}:

\[ A = \begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 1 & 1 & 0 \\ B & 1 & 0 & 0 & 1 \\ C & 1 & 0 & 0 & 1 \\ D & 0 & 1 & 1 & 0 \end{array} \]

Nhận xét: Ma trận đối xứng qua đường chéo chính.

2.4. Bậc của đỉnh từ ma trận kề

Bậc của đỉnh i = Tổng các phần tử trên hàng i (hoặc cột i):

\[ \deg(v_i) = \sum_{j=1}^{n} a_{ij} \]

3. Ma trận kề của đồ thị có hướng

Đồ thị có hướng là đồ thị mà mỗi cạnh có một chiều xác định, gọi là cung.

3.1. Đặc điểm của ma trận kề đồ thị có hướng

• Ma trận KHÔNG đối xứng (nói chung): \( a_{ij} \neq a_{ji} \)
• \( a_{ij} = 1 \) nếu có cung từ đỉnh i đến đỉnh j
• Tổng hàng i = Bán bậc ra của đỉnh i
• Tổng cột j = Bán bậc vào của đỉnh j

3.2. Công thức

\[ a_{ij} = \begin{cases} 1 & \text{nếu có cung từ i đến j: } (i \to j) \in E \\ 0 & \text{nếu không có cung từ i đến j} \end{cases} \]

3.3. Bán bậc ra và bán bậc vào

Khái niệm	Công thức	Ý nghĩa
Bán bậc ra (Out-degree)	\( \deg^+(v_i) = \sum_{j=1}^{n} a_{ij} \)	Số cung đi ra từ đỉnh i
Bán bậc vào (In-degree)	\( \deg^-(v_j) = \sum_{i=1}^{n} a_{ij} \)	Số cung đi vào đỉnh j

3.4. Ví dụ

Đồ thị có hướng với đỉnh {1, 2, 3, 4} và các cung: 1→2, 1→3, 2→3, 3→4, 4→1:

\[ A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix} \]

Nhận xét:

• \( a_{12} = 1 \) (có cung 1→2), nhưng \( a_{21} = 0 \) (không có cung 2→1)
• Bán bậc ra của đỉnh 1: \( 1 + 1 + 0 = 2 \)
• Bán bậc vào của đỉnh 3: \( 1 + 1 + 0 + 0 = 2 \)

4. Cách xây dựng ma trận kề

Để xây dựng ma trận kề cho một đồ thị, ta thực hiện theo các bước sau:

4.1. Các bước xây dựng

1. Bước 1: Đánh số các đỉnh từ 1 đến n (hoặc 0 đến n-1)
2. Bước 2: Tạo ma trận vuông n×n, khởi tạo tất cả phần tử bằng 0
3. Bước 3: Với mỗi cạnh (i, j) trong đồ thị:
   • Đồ thị vô hướng: Đặt \( a_{ij} = a_{ji} = 1 \)
   • Đồ thị có hướng: Đặt \( a_{ij} = 1 \)
4. Bước 4: Kiểm tra lại ma trận

4.2. Sơ đồ quy trình

Bước	Công việc	Kết quả
1	Đánh số đỉnh	V = {1, 2, …, n}
2	Khởi tạo ma trận	Ma trận n×n toàn số 0
3	Điền giá trị theo cạnh	Đặt 1 tại vị trí có cạnh
4	Kiểm tra	Ma trận kề hoàn chỉnh

4.3. Ma trận kề có trọng số

Với đồ thị có trọng số (weighted graph), ma trận kề được mở rộng:

\[ a_{ij} = \begin{cases} w_{ij} & \text{nếu có cạnh (i, j) với trọng số } w_{ij} \\ 0 \text{ hoặc } \infty & \text{nếu không có cạnh} \end{cases} \]

Ví dụ: Đồ thị có trọng số với cạnh (1,2) trọng số 5, (1,3) trọng số 3, (2,3) trọng số 2:

\[ A = \begin{pmatrix} 0 & 5 & 3 \\ 5 & 0 & 2 \\ 3 & 2 & 0 \end{pmatrix} \]

5. Tính chất của ma trận kề

Ma trận kề có nhiều tính chất quan trọng giúp phân tích đồ thị:

5.1. Tính chất cơ bản

Tính chất	Đồ thị vô hướng	Đồ thị có hướng
Đối xứng	\( A = A^T \)	Không (nói chung)
Đường chéo chính	= 0 (không có khuyên)	= 0 (không có khuyên)
Tổng tất cả phần tử	= 2|E| (2 lần số cạnh)	= |E| (số cung)
Phần tử	0 hoặc 1	0 hoặc 1

5.2. Tính chất của lũy thừa ma trận kề

Định lý quan trọng: Phần tử \( (A^k)_{ij} \) của ma trận \( A^k \) bằng số đường đi có độ dài k từ đỉnh i đến đỉnh j.

\[ (A^k)_{ij} = \text{Số đường đi độ dài k từ i đến j} \]

Lũy thừa	Ý nghĩa của \( (A^k)_{ij} \)
\( A^1 \)	Số đường đi độ dài 1 (cạnh trực tiếp)
\( A^2 \)	Số đường đi độ dài 2
\( A^3 \)	Số đường đi độ dài 3
\( A^k \)	Số đường đi độ dài k

5.3. Tính liên thông

Đồ thị liên thông khi và chỉ khi ma trận:

\[ B = I + A + A^2 + … + A^{n-1} \]

không có phần tử nào bằng 0 (ngoại trừ đường chéo nếu xét đồ thị không có khuyên).

5.4. Giá trị riêng của ma trận kề

• Giá trị riêng lớn nhất của ma trận kề gọi là bán kính phổ
• Với đồ thị vô hướng, tất cả giá trị riêng đều là số thực (vì ma trận đối xứng)

6. Ưu điểm và nhược điểm của ma trận kề

Khi sử dụng ma trận kề, cần cân nhắc các ưu và nhược điểm:

6.1. Ưu điểm

• Kiểm tra cạnh nhanh: Kiểm tra có cạnh (i, j) hay không chỉ mất O(1)
• Dễ cài đặt: Cấu trúc dữ liệu đơn giản (mảng 2 chiều)
• Phù hợp với đồ thị dày: Hiệu quả khi đồ thị có nhiều cạnh
• Dễ thực hiện các phép toán ma trận: Nhân ma trận, tìm lũy thừa
• Tính toán bậc đỉnh dễ dàng: Tổng hàng/cột

6.2. Nhược điểm

• Tốn bộ nhớ: Luôn cần O(n²) bộ nhớ, kể cả đồ thị thưa
• Duyệt đỉnh kề chậm: Phải duyệt cả hàng O(n) để tìm đỉnh kề
• Không hiệu quả với đồ thị thưa: Lãng phí khi số cạnh ít
• Thêm/xóa đỉnh khó: Phải thay đổi kích thước ma trận

6.3. So sánh với danh sách kề

Tiêu chí	Ma trận kề	Danh sách kề
Bộ nhớ	O(n²)	O(n + m)
Kiểm tra cạnh (i,j)	O(1)	O(degree(i))
Duyệt đỉnh kề của i	O(n)	O(degree(i))
Thêm cạnh	O(1)	O(1)
Xóa cạnh	O(1)	O(degree)
Phù hợp	Đồ thị dày	Đồ thị thưa

Ghi chú: n = số đỉnh, m = số cạnh

7. Ứng dụng của ma trận kề

Ma trận kề được ứng dụng rộng rãi trong nhiều lĩnh vực:

7.1. Trong thuật toán đồ thị

• Duyệt đồ thị: BFS, DFS
• Tìm đường đi ngắn nhất: Floyd-Warshall (dùng ma trận)
• Kiểm tra liên thông: Dùng lũy thừa ma trận
• Đếm đường đi: Tính \( A^k \) để đếm đường đi độ dài k

7.2. Trong mạng xã hội

• Biểu diễn quan hệ bạn bè
• Phân tích cộng đồng
• Đề xuất kết bạn (bạn của bạn = \( A^2 \))

7.3. Trong khoa học máy tính

• Biểu diễn mạng máy tính
• Phân tích liên kết web (PageRank)
• Tối ưu hóa mạng

7.4. Trong toán học

• Lý thuyết phổ đồ thị
• Đại số tổ hợp
• Nghiên cứu cấu trúc đồ thị

7.5. Bảng tổng hợp ứng dụng

Lĩnh vực	Ứng dụng cụ thể
Thuật toán	Floyd-Warshall, đếm đường đi
Mạng xã hội	Quan hệ bạn bè, đề xuất
Vận tải	Mạng lưới giao thông
Sinh học	Mạng protein, gen
Hóa học	Cấu trúc phân tử

8. Ví dụ và bài tập minh họa có lời giải chi tiết

Để nắm vững cách xây dựng và sử dụng ma trận kề, hãy cùng làm các bài tập sau:

Bài tập 1: Xây dựng ma trận kề đồ thị vô hướng

Đề bài: Cho đồ thị vô hướng G có 5 đỉnh {1, 2, 3, 4, 5} và các cạnh: (1,2), (1,3), (2,3), (2,4), (3,5), (4,5). Xây dựng ma trận kề của G.

Lời giải:

Bước 1: Tạo ma trận 5×5, khởi tạo bằng 0

Bước 2: Điền giá trị theo từng cạnh (đối xứng vì vô hướng)

• Cạnh (1,2): \( a_{12} = a_{21} = 1 \)
• Cạnh (1,3): \( a_{13} = a_{31} = 1 \)
• Cạnh (2,3): \( a_{23} = a_{32} = 1 \)
• Cạnh (2,4): \( a_{24} = a_{42} = 1 \)
• Cạnh (3,5): \( a_{35} = a_{53} = 1 \)
• Cạnh (4,5): \( a_{45} = a_{54} = 1 \)

Kết quả:

\[ A = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix} \]

Kiểm tra:

• Ma trận đối xứng ✓
• Đường chéo chính = 0 ✓
• Tổng phần tử = 12 = 2 × 6 cạnh ✓

Bài tập 2: Xây dựng ma trận kề đồ thị có hướng

Đề bài: Cho đồ thị có hướng G có 4 đỉnh {A, B, C, D} và các cung: A→B, A→C, B→C, C→D, D→A, D→B. Xây dựng ma trận kề của G.

Lời giải:

Đánh số: A=1, B=2, C=3, D=4

Điền theo từng cung (từ hàng đến cột):

• A→B: \( a_{12} = 1 \)
• A→C: \( a_{13} = 1 \)
• B→C: \( a_{23} = 1 \)
• C→D: \( a_{34} = 1 \)
• D→A: \( a_{41} = 1 \)
• D→B: \( a_{42} = 1 \)

Kết quả:

\[ A = \begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 1 & 1 & 0 \\ B & 0 & 0 & 1 & 0 \\ C & 0 & 0 & 0 & 1 \\ D & 1 & 1 & 0 & 0 \end{array} \]

Tính bán bậc:

• Bán bậc ra: A=2, B=1, C=1, D=2
• Bán bậc vào: A=1, B=2, C=2, D=1

Bài tập 3: Tính bậc của các đỉnh từ ma trận kề

Đề bài: Cho ma trận kề của đồ thị vô hướng:

\[ A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} \]

Tính bậc của mỗi đỉnh và tổng số cạnh.

Lời giải:

Tính bậc mỗi đỉnh: Tổng các phần tử trên mỗi hàng

• \( \deg(v_1) = 0 + 1 + 1 + 0 = 2 \)
• \( \deg(v_2) = 1 + 0 + 1 + 1 = 3 \)
• \( \deg(v_3) = 1 + 1 + 0 + 1 = 3 \)
• \( \deg(v_4) = 0 + 1 + 1 + 0 = 2 \)

Tổng bậc: \( 2 + 3 + 3 + 2 = 10 \)

Số cạnh: \( |E| = \frac{\text{Tổng bậc}}{2} = \frac{10}{2} = 5 \) cạnh

Kiểm tra: Tổng phần tử ma trận = 10 = 2 × 5 ✓

Bài tập 4: Đếm đường đi bằng lũy thừa ma trận

Đề bài: Cho ma trận kề:

\[ A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \]

Tìm số đường đi có độ dài 2 từ đỉnh 1 đến đỉnh 3.

Lời giải:

Tính \( A^2 \):

\[ A^2 = A \times A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \times \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \]

\[ = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix} \]

Phần tử \( (A^2)_{13} = 1 \)

Kết quả: Có 1 đường đi độ dài 2 từ đỉnh 1 đến đỉnh 3.

Đường đi đó là: 1 → 2 → 3

Bài tập 5: Ma trận kề có trọng số

Đề bài: Xây dựng ma trận kề có trọng số cho đồ thị vô hướng với các cạnh và trọng số: (A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,D,3).

Lời giải:

Đánh số: A=1, B=2, C=3, D=4

Dùng ∞ cho các cặp đỉnh không có cạnh (hoặc 0 trên đường chéo):

\[ A = \begin{pmatrix} 0 & 4 & 2 & \infty \\ 4 & 0 & 1 & 5 \\ 2 & 1 & 0 & 3 \\ \infty & 5 & 3 & 0 \end{pmatrix} \]

Hoặc dùng 0 thay cho ∞ (tùy quy ước):

\[ A = \begin{pmatrix} 0 & 4 & 2 & 0 \\ 4 & 0 & 1 & 5 \\ 2 & 1 & 0 & 3 \\ 0 & 5 & 3 & 0 \end{pmatrix} \]

Bài tập 6: Từ ma trận kề vẽ đồ thị

Đề bài: Cho ma trận kề của đồ thị có hướng:

\[ A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]

Liệt kê các cung và tính bán bậc của mỗi đỉnh.

Lời giải:

Liệt kê các cung: (vị trí có giá trị 1)

• \( a_{12} = 1 \): Cung 1 → 2
• \( a_{14} = 1 \): Cung 1 → 4
• \( a_{23} = 1 \): Cung 2 → 3
• \( a_{31} = 1 \): Cung 3 → 1
• \( a_{34} = 1 \): Cung 3 → 4

Tổng: 5 cung

Tính bán bậc:

Đỉnh	Bán bậc ra (tổng hàng)	Bán bậc vào (tổng cột)
1	2	1
2	1	1
3	2	1
4	0	2

Nhận xét: Đỉnh 4 là đỉnh thu (sink) vì bán bậc ra = 0.

Bài tập 7: Kiểm tra đồ thị có đường đi

Đề bài: Cho ma trận kề:

\[ A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]

Kiểm tra có đường đi từ đỉnh 1 đến đỉnh 4 không và độ dài ngắn nhất là bao nhiêu?

Lời giải:

Tính các lũy thừa của A:

\[ A^2 = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]

\[ A^3 = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]

Phân tích:

• \( (A)_{14} = 0 \): Không có đường đi độ dài 1
• \( (A^2)_{14} = 0 \): Không có đường đi độ dài 2
• \( (A^3)_{14} = 1 \): Có 1 đường đi độ dài 3

Kết quả: Có đường đi từ đỉnh 1 đến đỉnh 4, độ dài ngắn nhất là 3.

Đường đi: 1 → 2 → 3 → 4

9. Kết luận

Qua bài viết trên, VJOL đã giúp bạn hiểu rõ về ma trận kề cùng các kiến thức quan trọng liên quan. Tóm tắt những điểm cần nhớ:

• Ma trận kề là ma trận vuông n×n biểu diễn quan hệ kề nhau giữa các đỉnh trong đồ thị
• Đồ thị vô hướng: Ma trận kề đối xứng (\( A = A^T \))
• Đồ thị có hướng: Ma trận kề không đối xứng (nói chung)
• Tính chất quan trọng: \( (A^k)_{ij} \) = số đường đi độ dài k từ đỉnh i đến đỉnh j
• Ưu điểm: Kiểm tra cạnh O(1), dễ cài đặt, phù hợp đồ thị dày
• Nhược điểm: Tốn bộ nhớ O(n²), không hiệu quả với đồ thị thưa

Hy vọng bài viết đã giúp bạn nắm vững kiến thức về ma trận kề và có thể áp dụng vào giải toán hiệu quả!