Ma trận kề

Trong Toán học và Khoa học máy tính, ma trận kề (tiếng Anh: adjacency matrix) cho một đồ thị hữu hạn G gồm n đỉnh là một ma trận n × n, trong đó, các ô không nằm trên đường chéo chính a_ij là số cạnh nối hai đỉnh i và j, còn ô nằm trên đường chéo chính a_ii là hai lần số khuyên tại đỉnh i, hoặc chỉ là số khuyên tại đỉnh đó (bài này chọn cách thứ nhất, các đồ thị có hướng luôn theo cách thứ hai). Mỗi đồ thị có duy nhất một ma trận kề, các đồ thị khác nhau có các ma trận kề khác nhau. Trong trường hợp đặc biệt của đồ thị đơn hữu hạn, ma trận kề là một ma trận (0,1) với các giá trị 0 nằm trên đường chéo chính. Nếu đồ thị là vô hướng, ma trận kề là ma trận đối xứng.

Đối với đồ thị thưa, nghĩa là đồ thị có ít cạnh, người ta thường chọn dùng danh sách kề hơn do nó chiếm ít bộ nhớ hơn. Ma trận liên thuộc là một biểu diễn ma trận khác cho đồ thị.

Quan hệ giữa một đồ thị và ma trận kề của nó được nghiên cứu trong lý thuyết phổ đồ thị (spectral graph theory).

Khái niệm

• Xét đồ thị G=(X, U) (có hướng hay vô hướng)
• Giả sử tập X gồm n đỉnh và được sắp thứ tự X={$x_{\text{1}},x_{\text{2}},...,x_{\text{n}}$}, tập U gồm n cạnh và được sắp thứ tự U={$u_{\text{1}},u_{\text{2}},...,u_{\text{n}}$}

Quy tắc

Ma trận kề của đồ thị G, ký hiệu B(G), là một ma trận nhị phân cấp n x n được định nghĩa như sau: B=($B_{\text{ij}}$) với:

