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). —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. —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. 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) 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 ⇒ {\displaystyle \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 ^ Reinhard Diestel. Graph Theory, Electronic Edition 2005. © Springer - Verlag Heidelberg, New York 1997, 2000, 2005