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

Định nghĩa

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ụ 

Đồ thị có nhãn đỉnhMa trận bậc175px

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ố .

Tham khảo

Thể loại:Lý thuyết đồ thị
Thể loại:Ma trận