跳至內容

度數矩陣

維基百科,自由的百科全書

數學領域圖論中,無向圖的度數矩陣(英語:degree matrix)是一個對角矩陣 ,其中包含的信息為的每一個頂點的度數,也就是每個頂點相鄰的邊數。[1] 它可以和鄰接矩陣一起使用以構造圖的拉普拉斯算子矩陣(拉普拉斯矩陣是度數矩陣和鄰接矩陣的差值)。[2]

定義

給定一個圖 度數矩陣 是一個 對角線矩陣,其定義為[1]

其中度數 為這個頂點上的邊的條數。 在無向圖中,這意味著每個環會使得度數增加2。 在有向圖中,術語「」可以指「入度」(indegree,終點在這個頂點的邊的條數)或「出度」( outdegree,起點在這個頂點的邊的條數)。

例子

下面的無向圖有一個6x6的度數矩陣,其數值為。

Vertex labeled graph 度數矩陣

注意,對於無向圖而言,開始和結束於同一節點的邊(即環,如上圖中的節點1)會使相應的度增加2(即被計算兩次)。

性質

一個k-正則圖的度數矩陣是恆為的對角線矩陣。

根據度的總和公式,度數矩陣的是對應圖的邊數的兩倍。

參考文獻

  1. ^ 1.0 1.1 Chung, Fan; Lu, Linyuan; Vu, Van, Spectra of random graphs with given expected degrees, Proceedings of the National Academy of Sciences of the United States of America, 2003, 100 (11): 6313–6318, MR 1982145, PMC 164443可免費查閱, PMID 12743375, doi:10.1073/pnas.0937490100 
  2. ^ Mohar, Bojan, Graph Laplacians, Beineke, Lowell W.; Wilson, Robin J. (編), Topics in algebraic graph theory, Encyclopedia of Mathematics and its Applications 102, Cambridge University Press, Cambridge: 113–136, 2004, ISBN 0-521-80197-4, MR 2125091 .