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

単純グラフの隣接行列は、対称行列であり、したがって直行行列に対角化可能英語版であり;その固有値は実な代数的整数である。

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

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

共スペクトルグラフ

編集

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

 
あり得る最も小さな多面体グラフの、二つの等スペクトルな九面体英語: enneahedron

二つの共スペクトルグラフは互いに同型である必要はない、しかし同型なグラフは常に共スペクトルである。

共スペクトルグラフを探すこと

編集

ほとんどすべてのは共スペクトルである、すなわち、頂点が増えるにつれ、共スペクトルな木があるような木の割合は1に近づいてゆく。[1]

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

もしそれらが等しい交点配列: inter-section array)を有するときに限り、一対の距離正則グラフ英語: distance-regular graphは共スペクトルである。

共スペクトルグラフは砂田の方法英語版によっても構成されうる。[3]

共スペクトルグラフのその他の重要な根拠としては点と直線の幾何英語版の、点-共線形グラフ: point-colinearity graph)と直線-交点グラフ: line-intersection graphがある。これらのグラフは常に共スペクトルである、しかししばしばグラフ同型ではない。[4]

関連項目

編集

脚注または引用文献

編集

ウェブサイト

編集

書籍

編集
  • Schwenk, A. J. (1973). “Almost All Trees are cospectral”. In Harary, Frank. New Directions in the Theory of Graphs. New York: Academic Press. p. 275-307. ISBN 012324255X. OCLC 890297242 
  • 吉田 悠一:「スペクトルグラフ理論: 線形代数からの理解を目指して」、サイエンス社(SGCライブラリ190),ISBN 978-4781916019、(2024年3月).
  • ボグダン・ニカ:「線形代数で考える スペクトラル・グラフ理論入門」、日本評論社、ISBN 978-4535790049、(2024年4月).

雑誌

編集

参考文献

編集

外部リンク

編集