✨Ma trận liên thuộc

Trong lý thuyết đồ thị, ta có thể biểu diễn 1 đồ thị G=(V,E) [có hướng hay vô hướng] thành một ma trận liên thuộc (incidence matrix).

Định nghĩa

Có hướng

—Nếu G là đồ thị có hướng không có khuyên, ma trận liên thuộc (hay liên kết đỉnh cạnh) của đồ thị G, ký hiệu A(G), là ma trận n*m (n: số đỉnh, m: số cạnh) được định nghĩa là A = (A_ij) với quy ước:

 * A<sub>ij</sub> = 1 nếu cạnh j hướng ra khỏi đỉnh i 
 * A<sub>ij</sub> = -1 nếu cạnh j hướng vào đỉnh i. 
 * A<sub>ij</sub> = 0 nếu cạnh j không kề đỉnh i.

DTLT Có Hướng MTLT Có Hướng

Vô hướng

—Nếu G là đồ thị vô hướng không có khuyên, ma trận liên thuộc (hay liên kết đỉnh cạnh) của đồ thị G, ký hiệu A(G), là ma trận n*m (n: số đỉnh, m: số cạnh) được định nghĩa là A = (A_ij) với quy ước:

 * A<sub>ij</sub> = 1 nếu đỉnh i kề với cạnh j. 
 * A<sub>ij</sub> = 0 nếu ngược lại.

DTLT Vô Hướng MTLT Vô Hướng

Bậc Đồ Thị Dựa Vào Bảng Ma Trận

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. Ký hiệu: Σdeg^-(v) = Σdeg⁺(v) = |E|, trong đó |E| là số cạnh của đồ thị (Trong minh họa hình trên: 7_(-1) = 7₍₊₁₎ = 7)
• Tổng bậc của tất cả các đỉnh = 2 lần số cạnh. Ký hiệu: Σdeg(v) = 2|E| (Trong minh họa hình trên: 7_(-1) + 7₍₊₁₎ = 7*2)

Vô hướng

• Tổng bậc của tất cả các đỉnh = 2 lần số cạnh. Ký hiệu: Σdeg(v) = 2|E| (Trong minh họa hình trên: 14₍₁₎ = 7*2 )

Ví dụ:Nếu một đồ thị có 6 đỉnh bậc 3,2 đỉnh bậc 4,4 đỉnh bậc 5(tổng cộng 12 đỉnh) thì đồ thị có bao nhiêu cạnh?

Số cạnh 2|E|=6x3+2x4+4x5=46$\backslash Rightarrow$ |E|=23

• Hệ quả:Số lượng các đỉnh bậc lẻ trong một đồ thị bất kì là số chẵn

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