• B=($B_{\text{ij}}$ = 1 nếu có cạnh nối $x_{\text{i}}$ tới $x_{\text{j}}$
• B=($B_{\text{ij}}$ = 0 nếu không có cạnh nối $x_{\text{i}}$ tới $x_{\text{j}}$

Nếu G là đồ thị vô hướng, ma trận liên thuộc của đồ thị G, ký hiệu A(G), là ma trận nhị phân cấp nxm được định nghĩa như sau: A=($A_{\text{ij}}$)

• A=($A_{\text{ij}}$) = 1 nếu có cạnh nối $x_{\text{i}}$ tới $x_{\text{j}}$
• A=($A_{\text{ij}}$) = 0 nếu không có cạnh nối $x_{\text{i}}$ tới $x_{\text{j}}$

Biểu diễn

Đồ thị vô hướng

Cho đồ thị G vô hướng (7 đỉnh):

Đồ thị G

• Gọi A là ma trận kề biểu diễn đồ thị G.
• Từ đồ thị G, ta thấy:
  • 1 và 2 có cạnh nối => $A_{\text{12}}=A_{\text{21}}=1$
  • 1 và 4 có cạnh nối => $A_{\text{14}}=A_{\text{41}}=1$
  • 1 và 6 có cạnh nối => $A_{\text{16}}=A_{\text{61}}=1$
  • 2 và 3 có cạnh nối => $A_{\text{23}}=A_{\text{32}}=1$
  • 2 và 6 có cạnh nối => $A_{\text{26}}=A_{\text{62}}=1$
  • 3 và 4 có cạnh nối => $A_{\text{34}}=A_{\text{43}}=1$
  • 3 và 5 có cạnh nối => $A_{\text{35}}=A_{\text{53}}=1$
  • 3 và 7 có cạnh nối => $A_{\text{37}}=A_{\text{73}}=1$
  • 4 và 6 có cạnh nối => $A_{\text{46}}=A_{\text{64}}=1$
  • 4 và 5 có cạnh nối => $A_{\text{45}}=A_{\text{54}}=1$
  • 5 và 6 có cạnh nối => $A_{\text{56}}=A_{\text{65}}=1$
  • 6 và 7 có cạnh nối => $A_{\text{67}}=A_{\text{76}}=1$
  • Còn lại các cặp đỉnh không có cạnh nối với nhau => $A_{\text{ij}}$ = $A_{\text{ji}}$ = 0
• Kết quả sau khi biểu diễn đồ thị G sang ma trận kề:

Đồ thị G

• Trong đó dòng và cột màu vàng là danh sách các đỉnh của đồ thị vô hướng G.

Biểu diễn đồ thị có hướng

Cho đồ thị G có hướng (4 đỉnh):

Đồ thị G

• Gọi A là ma trận kề biểu diễn đồ thị G.
• Từ đồ thị G, ta thấy:
  • 1 và 2 có 1 cạnh nối và 1 đi vào 2 => $A_{\text{12}}=1$
  • 2 và 3 có 1 cạnh nối và 2 đi vào 3 => $A_{\text{23}}=1$
  • 3 và 1 có 2 cạnh nối và 3 đi vào 1 => $A_{\text{31}}=2$
  • 4 và 1 có 1 cạnh nối và 4 đi vào 1 => $A_{\text{41}}=1$
  • Còn lại các cặp đỉnh không có cạnh nối thì $A_{\text{ij}}=0$
• Kết quả sau khi biểu diễn đồ thị G sang ma trận kề:

Tính chất

• Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là:

$a[i,j]=a[j,i],i,j=1,2,...,n.$

Ngược lại, mỗi (0,1)-ma trận đối xứng cấp n sẽ tương ứng, chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hướng n đỉnh.

• Ma trận kề của đồ thị có hướng không phải là ma trận đối xứng.
• Đối với đồ thị vô hướng, tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j).
• Đối với đồ thị có hướng, tổng các phần tử trên dòng i (cột i) sẽ là bán bậc ra (bán bậc vào) của đỉnh i của đồ thị.

Nhận xét

• Ở cách biểu diễn ma trận này, ma trận sẽ không biểu diễn được:
  • Đồ thị có cạnh song song
• Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh.
• Nhược điểm lớn nhất của phương pháp này là: không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n^2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó.

Các tính chất

Ma trận kề của một đồ thị vô hướng có tính đối xứng, và do đó có một tập đầy đủ các giá trị riêng (eigenvalue) và cơ sở vectơ riêng (eigenvector) trực giao. Tập các giá trị riêng của đồ thị là phổ của đồ thị.

Giả sử cho trước hai đồ thị có hướng hoặc vô hướng G₁ và G₂ với các ma trận kề A₁ và A₂. G₁ và G₂ đẳng cấu (isomorphic) khi và chỉ khi tồn tại một ma trận hoán vị (permutation matrix) P sao cho

PA₁P ⁻¹ = A₂.

Cụ thể là A₁ và A₂ là các ma trận đồng dạng và do đó có cùng đa thức cực tiểu (minimal polynomial), đa thức đặc trưng (characteristic polynomial), các giá trị riêng, định thức (determinant) và vết của ma trận (trace). Do đó chúng có thể được dùng như các bất biến đẳng cấu của đồ thị. Cho trước hai ma trận kề, có thể xây dựng lại ma trận hoán vị đã được sử dụng: xem chi tiết tại Ma trận hoán vị.

Tuy nhiên, cần lưu ý rằng điều ngược lại không đúng: hai đồ thị có thể có bộ giá trị riêng giống nhau nhưng chúng không đẳng cấu. Phép nhân với ma trận hoán vị có thể được coi là việc gắn nhãn mới cho các cạnh.

Nếu A là ma trận kề của đồ thị có hướng hoặc vô hướng G, thì ma trận Aⁿ (ma trận tích của n lần A) có một ý nghĩa thú vị: ô tại hàng i và cột j cho biết số đường đi (có hướng hoặc vô hướng) có độ dài n từ đỉnh i tới đỉnh j.

Ma trận I − A (trong đó I ký hiệu ma trận đơn vị n×n) là nghịch đảo được khi và chỉ khi đồ thị G không có chu trình có hướng. Khi đó, ma trận nghịch đảo (I − A)⁻¹ có ý nghĩa sau: ô tại hàng i và cột j cho biết số đường đi có hướng từ đỉnh i tới đỉnh j (giá trị này luôn hữu hạn nếu đồ thị không có chu trình có hướng). Điều này có thể được giải thích bằng cấp số nhân (geometric series) của các ma trận:

(I − A)⁻¹ = I + A + A² + A³ +...

tương ứng với thực tế rằng số đường đi từ i tới j bằng số đường đi độ dài 0 cộng với số đường đi độ dài 1 cộng với số đường đi độ dài 2 v.v... Đường chéo chính của mọi ma trận kề tương ứng của đồ thị không có khuyên gồm toàn các ô chứa giá trị 0.

Ma trận kề của đồ thị phân đôi

Một ma trận kề A của một đồ thị phân đôi gồm r và s đỉnh có dạng:

$A={\begin{pmatrix}O&B\\B^{T}&O\end{pmatrix}}$

Trong đó B là một ma trận r × s và O là một ma trận toàn-số-0. Rõ ràng là ma trận B là đại diện duy nhất cho đồ thị phân đôi. Ta có G = (U, V, E) là một đồ thị phân đôi với các phần $U={u_{1},...,u_{r}}$ và $V={v_{1},...,v_{s}}$. Ma trận phân đôi là ma trận B r × s 0-1 trong đó $b_{i,j}=1$ khi và chỉ khi $(u_{i},v_{j})\in E$.

Nếu G là một đa đồ thị phân đôi hoặc đồ thị trọng số phân đôi thì các thành phần $b_{i,j}$ chứa giá trị tương ứng là bậc của các đỉnh hoặc trọng số của cạnh $(u_{i},v_{j}),$

Các biến thể

Ma trận kề (0,−1,1) của một đồ thị đơn có a_ii = 0 và a_ij = −1 nếu ij là một cạnh và bằng 1 nếu không phải là cạnh. Đồ thị này được dùng trong nghiên cứu các đồ thị chính quy mạnh (strongly regular graph) và các two-graph (đồ thị đôi???).

Các thỏa hiệp trong vai trò cấu trúc dữ liệu

Khi được sử dụng với vai trò cấu trúc dữ liệu, đối thủ chính của ma trận kề là danh sách kề. Do mỗi ô trong ma trận kề chỉ đòi hỏi một bit, nên chúng có thể được biểu diễn bằng một cách rất gọn, chỉ chiếm n²/8 byte bộ nhớ liên tục, trong đó n là số đỉnh. Ngoài việc tiết kiệm bộ nhớ, lưu trữ gọn gàng này còn khuyến khích locality of reference (tính địa phương của các truy nhập đến bộ nhớ).

Mặt khác, khi dùng cho đồ thị thưa, danh sách kề lại thắng thế, do chúng không lưu trữ các cạnh không tồn tại. Sử dụng cài đặt danh sách liên kết đơn giản trên một máy tính 32-bit, một danh sách kề cho một đồ thị vô hướng cần khoảng 16e byte, trong đó e là số cạnh của đồ thị.

Lưu ý rằng một đồ thị có thể có nhiều nhất n² cạnh (kể cả các khuyên). Giả sử d = e/n² ký hiệu mật độ của đồ thị. Ta có: 16e > n²/8, có nghĩa là danh sách kề chiếm nhiều không gian hơn khi d > 1/128. Do đó, chỉ nên dùng danh sách kề với đồ thị thưa.

Bên cạnh thỏa hiệp về không gian bộ nhớ, các cấu trúc dữ liệu khác nhau còn tạo thuận lợi cho các thao tác dữ liệu khác nhau. Với một danh sách kề, ta dễ dàng tìm mọi đỉnh kề với một đỉnh cho trước; ta chỉ cần đọc danh sách kề của đỉnh đó. Với một ma trận kề, ta phải duyệt toàn bộ một hàng, việc đó cần thời gian O(n). Còn nếu ta lại muốn biết giữa hai đỉnh cho trước có cạnh nối hay không, điều này có thể được xác định ngay lập tức với một ma trận kề, trong khi đó với một danh sách kề, việc này đòi hỏi thời gian tỷ lệ thuận với bậc nhỏ nhất của các đỉnh trong đồ thị.

Xem thêm

• Ma trận kề
• Ma trận trọng số

Tài liệu

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 22.1: Representations of graphs, pp. 527–531.