Ma trận liên thuộc

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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

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

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 = (Aij) với quy ước:

         * Aij = 1 nếu cạnh i kề với cạnh j. 
         * Aij = 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[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 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) = 2e

(Trong minh họa hình trên: 7(-1) + 7(+1) = 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) = 2e

(Trong minh họa hình trên: 14(1) = 7*2 )

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

  1. ^ Reinhard Diestel. Graph Theory, Electronic Edition 2005. © Springer - Verlag Heidelberg, New York 1997, 2000, 2005
Các chủ đề chính trong toán học
Nền tảng toán học | Đại số | Giải tích | Hình học | Lý thuyết số | Toán học rời rạc | Toán học ứng dụng |
Toán học giải trí | Toán học tô pô | Xác suất thống kê