正則グラフ

正則グラフの詳細

正則グラフ（せいそくグラフ）とは、グラフ理論の中で、すべての頂点が同じ隣接頂点数を持つグラフのことを指します。言い換えれば、正則グラフでは、すべての頂点の次数が同じです。次数が k の正則グラフは「k-正則グラフ」や「次数 k の正則グラフ」と呼ばれます。

正則グラフの分類

次数が2以下の正則グラフは、比較的簡単に分類できます。具体的には、以下のようになります。

• - 0-正則グラフ: 連結していない頂点から構成される。
• - 1-正則グラフ: 連結していない辺で構成される。
• - 2-正則グラフ: 連結していない閉路から構成される。

さらに、次数3の正則グラフはしばしば「立方体グラフ」とも呼ばれています。

強正則グラフ

正則グラフの中でも特に興味深いものが、強正則グラフです。これは、隣接する2つの頂点が常に同じ l 個の共通の隣接点を持ち、隣接しない2つの頂点が常に同じ n 個の共通の隣接点を持つグラフです。強正則でない正則グラフの中で最小のものは、6つの頂点から成る閉路グラフです。

完全グラフ K_m は、任意の m に対して強正則の性質を持ちます。さらに、クリスピン・ナッシュ＝ウィリアムズの定理によると、2k+1個の頂点から成る k-正則グラフには必ずハミルトン路が含まれています。

代数的属性

正則グラフの性質に関して、代数的な視点も重要です。あるグラフの隣接行列を A とした場合、グラフが k-正則であるための条件は、ベクトル j = (1, …, 1) が A の固有値 k に対応する固有ベクトルであることです。別の固有値に属する固有ベクトルは j と直交します。具体的には、そのような固有ベクトルは v = (v_1, …, v_n) と表され、次の条件が成り立ちます：

\[ \sum_{i=1}^{n} v_i = 0 \]

また、次数 k の正則グラフが連結していることと、固有値 k の重複度が1であることは同値です。正則な連結グラフを判定する基準も存在し、グラフが連結かつ正則である場合、行列 J がその隣接代数に含まれることも必要です。

直径と固有値

グラフ G が k-正則であるとし、直径を D とし、隣接行列の固有値の群が \( k = \lambda_0 > \lambda_1 \geq \dots \geq \lambda_{n-1} \) とした場合、G が二部グラフでないならば以下の不等式が成り立ちます。

\[ D \leq \frac{\log(n-1)}{\log(k/\lambda)} + 1 \]

ここで、\( \lambda = \max_{i > 0} \{ | \lambda_i | \} \) と定義されます。

グラフ生成ソフトウェア

正則グラフを生成するための便利なソフトウェアも存在します。その一例が GenReg です。これを用いることで、さまざまな正則グラフを効率よく生成できます。

関連項目

正則グラフや強正則グラフについて知識を深めることは、グラフ理論全般の理解を助けます。興味のある方は、参考文献やオンラインリソースを活用してさらなる学びを深めてみてください。

もう一度検索