代数的グラフ理論

代数グラフ理論は、代数的手法をグラフに関する問題に適用する数学の分野です。これは、幾何学的、組合せ論的、またはアルゴリズム的アプローチとは対照的です。代数グラフ理論には、線形代数の使用、群論の使用、およびグラフ不変量の研究を含む 3 つの主要な分野があります。

代数的グラフ理論の最初の分野は、線型代数に関連したグラフの研究です。特に、グラフの隣接行列またはラプラシアン行列のスペクトルを研究します（代数的グラフ理論のこの部分はスペクトルグラフ理論とも呼ばれます）。たとえば、ピーターセングラフの場合、隣接行列のスペクトルは (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3) です。いくつかの定理は、スペクトルの特性と他のグラフの特性を関連付けます。簡単な例として、直径Dの接続グラフは、そのスペクトルに少なくともD +1 個の異なる値を持ちます。^{[1]グラフスペクトルの}側面は、ネットワークの同期可能性の分析に使用されてきました。

代数的グラフ理論の2番目の分野は、群論、特に自己同型群と幾何群論に関連したグラフの研究である。対称性に基づくさまざまなグラフ族（対称グラフ、頂点推移グラフ、辺推移グラフ、距離推移グラフ、距離正則グラフ、強正則グラフなど）と、これらの族間の包含関係に焦点が当てられている。そのようなグラフのカテゴリの中には、グラフのリストを作成できるほどまばらなものがある。フルヒトの定理により、すべての群は連結グラフ（実際は立方グラフ）の自己同型群として表すことができる。^[2]群論とのもう1つの関連は、任意の群が与えられた場合、ケイリーグラフと呼ばれる対称グラフを生成できることであり、これらは群の構造に関連する特性を持つ。^[1]

代数的グラフ理論のこの2番目の分野は、グラフの対称性がスペクトルに反映されるため、最初の分野と関連しています。特に、ピーターセングラフなどの対称性の高いグラフのスペクトルには、異なる値はほとんどありません^[1]（ピーターセングラフには3つの値があり、これは直径を考えると最小値です）。ケイリーグラフの場合、スペクトルはグループの構造、特にその既約な特性に直接関連付けることができます。^{[1] [3]}

最後に、代数グラフ理論の3番目の分野は、グラフの不変量の代数的性質、特に彩色多項式、タット多項式、結び目不変量に関するものです。たとえば、グラフの彩色多項式は、その適切な頂点彩色の数を数えます。ピーターセングラフの場合、この多項式は です。^[1]特に、これはピーターセングラフを1色または2色で適切に彩色することはできないが、3色では120通りの方法で彩色できることを意味します。代数グラフ理論のこの分野における多くの研究は、4色定理を証明しようとする試みによって動機づけられました。しかし、同じ彩色多項式を持つグラフの特徴付けや、どの多項式が彩色であるかの決定など、まだ多くの未解決の問題が残っています。 ${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

• スペクトルグラフ理論
• 代数的組合せ論
• 代数的接続性
• ダルメージ・メンデルゾーン分解
• グラフプロパティ
• 隣接行列

• ウィキメディア・コモンズの代数的グラフ理論に関連するメディア