内周 (グラフ理論)

内周（Girth）について

グラフ理論において、内周（ないしゅう、英: girth）とは、特定のグラフに含まれる最小の閉路の長さを指します。この概念は、無閉路グラフ、すなわち閉路を持たないグラフにおいては、その内周を無限大と定義しています。たとえば、4つの頂点を持つ平方4-閉路グラフは内周が4であり、また格子グラフも内周が4です。一方、三角形メッシュの内周は3となります。内周が4以上のグラフは、特にトライアングルフリー、すなわち三角形を含まない特性を持ちます。

ケージ

内周に関連する用語として、ケージが挙げられます。これは、全ての頂点の次数が3である立方体グラフの一種で、内周が g であるものを g-ケージ、または (3,g)-ケージと呼びます。特に有名なケージとして、ピーターセングラフは唯一の5-ケージであり、内周が5の最小の立方体グラフです。その他にも、ヒーウッドグラフは独自の6-ケージ、マギーグラフは7-ケージ、トゥッテ8-ケージは8-ケージとして知られています。興味深いことに、与えられた内周に対しては、複数のケージが存在する場合があり、例えば70個の頂点を持つ非同型な10-ケージには、バラバン10-ケージ、ハリエスグラフ、ハリエス-ウォングラフの三つが存在します。

内周とグラフ彩色

数学的には、任意の正の整数 g と χ に対し、内周が少なくとも g であり、彩色数が少なくとも χ であるようなグラフが存在します。たとえば、グレッチグラフはトライアングルフリーでありながら彩色数が4の特性を持っています。これを構築するために用いられるミシェルスキアン構成法を繰り返すことで、彩色数の大小に関わらず任意のサイズのトライアングルフリーなグラフを作成することが可能です。このような性質を示したのがポール・エルデシュで、彼は確率論的手法により、特定のタイプのグラフがどのように機能するかを証明しました。具体的には、各辺が含まれるかどうかを独立に決定する確率が n(1 − g)/g であり、ランダムに生成されたグラフの中に、長さが g 以下の閉路を n/2個含むが、サイズが n/2k である独立集合を含まないという性質を証明しました。この結果は、特定の条件下で閉路を取り除くことにより、内周が g より大きく、各彩色の同色セットが小さくなるグラフが作成できることを示しています。

関連する概念

内周には、奇内周（odd girth）や偶内周（even girth）といった関連する概念があります。これらはそれぞれ最小の奇閉路と偶閉路の長さを指し、内周の理解を深める上で重要です。さらに、内周を用いた非自明な閉路の最小の長さを考慮することで、シストリック幾何学における1-シストールおよびより高度なシストールへの自然な一般化が実現可能となります。

このように、内周という概念はグラフの構造や性質を理解するための重要な枠組みであり、さまざまな数学的応用に結びついています。

もう一度検索