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