内周 (グラフ理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数学グラフ理論の分野における内周(ないしゅう、: girth)とは、グラフに含まれる最小の閉路の長さのことを言う[1]。もしもグラフが閉路を含まないなら(すなわち、無閉路グラフであるなら)、その内周は無限大と定義される[2]。例えば、(平方)4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、トライアングルフリー英語版である。

ケージ[編集]

立方体グラフ(すべての頂点の次数が3であるグラフ)で、その内周が(可能な限り最小な) g であるようなものは、g-ケージ英語版(あるいは (3,g)-ケージ)として知られる。ピーターセングラフは唯一つの 5-ケージであり(内周が5であるような最小の立方体グラフである)、ヒーウッドグラフは唯一つの 6-ケージ、マギーグラフ英語版は唯一つの 7-ケージ、トゥッテ8-ケージ英語版は唯一つの 8-ケージである[3]。与えられた内周に対して、複数のケージが存在することもある。例えば、70個の頂点を持つ非同型な10-ケージは、三つ存在する:バラバン10-ケージ英語版ハリエスグラフ英語版、およびハリエス-ウォングラフ英語版である。

内周とグラフ彩色[編集]

任意の正の整数 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-シストールやより高位のシストールとしての自然な一般化が可能となる。

参考文献[編集]

  1. ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. ^ Girth -- Wolfram MathWorld, http://mathworld.wolfram.com/Girth.html 
  3. ^ Brouwer, Andries E., Cages, http://www.win.tue.nl/~aeb/drg/graphs/ . Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
  4. ^ Erdős, Paul (1959), “Graph theory and probability”, Canadian Journal of Mathematics 11: 34–38, doi:10.4153/CJM-1959-003-9 .