6 Regular Graphs ぱらぱらめくる『Graphs and Matrices』

• 全ノードの次数が等しいグラフがRegular
• 6.1 Perron-Frobenius theory
  • 成分が正である実正方行列には唯一つの最大実固有値が存在し、それに対応する固有ベクトルの各成分は厳密に正である、という主張。グラフのノードの重みづけ(ページランク)計算などに用いられる
• 6.2 Adjacency algebra of a regular graph
  • Adjacency matrixのべき乗を項とする多項式で表される行列の集合を考える
  • この集合に全要素が１の行列Jが含まれることがconnected で regularであることの必要十分
• 6.3 Complement and line graph of a regular graph
  • Regular グラフのadjacency matrixとLaplacian matrixには単純な関係がある。またそのグラフの補グラフにも同様の関係があり、そのグラフのLine graph(エッジをノードと見立てたグラフ)にも同様に単純な関係がある。特性多項式を使って表現できる関係である
• 6.4 Strongly regular graphs and friendship theorem
  • Strongly regular graphsは(n,k,a,c)と４つのパラメタで表される。n個のノード、次数がk、隣接ノードはa個のcommon neighborsを持ち、非隣接ノードはc 個のcommon neighborsを持つ(Wiki記事)
• 6.5 Graphs with maximum energy