Ma trận liên thuộc

Trong lý thuyết đồ thị,Reinhard Diestel. Graph Theory, Electronic Edition 2005. © Springer - Verlag Heidelberg, New York 1997, 2000, 2005 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 = (Aij) với quy ước:

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

185px|DTLT Có Hướng
185px|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 = (Aij) với quy ước:

     * Aij = 1 nếu đỉnh i kề với cạnh j. 
     * Aij = 0 nếu ngược lại.

185px|DTLT Vô Hướng
185px|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(+1) = 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(+1) = 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(1) = 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 |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

 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.

Thể loại:Đại số tuyến tính
Thể loại:Lý thuyết đồ thị
Thể loại:Ma trận
Thể loại:Toán học tổ hợp