単純グラフのラプラシアン行列
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/09/13 00:05 UTC 版)
「ラプラシアン行列」の記事における「単純グラフのラプラシアン行列」の解説
n個の頂点を持つ単純グラフを考えると、そのラプラシアン行列 L n × n {\textstyle L_{n\times n}} は以下の式で定義される。 L = D − A {\displaystyle L=D-A} 上式において、Dはグラフの次数行列、Aは隣接行列である。 G {\textstyle G} は単純グラフであるため、 A {\textstyle A} の成分は1または0のみであり、その対角要素は全て0である。 有向グラフの場合は、入次数または出次数のいずれかが、応用に依存して使われるだろう。 L {\textstyle L} の要素は式 L i , j := { deg ( v i ) if i = j − 1 if i ≠ j and v i is adjacent to v j 0 otherwise {\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}\end{cases}}} によって与えられる。上式において、 deg ( v i ) {\displaystyle \operatorname {deg} (v_{i})} は頂点 i {\displaystyle i} の次数である。
※この「単純グラフのラプラシアン行列」の解説は、「ラプラシアン行列」の解説の一部です。
「単純グラフのラプラシアン行列」を含む「ラプラシアン行列」の記事については、「ラプラシアン行列」の概要を参照ください。
- 単純グラフのラプラシアン行列のページへのリンク