Có người đề nghị hợp nhất bài viết này vào Ma trận liên kết. (Thảo luận)

Bài viết hoặc đoạn này cần được wiki hóa để đáp ứng tiêu chuẩn quy cách định dạng và văn phong của Wikipedia. Xin hãy giúp sửa bài viết này bằng cách thêm bớt liên kết hoặc cải thiện bố cục và cách trình bày bài. (tháng 9/2022)

Trong Lý thuyết đồ thị^[1], 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[sửa | sửa mã nguồn]

Có hướng[sửa | sửa mã nguồn]

—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:

    * 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[sửa | sửa mã nguồn]

—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:

    * 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[sửa | sửa mã nguồn]

Có hướng[sửa | sửa mã nguồn]

• 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[sửa | sửa mã nguồn]

• 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${\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

Tham khảo[sửa | sửa mã nguồn]

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Ma trận liên thuộc.