スペクトルグラフ理論

数学において、スペクトルグラフ理論は、隣接行列もしくはラプラシアン行列のような、そのグラフに結びついた行列の固有方程式、固有値、固有ベクトルに関係する、グラフの性質の研究である。

単純グラフの隣接行列は、実な対称行列であり、したがってであり；その固有値は実な代数的整数である。

頂点の名称付けによってその隣接行列が変わるのにたいして、それのスペクトルは、完全ではないものの、ひとつのである。

スペクトルグラフ理論は、のような、そのグラフと結びついた行列の固有値の重複度を通して定義される、グラフのパラメーターとも関係する。

 共スペクトルグラフ 
もし二つのグラフの隣接行列の固有値の多重集合が等しいならば、それらの二つのグラフは共スペクトル（）あるいは等スペクトル（）であると呼ばれる。

thumb |300px |あり得る最も小さな多面体グラフの、二つの等スペクトルな。
二つの共スペクトルグラフは互いに同型である必要はない、しかし同型なグラフは常に共スペクトルである。
 共スペクトルグラフを探すこと 
木は共スペクトルである、すなわち、頂点が増えるにつれ、共スペクトルな木があるような木の割合は1に近づいてゆく。

正則グラフの一対は、それらの補グラフが共スペクトルであるときにかぎり、共スペクトルである。

もしそれらが等しい交点配列（）を有するときに限り、一対のは共スペクトルである。

共スペクトルグラフはによっても構成されうる。

共スペクトルグラフのその他の重要な根拠としてはの、点-共線形グラフ（）と直線-交点グラフがある。これらのグラフは常に共スペクトルである、しかししばしばグラフ同型ではない。外部リンクのを見よ。

 脚注 
 出典 

 参考文献 


 吉田 悠一：「スペクトルグラフ理論: 線形代数からの理解を目指して」、サイエンス社(SGCライブラリ190），ISBN 978-4781916019、（2024年3月）.
 ボグダン・ニカ：「線形代数で考える スペクトラル・グラフ理論入門」、日本評論社、、（2024年4月）.

 関連文献 


 関連項目 

 強正則グラフ


 代数的グラフ理論




 外部リンク 





*
*
Category:数学に関する記事