内周（グラフ理論）

グラフ理論では、無向グラフの内周は、グラフに含まれる最短の閉路の長さである。 ^[1]グラフに閉路が含まれていない場合（つまり、フォレストである場合）、その内周は無限大と定義される。^[2] たとえば、4閉路（正方形）の内周は4です。グリッドの内周も4で、三角形のメッシュの内周は3です。内周が4以上のグラフは三角形なしです。

可能な限り小さい内周gの立方グラフ（すべての頂点の次数が 3）はgケージ（または(3, g )ケージ）として知られています。ピーターセングラフは唯一の 5 ケージ（内周 5 の最小の立方グラフ）であり、ヒーウッドグラフは唯一の 6 ケージ、マギーグラフは唯一の 7 ケージ、タットの 8 ケージは唯一の 8 ケージです。^[3]与えられた内周に対して複数のケージが存在する場合があります。たとえば、それぞれ 70 個の頂点を持つ 3 つの非同型 10 ケージがあります。バラバン 10 ケージ、ハリーズグラフ、ハリーズ–ウォングラフです。

• 
  ピーターセングラフの内周は5である
• 
  ヒーウッドグラフの内周は6である。
• 
  マギーグラフの周囲長は7である
• 
  タット・コクセターグラフ（タ​​ット8ケージ）の内周は8である。

任意の正の整数gとχに対して、内周が​​少なくともgで彩色が少なくともχであるグラフが存在する。たとえば、Grötzsch グラフは三角形がなく彩色数が 4 であり、Grötzsch グラフを形成するために使用されるMycielskian構成を繰り返すと、任意の大きな彩色数の三角形のないグラフが生成されます。ポール・エルデシュは、確率的方法を使用して、一般的な結果を初めて証明しました。^[4]より正確には、彼は、各辺を含めるかどうかを確率n ^{(1– g )/ g}で独立に選択することによって形成されたn頂点のランダムグラフは、 n が無限大になるにつれて確率が 1 に近づくにつれて、最大で⁠ん/2⁠長さg以下のサイクルがサイズの独立した集合はない⁠ん/2k円 したがって、各短閉路から 1 つの頂点を削除すると、内周がgより大きい小さなグラフが残ります。この場合、色付けの各色クラスは小さくなければならず、したがって、どの色付けでも少なくともk色が必要になります。

明示的だが大きな内周と彩色数を持つグラフは、有限体上の線型群の特定のケーリーグラフとして構成することができる。^[5]これらの注目すべきラマヌジャングラフは、大きな展開係数も持つ。

グラフの奇数内周と偶数内周は、それぞれ最短の奇数サイクルと最短の​​偶数サイクルの 長さです。

のグラフの円周は、最短サイクルではなく、最長（単純）サイクルの長さです。

非自明なサイクルの最小の長さとして考えれば、内周は、シストリック幾何学における 1 シストールまたはそれ以上のシストールとして自然に一般化できます。

内周は辺の接続性と双対の概念であり、平面グラフの内周はその双対グラフの辺の接続性と等しく、逆もまた同様である。これらの概念はマトロイド理論において、マトロイドの内周、すなわちマトロイド内の最小の従属集合のサイズによって統一される。グラフィックマトロイドの場合、マトロイドの内周は基になるグラフの内周に等しく、コグラフィックマトロイドの場合は辺の接続性と等しい。^[6]

無向グラフの内周は、各ノードから幅優先探索を実行することで計算できます。複雑度はグラフの頂点数、辺数です。^[7]実用的な最適化は、BFS の深さを、これまでに発見された最小の閉路の長さに依存する深さに制限することです。^[8]内周が偶数の場合^[9]やグラフが平面の場合、より優れたアルゴリズムが知られています。^[10]下限の点では、グラフの内周を計算することは、少なくともグラフ上の 三角形検索問題を解くのと同じくらい難しいです。${\displaystyle O(nm)}$${\displaystyle n}$${\displaystyle m}$