内周 (グラフ理論)
ウィキペディアから無料の百科事典
数学のグラフ理論の分野における内周（ないしゅう、英: girth）とは、グラフに含まれる最小の閉路の長さのことを言う[1]。もしもグラフが閉路を含まないなら（すなわち、無閉路グラフであるなら）、その内周は無限大と定義される[2]。例えば、（平方）4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、トライアングルフリーである。
ケージ
[編集]立方体グラフ（すべての頂点の次数が3であるグラフ）で、その内周が（可能な限り最小な） g であるようなものは、g-ケージ（あるいは (3,g)-ケージ）として知られる。ピーターセングラフは唯一つの 5-ケージであり（内周が5であるような最小の立方体グラフである）、ヒーウッドグラフは唯一つの 6-ケージ、マギーグラフは唯一つの 7-ケージ、トゥッテ8-ケージは唯一つの 8-ケージである[3]。与えられた内周に対して、複数のケージが存在することもある。例えば、70個の頂点を持つ非同型な10-ケージは、三つ存在する：バラバン10-ケージとハリエスグラフ、およびハリエス-ウォングラフである。
-
ピーターセングラフの内周は5である。 -
ヒーウッドグラフの内周は6である。 -
マギーグラフの内周は7である。 -
トゥッテ-コクセターグラフ（トゥッテ8-ケージ）の内周は8である。
内周とグラフ彩色
[編集]任意の正の整数 g と χ に対して、内周が少なくとも g であり、彩色数が少なくとも χ であるようなグラフが存在する：例えば、グレッチグラフはトライアングルフリーで彩色数が 4 であり、そのグラフを構成するためのミシェルスキアン構成法を繰り返すことで、任意の大きさの彩色数を備えるトライアングルフリーなグラフを構成することが出来る。ポール・エルデシュは、確率的手法を用いて、初めてその一般的な結果を証明した[4]。厳密に言うと彼は、各辺が含まれるかどうかが確率 n(1 − g)/g で独立に決定されるような頂点数 n のランダムグラフは、n が無限大へと向かうにつれて 1 に近付くような確率に対して、長さが g 以下であるような閉路を多くとも n/2 個含むが、大きさが n/2k であるような独立集合は含まない、ということを証明した。したがって、それぞれの短閉路（short cycle）から一つ頂点を取り除くことにより、内周が g より大きく、各彩色の同色集合が小さいためにどのような彩色においても少なくとも k 色が必要となるような、より小さいグラフが得られる。
関連のある概念
[編集]グラフの奇内周（odd girth）および偶内周（even girth）とは、それぞれ最小の奇閉路および偶閉路の長さのことを言う。
非自明な閉路の最小の長さを考えることで、内周は、シストリック幾何学における1-シストールやより高位のシストールとしての自然な一般化が可能となる。
参考文献
[編集]- ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
- ^ Girth -- Wolfram MathWorld
- ^ Brouwer, Andries E., Cages. Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
- ^ Erdős, Paul (1959), “Graph theory and probability”, Canadian Journal of Mathematics 11: 34–38, doi:10.4153/CJM-1959-003-9.
