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={}, tập U gồm n cạnh và được sắp thứ tự U={}

Đồ 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à  với:
 = 1 nếu  kề với cạnh 
 = 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.

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 =>  
1 kề với cạnh e2 =>  
1 kề với cạnh e4 =>  
1 kề với cạnh e5 =>  
2 kề với cạnh e3 =>  
2 kề với cạnh e4 =>  
2 kề với cạnh e6 =>  
3 kề với cạnh e1 =>  
3 kề với cạnh e2 =>  
3 kề với cạnh e3 =>  
4 kề với cạnh e5 =>  
4 kề với cạnh e6 =>  
Còn lại nếu đỉnh  không có kề với cạnh  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:

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à  với:
 = 1 nếu  hướng ra khỏi đỉnh 
 = -1 nếu  hướng vào đỉnh 
 = 0 nếu  không kề với đỉnh

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.

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 =>  
1 kề với cạnh e2 và e2 đi vào 1 =>  
1 kề với cạnh e4 và e4 đi ra khỏi 1 =>  
1 kề với cạnh e5 và e5 đi vào 1 =>  
2 kề với cạnh e3 và e3 đi ra khỏi 2 =>  
2 kề với cạnh e4 và e4 đi vào 2 =>  
2 kề với cạnh e6 và e6 đi ra khỏi 2 =>  
3 kề với cạnh e1 và e1 đi ra khỏi 3 =>  
3 kề với cạnh e2 và e2 đi ra khỏi 3 =>  
3 kề với cạnh e3 và e3 đi vào 3 =>  
4 kề với cạnh e5 và e5 đi ra khỏi 4 =>  
4 kề với cạnh e6 và e6 đi vào 4 =>  
Còn lại nếu đỉnh  không có kề với cạnh  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:

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ố

Chú thích

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.

Lý thuyết đồ thị