立方体グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ピーターセングラフは立方体グラフである。
完全2部グラフ K_{3,3} は2部立方体グラフの一例である。

数学グラフ理論の分野における立方体グラフ(りっぽうたいグラフ、: cubic graph)とは、すべての頂点次数が 3 であるようなグラフのことを言う。言い換えると、立方体グラフとは 3-正則グラフである。立方体グラフは 3価グラフとも呼ばれる。2部立方体グラフ(bicubic graph)とは、立方体グラフかつ2部グラフであるようなグラフのことを言う。

対称性[編集]

1932年、ロナルド・フォスター英語版は、フォスター調査(Foster census)の皮切りとして、立方体対称グラフの例の集計をはじめた[1]設備グラフピーターセングラフヒーウッドグラフメビウス-カントールグラフ英語版パップスグラフ英語版デザルググラフ英語版ナウルグラフ英語版コクセターグラフ英語版トゥッテ-コクセターグラフ英語版ディックグラフ英語版フォスターグラフ英語版ビッグス-スミスグラフ英語版など、多くの有名なグラフは立方体かつ対称的であった。

ウィリアム・トーマス・タット英語版は、長さ s の各二つの有向路が、ちょうど一回のグラフの対称性によって互いに写される時、そのような s の最小のものによって対称立方体グラフを分類した。彼は、そのような s は多くとも 5 であることを示し、s が 1 から 5 であるような各グラフの例を提示した[2]

半対称立方体グラフには、グレイグラフ英語版(最小の半対称立方体グラフ)やリュブリャナグラフ英語版トゥッテ12-ケージ英語版が含まれる。

フルフトグラフ英語版は、対称性を持たない最小の立方体グラフの二つの内の一つである。それは、単一のグラフ自己同型英語版として、恒等自己同型のみを備える。

彩色と独立集合[編集]

グラフ理論英語版によると、完全グラフ K4 以外のすべての立方体グラフは、多くとも 3色によって彩色される。したがって、K4 以外のすべての立方体グラフは、少なくとも n/3 個の頂点の独立集合を持つことになる。ここで n はそのグラフ内の頂点の数とする:例えば、3-彩色における最大の色の類は、少なくともこのくらい多くの頂点を含む。

ビジングの定理英語版によると、すべての立方体グラフは、その辺彩色のために 3色か 4色を必要とする。3-辺彩色はテイト彩色として知られ、そのグラフの辺を三つの完全マッチングへと区分する。ケーニヒの線彩色定理英語版によれば、すべての2部立方体グラフにはテイト彩色が存在する。

テイト彩色が存在しない、橋のない立方体グラフはスナーク英語版として知られる。ピーターセングラフや、ティーツェのグラフ英語版ブラヌサスナーク英語版フラワースナーク英語版ダブルスタースナーク英語版スゼッケルスナーク英語版ワトキンススナーク英語版などが、これに該当する。スナークは無数に存在する[3]

位相と幾何[編集]

立方体グラフは位相幾何学の分野において、いくつかの方法によって自然に現れる。例えば、1-次元CW複体英語版であるようなグラフを考えた時、立方体グラフは、そのグラフの 0-スケルトンと最大 1-セル接着写像が互いに素であるようなジェネリック(generic)である。立方体グラフはまた、どの頂点においても三つの面が接している正十二面体のような、三次元における単純多面体のグラフとして構成される。

二次元平面上の任意のグラフ埋め込み英語版は、graph-encoded map として知られる立方体グラフの構造によって表現される。この構造において、立方体グラフの各頂点は埋め込みの英語版、すなわち、互いに付帯した頂点、辺および平面の表面からなる組を表す。各旗の三つの隣(neighbor)は、その組の内のどれか一つを変更し、他の二つはそのままにしたものとして得られるような三つの旗である[4]

ハミルトン性[編集]

立方体グラフのハミルトン性については多くの研究結果がある。1980年にP.G. テイト英語版は、すべての立方多面体グラフ英語版ハミルトン閉路を持つと予想した。このテイトの予想に対する反例は、ウィリアム・トーマス・トゥッテ英語版の 46-頂点トゥッテグラフ英語版によって、1946年に挙げられた。そのトゥッテは 1971年、すべての 2部立方体グラフはハミルトンであると予想した。しかし、ジョセフ・ホートンは 96-頂点ホートングラフ英語版をこの反例として挙げた[5]。その後、マーク・エリンガムはさらに二つの反例を挙げた:エリンガム-ホートングラフ英語版である[6][7]。未だに解決のなされていない、テイトとトゥッテの予想の組合せであるバーネットの予想英語版では、すべての二部立方多面体グラフはハミルトンである、としている。立方体グラフがハミルトンであるとき、LCF表記英語版によってそれを正確に表現することが出来る。

すべての n-頂点立方体グラフの中から一様にランダムに英語版一つの立方体グラフが選ばれるとき、それはハミルトンであることが非常に多い: n が無限大へと向かう極限において、n-頂点立方体グラフがハミルトンである割合は 1 となる[8]

