Wikipedia

スペクトルグラフ理論

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

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

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

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

共スペクトルグラフ

編集

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

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

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

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

編集

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

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

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

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

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

関連項目

編集

脚注または引用文献

編集
  1. ^ Schwenk (1973).
  2. ^ Godsil (2007).
  3. ^ Sunada (1985).
  4. ^ 外部リンクの(Brouwer & Haemers 2011)を見よ。

ウェブサイト

編集

書籍

編集
  • 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月）.

雑誌

編集

参考文献

編集

外部リンク

編集
「https://ja.wikipedia.org/w/index.php?title=スペクトルグラフ理論&oldid=102503864」から取得