Ma trận liên kết

• Là một trong những cách biểu diễn đồ thị, biểu diễn mối quan hệ giữa các cạnh và các đỉnh của đồ thị, tạo ra ma trận để biểu diễn đồ thị.
• Còn được gọi là ma trận liên thuộc.
• 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}}$}

Đồ thị vô hướng

• Nếu G là đồ thị vô hướng, ma trận liên kết của đồ thị G, ký hiệu A(G), là ma trận nhị phân cấp (n x m) được định nghĩa là $A=A_{\text{ij}}$ với:
  • $A=A_{\text{ij}}$ = 1 nếu $x_{\text{i}}$ kề với cạnh $u_{\text{j}}$
  • $A=A_{\text{ij}}$ = 0 nếu ngước lại

Ví dụ

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

• Hãy biểu diễn đồ thị G với ma trận liên kết.

Đồ thị G

• Gọi A là ma trận biểu diễn đồ thị G.
• Từ đồ thị G, ta thấy:
  • 1 kề với cạnh e1 => $A_{\text{11}}=1$
  • 1 kề với cạnh e2 => $A_{\text{12}}=1$
  • 1 kề với cạnh e4 => $A_{\text{14}}=1$
  • 1 kề với cạnh e5 => $A_{\text{15}}=1$
  • 2 kề với cạnh e3 => $A_{\text{23}}=1$
  • 2 kề với cạnh e4 => $A_{\text{24}}=1$
  • 2 kề với cạnh e6 => $A_{\text{26}}=1$
  • 3 kề với cạnh e1 => $A_{\text{31}}=1$
  • 3 kề với cạnh e2 => $A_{\text{32}}=1$
  • 3 kề với cạnh e3 => $A_{\text{33}}=1$
  • 4 kề với cạnh e5 => $A_{\text{45}}=1$
  • 4 kề với cạnh e6 => $A_{\text{46}}=1$
  • Còn lại nếu đỉnh $x_{\text{i}}$ không có kề với cạnh $e_{\text{j}}$ thì gán giá trị 0.
• Kết quả sau khi biểu diễn đồ thị G sang ma trận liên kết:

Đồ thị G

Lưu ý: Hàng đầu tiên màu vàng là danh sách tất cả các cạnh trong đồ thị G.

Đồ thị có hướng

• Nếu G là đồ thị có hướng không có khuyên, ma trận liên kết của đồ thị G, ký hiệu A(G), là ma trận nhị phân cấp (n x m) được định nghĩa là $A=A_{\text{ij}}$ với:
  • $A=A_{\text{ij}}$ = 1 nếu $u_{\text{j}}$ hướng ra khỏi đỉnh $x_{\text{i}}$
  • $A=A_{\text{ij}}$ = -1 nếu $u_{\text{j}}$ hướng vào đỉnh $x_{\text{i}}$
  • $A=A_{\text{ij}}$ = 0 nếu $u_{\text{j}}$ không kề với đỉnh $x_{\text{i}}$

Ví dụ

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

• Hãy biểu diễn đồ thị G với ma trận liên kết.

Đồ thị G

• Gọi A là ma trận biểu diễn đồ thị G.
• Từ đồ thị G, ta thấy:
  • 1 kề với cạnh e1 và e1 đi vào 1 => $A_{\text{11}}=-1$
  • 1 kề với cạnh e2 và e2 đi vào 1 => $A_{\text{12}}=-1$
  • 1 kề với cạnh e4 và e4 đi ra khỏi 1 => $A_{\text{14}}=1$
  • 1 kề với cạnh e5 và e5 đi vào 1 => $A_{\text{15}}=-1$
  • 2 kề với cạnh e3 và e3 đi ra khỏi 2 => $A_{\text{23}}=1$
  • 2 kề với cạnh e4 và e4 đi vào 2 => $A_{\text{24}}=1$
  • 2 kề với cạnh e6 và e6 đi ra khỏi 2 => $A_{\text{26}}=1$
  • 3 kề với cạnh e1 và e1 đi ra khỏi 3 => $A_{\text{31}}=1$
  • 3 kề với cạnh e2 và e2 đi ra khỏi 3 => $A_{\text{32}}=1$
  • 3 kề với cạnh e3 và e3 đi vào 3 => $A_{\text{33}}=-1$
  • 4 kề với cạnh e5 và e5 đi ra khỏi 4 => $A_{\text{45}}=1$
  • 4 kề với cạnh e6 và e6 đi vào 4 => $A_{\text{46}}=-1$
  • Còn lại nếu đỉnh $x_{\text{i}}$ không có kề với cạnh $e_{\text{j}}$ thì gán giá trị 0.
• Kết quả sau khi biểu diễn đồ thị G sang ma trận liên kết:

Đồ thị G

Lưu ý: Hàng đầu tiên màu vàng là danh sách tất cả các cạnh trong đồ thị G.

Nhận xét

• Trong ma trận của đồ thị có hướng tổng bậc ra của các đỉnh = Tổng bậc vào của các đỉnh = Đỉnh.
• Trong ma trận của đồ thị vô hướng tổng bậc của tất cả các đỉnh = 2 lần số cạnh.
• Ưu điểm:
  • Đồ thị có cạnh song song
  • Ma trận liên thuộc đỉnh-cạnh sẽ tiết kiệm bộ nhớ hơn khi đồ thị có ít cạnh/cung.
• Khuyết điểm:
  • Biểu diễn phức tạp

Xem thêm

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

Tham khảo

• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics 173 (3rd ed.), Springer-Verlag, ISBN 3-540-26183-4.
• Coxeter, H.S.M. Regular Polytopes, (3rd edition, 1973), Dover edition, ISBN 0-486-61480-8 (Section 9.2 Incidence matrices, pp. 166–171)
• Jonathan L Gross, Jay Yellen, Graph Theory and its applications, second edition, 2006 (p 97, Incidence Matrices for undirect graphs; p 98, incidence matrices for digraphs)
• Weisstein, Eric W., "Incidence matrix" from MathWorld.