デビッド・エプシュタイン英語版は、すべての n-頂点立方体グラフは多くとも 2n/3 個(およそ 1.260n 個)の異なるハミルトン閉路を含むと予想し、そのような多くの閉路を含む立方体グラフの例を提供した[9]。異なるハミルトン閉路の数について証明された最良の上界は、1.276n である[10]

他の性質[編集]

任意の n-頂点立方体グラフのパス幅英語版は、最大でも n/6 である。しかし、立方体グラフのパス幅の知られている下界のうち最良のものは、より小さく、0.082n である[11]

グラフ理論を初めて扱った、1736年のレオンハルト・オイラーによる論文の一部分において証明された握手補題英語版によると、すべての立方体グラフの頂点の数は偶数であることが分かる。

ジュリウス・ピーターセンの定理は、英語版の無いすべての立方体グラフには完全マッチングが存在する、というものである[12]

ロヴァース英語版とプラマーは、すべての橋の無い立方体グラフには、指数関数的な数の完全マッチングが存在すると予想した。この予想は近年、すべての橋の無い n 頂点立方体グラフには少なくとも 2n/3656 個の完全マッチングが存在する、という結果とともに証明された[13]

アルゴリズムと計算量[編集]

何人かの研究者は、立方体グラフに限定された指数関数時間アルゴリズムの計算量についての研究を行っている。例えば、グラフのパス分解英語版動的計画法を適用することにより、Fomin と Høie は時間 O(2n/6 + o(n)) 内に彼らの最大独立集合を見つける方法を示した[11]巡回セールスマン問題は、立方体グラフによって時間 O(1.251n) 内に解くことが出来る[14]

いくつかの重要なグラフ最適化問題はAPX困難である。すなわち、それらには近似率がある定数で評価されるような近似アルゴリズムが存在するが、(P=NPでない限り)近似率が 1 へと向かうような多項式時間近似スキームは存在しない。そのような問題には、最小の頂点被覆を見つける問題や最大独立集合、最小支配集合英語版最大カットを見つける問題などが含まれる[15]。立方体グラフの交叉数英語版(任意のグラフ描画英語版において交叉する辺の最小数)もまた、NP困難であるが、近似出来ることもある[16]

関連項目[編集]

参考文献[編集]

  1. ^ Foster, R. M. (1932), “Geometrical Circuits of Electrical Networks”, Transactions of the American Institute of Electrical Engineers 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068 .
  2. ^ Tutte, W. T. (1959), “On the symmetry of cubic graphs”, Canad. J. Math 11: 621–624, doi:10.4153/CJM-1959-057-2, http://cms.math.ca/cjm/v11/p621 .
  3. ^ Isaacs, R. (1975), [http://jstor.org/stable/2319844 “Infinite families of nontrivial trivalent graphs which are not Tait colorable”], American Mathematical Monthly 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844, http://jstor.org/stable/2319844 .
  4. ^ Bonnington, C. Paul; Little, Charles H. C. (1995), The Foundations of Topological Graph Theory, Springer-Verlag .
  5. ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
  6. ^ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  7. ^ Ellingham, M. N.; Horton, J. D. (1983), “Non-Hamiltonian 3-connected cubic bipartite graphs”, Journal of Combinatorial Theory, Series B 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1 .
  8. ^ Robinson, R.W.; Wormald, N.C. (1994), “Almost all regular graphs are Hamiltonian”, Random Structures and Algorithms 5 (2): 363–374, doi:10.1002/rsa.3240050209 .
  9. ^ Eppstein, David (2007), “The traveling salesman problem for cubic graphs”, Journal of Graph Algorithms and Applications 11 (1): 61–81, arXiv:cs.DS/0302030, http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf .
  10. ^ Gebauer, H. (2008), “On the number of Hamilton cycles in bounded degree graphs”, Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), http://zeno.siam.org/proceedings/analco/2008/anl08_023gebauerh.pdf .
  11. ^ a b Fomin, Fedor V.; Høie, Kjartan (2006), “Pathwidth of cubic graphs and exact algorithms”, Information Processing Letters 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012 .
  12. ^ Petersen, Julius Peter Christian (1891), “Die Theorie der regulären Graphs (The theory of regular graphs)”, Acta Mathematica 15 (15): 193–220, doi:10.1007/BF02392606 .
  13. ^ Esperer, Louis; Kardoš, František; King, Andrew D.; Král, Daniel; Norine, Serguei (2011), “Exponentially many perfect matchings in cubic graphs”, Advances in Mathematics 227 (4): 1646–1664, doi:10.1016/j.aim.2011.03.015 .
  14. ^ Iwama, Kazuo; Nakashima, Takuya (2007), “An Improved Exact Algorithm for Cubic Graph TSP”, Computing and Combinatorics, Lecture Notes in Computer Science, 4598, Springer-Verlag, pp. 108–117, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1 .
  15. ^ Alimonti, Paola; Kann, Viggo (2000), “Some APX-completeness results for cubic graphs”, Theoretical Computer Science 237 (1–2): 123–134, doi:10.1016/S0304-3975(98)00158-3 .
  16. ^ Hliněný, Petr (2006), “Crossing number is hard for cubic graphs”, Journal of Combinatorial Theory, Series B 96 (4): 455–471, doi:10.1016/j.jctb.2005.09.009 .

外部リンク[編集]