Ma trận bậc

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

Cho một đồ thị ${\displaystyle G=(V,E)}$ với ${\displaystyle \|V\|=n}$, ma trận bậc ${\displaystyle D}$ của đồ thị ${\displaystyle G}$ mà một ma trận vuông ${\displaystyle n\times n}$ được định nghĩa như sau

${\displaystyle d_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{nếu}}\ i=j\\0&{\mbox{ngược lại}}\end{matrix}}\right.}$

với giá trị bậc ${\displaystyle \deg(v_{i})}$ 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ụ

Đồ thị có nhãn đỉnh	Ma trận bậc
	${\displaystyle {\begin{pmatrix}4&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{pmatrix}}}$

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

• Ma trận bậc của đồ thị chính quy bậc k có một đường chéo chứa toàn các hằng số ${\displaystyle k}$.

Tham khảo

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ê