Ma trận liên kết

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