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 1 , x 2 , . . . , x n {\displaystyle 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 1 , u 2 , . . . , u n {\displaystyle u_{\text{1}},u_{\text{2}},...,u_{\text{n}}} } 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 ij {\displaystyle A=A_{\text{ij}}} với: A = A ij {\displaystyle A=A_{\text{ij}}} = 1 nếu x i {\displaystyle x_{\text{i}}} kề với cạnh u j {\displaystyle u_{\text{j}}} A = A ij {\displaystyle A=A_{\text{ij}}} = 0 nếu ngước lại 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 => A 11 = 1 {\displaystyle A_{\text{11}}=1} 1 kề với cạnh e2 => A 12 = 1 {\displaystyle A_{\text{12}}=1} 1 kề với cạnh e4 => A 14 = 1 {\displaystyle A_{\text{14}}=1} 1 kề với cạnh e5 => A 15 = 1 {\displaystyle A_{\text{15}}=1} 2 kề với cạnh e3 => A 23 = 1 {\displaystyle A_{\text{23}}=1} 2 kề với cạnh e4 => A 24 = 1 {\displaystyle A_{\text{24}}=1} 2 kề với cạnh e6 => A 26 = 1 {\displaystyle A_{\text{26}}=1} 3 kề với cạnh e1 => A 31 = 1 {\displaystyle A_{\text{31}}=1} 3 kề với cạnh e2 => A 32 = 1 {\displaystyle A_{\text{32}}=1} 3 kề với cạnh e3 => A 33 = 1 {\displaystyle A_{\text{33}}=1} 4 kề với cạnh e5 => A 45 = 1 {\displaystyle A_{\text{45}}=1} 4 kề với cạnh e6 => A 46 = 1 {\displaystyle A_{\text{46}}=1} Còn lại nếu đỉnh x i {\displaystyle x_{\text{i}}} không có kề với cạnh e j {\displaystyle 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: 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. 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 ij {\displaystyle A=A_{\text{ij}}} với: A = A ij {\displaystyle A=A_{\text{ij}}} = 1 nếu u j {\displaystyle u_{\text{j}}} hướng ra khỏi đỉnh x i {\displaystyle x_{\text{i}}} A = A ij {\displaystyle A=A_{\text{ij}}} = -1 nếu u j {\displaystyle u_{\text{j}}} hướng vào đỉnh x i {\displaystyle x_{\text{i}}} A = A ij {\displaystyle A=A_{\text{ij}}} = 0 nếu u j {\displaystyle u_{\text{j}}} không kề với đỉnh x i {\displaystyle x_{\text{i}}} 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 => A 11 = − 1 {\displaystyle A_{\text{11}}=-1} 1 kề với cạnh e2 và e2 đi vào 1 => A 12 = − 1 {\displaystyle A_{\text{12}}=-1} 1 kề với cạnh e4 và e4 đi ra khỏi 1 => A 14 = 1 {\displaystyle A_{\text{14}}=1} 1 kề với cạnh e5 và e5 đi vào 1 => A 15 = − 1 {\displaystyle A_{\text{15}}=-1} 2 kề với cạnh e3 và e3 đi ra khỏi 2 => A 23 = 1 {\displaystyle A_{\text{23}}=1} 2 kề với cạnh e4 và e4 đi vào 2 => A 24 = 1 {\displaystyle A_{\text{24}}=1} 2 kề với cạnh e6 và e6 đi ra khỏi 2 => A 26 = 1 {\displaystyle A_{\text{26}}=1} 3 kề với cạnh e1 và e1 đi ra khỏi 3 => A 31 = 1 {\displaystyle A_{\text{31}}=1} 3 kề với cạnh e2 và e2 đi ra khỏi 3 => A 32 = 1 {\displaystyle A_{\text{32}}=1} 3 kề với cạnh e3 và e3 đi vào 3 => A 33 = − 1 {\displaystyle A_{\text{33}}=-1} 4 kề với cạnh e5 và e5 đi ra khỏi 4 => A 45 = 1 {\displaystyle A_{\text{45}}=1} 4 kề với cạnh e6 và e6 đi vào 4 => A 46 = − 1 {\displaystyle A_{\text{46}}=-1} Còn lại nếu đỉnh x i {\displaystyle x_{\text{i}}} không có kề với cạnh e j {\displaystyle 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: 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. 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 Ma trận kề Ma trận trọng số 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.