強正則グラフ

強正則グラフの概要

強正則グラフ（strongly regular graph）は、グラフ理論において重要な役割を果たす構造体です。これらのグラフは特定の条件を満たし、数学やコンピュータ科学、ネットワーク理論など多くの分野で応用が見られます。例えば、ネットワークのトポロジーやエラーレートの解析に利用されます。

定義と条件

強正則グラフは、正則グラフの一種であり、定義において次のような条件を揃えています。グラフ G = (V, E) が強正則であるとは、以下の整数 λ と μ が存在することです。

• - 任意の隣接する2頂点は、正確に λ 個の近傍を共有します。
• - 任意の隣接しない2頂点は、正確に μ 個の近傍を共有します。

このようなグラフは表記で srg(v, k, λ, μ) と呼ばれ、グラフの頂点数 v と次数 k を明示しています。また、1963年にラジ・チャンドラ・ボースによって導入されました。

なお、特定の著者による解釈では、完全グラフやその補グラフは強正則グラフには含めない場合があります。このようなグラフの補グラフもまた強正則グラフであることが知られています。補グラフの仕様は、srg(v, v−k−1, v−2−2k+μ, v−2k+λ) と表されることがあります。

性質とパラメータの関係

強正則グラフの4つの主要なパラメータ v, k, λ, μ は互いに独立ではなく、特定の関係を満たす必要があります。この関係は次の通りです：

$$(v-k-1)μ = k(k−λ−1)$$

この式は数え上げ論法によって簡単に示すことが可能です。グラフの全頂点を3つの層（階層）に分け、特定の条件を持つ接続関係を構築することで示されます。特に、層1の頂点と層2の頂点との接続関係がキーポイントとなります。

隣接行列と固有値

強正則グラフの隣接行列は、特有の行列方程式を満たす必要があります。まず、すべての行列の成分が1の行列 J に対して以下が成立します。

$$AJ = JA = kJ$$

これはグラフの正則性を示しており、k は固有値の一つであることが示されます。

次に、以下の二次式の関係も満たさなければなりません：

$$A^2 = kI + λA + μ(J - I - A)$$

ここで、左辺は長さ2のパスの数を示し、右辺は異なる構造の合計を表しています。この条件を満たすグラフは強正則グラフであると判断されます。特に、強正則グラフの隣接行列は3つの異なる固有値を持つことが知られています。

例

強正則グラフの具体例には、次のようなものがあります：

• - 長さ5の閉路グラフ：srg(5, 2, 0, 1)
• - ピーターセングラフ：srg(10, 3, 0, 1)
• - クレブシュグラフ：srg(16, 5, 0, 2)
• - シュリクハンデグラフ：srg(16, 6, 2, 2)

これらのグラフは様々な特性を持ち、特定の条件下で原始的な構造を形成します。

ムーアグラフ

特に λ = 0 の強正則グラフはトライアングルフリーと呼ばれ、既知のムーアグラフがいくつか存在します。これらのムーアグラフは特異な特性を持ち、数学的研究の重要な対象となっています。

結論

強正則グラフは、様々な数学的および応用分野で非常に有用な特徴を持っています。今後の研究においても、その性質や応用範囲は拡大していくことでしょう。

もう一度検索