Ma trận bậc

Bách khoa toàn thư mở Wikipedia
Bước tới điều hướng Bước tới tìm kiếm

Trong lý thuyết đồ thị, ma trận bậc (tiếng Anh: degree matrix) là một ma trận đường chéo (diagonal matrix) chứa thông tin về bậc của mỗi đỉnh. [1]

Định nghĩa[sửa | sửa mã nguồn]

Cho một đồ thị với , ma trận bậc của đồ thị mà một ma trận vuông được định nghĩa như sau

với giá trị bậc của một đỉnh là số các cạnh kết thúc ở đỉnh đó. Trong một đồ thị vô hướng, điều này có nghĩa là mỗi vòng lặp (cạnh xuất phát và kết thúc cùng một đỉnh) sẽ có giá trị bậc là 2. Trong một đồ thị có hướng, thuật ngữ bậc có thể là bậc vào (indegree, số cạnh đến ở mỗi đỉnh) hoặc bậc ra (outdegree, số cạnh đi ra từ mỗi đỉnh).

Ví dụ[sửa | sửa mã nguồn]

Đồ thị có nhãn đỉnh Ma trận bậc
6n-graph2.svg

Trong đó, đỉnh số 1 có giá trị bậc là 4 (do có một vòng lặp nên tính là 2), đỉnh số 2 có giá trị bậc là 3 (kết nối với 3 cạnh) và các giá trị khác trên đường chéo ma trận tương ứng với số cạnh được kết nối ở mỗi đỉnh.

Tính chất[sửa | sửa mã nguồn]

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

  1. ^ Chung, Fan; Lu, Linyuan; Vu, Van (2003), “Spectra of random graphs with given expected degrees”, Proceedings of the National Academy of Sciences of the United States of America, 100 (11): 6313–6318, doi:10.1073/pnas.0937490100, MR 1982145, PMC 164443, PMID 12743375.
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ê