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 = (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.

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.

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

Tham khảo

Đại số tuyến tính
Lý thuyết đồ thị
Ma trận
Toán học tổ hợp
Trong Lý thuyết đồ thị , ta có thể biểu diễnđồ 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 =nếu cạnh j hướng ra khỏi đỉnh i * Aij =nếu cạnh j hướng vào đỉnh i . * Aij =nếu cạnh j không kề đỉnh i . 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 =nếu đỉnh i kề với cạnh j . * Aij =nếu ngược lại . 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 : -1) =+1) = Tổng bậc của tất cả các đỉnh =lần số cạnh . Ký hiệu : Σdeg(v) =E| (Trong minh họa hình trên : -1) ++1) =2) Vô hướng Tổng bậc của tất cả các đỉnh =lần số cạnh . Ký hiệu : Σdeg(v) =E| (Trong minh họa hình trên : 1) =2 ) Ví dụ: Nếu một đồ thị cóđỉnh bậc2 đỉnh bậc4 đỉnh bậctổng cộngđỉnh) thì đồ thị có bao nhiêu cạnh ? Số cạnhE|=6 x3+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 Tham khảo Đại số tuyến tính Lý thuyết đồ thị Ma trận Toán học tổ hợp