立方体グラフのソースを表示

[[Image:Petersen1 tiny.svg|thumb|right|[[ピーターセングラフ]]は立方体グラフである。]]

[[Image:Biclique K 3 3.svg|thumb|right|180px|[[完全2部グラフ]] <math>K_{3,3}</math> は2部立方体グラフの一例である。]]

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

== 対称性 ==
1932年、{{仮リンク|ロナルド・フォスター|en|R. M. Foster}}は、[[対称グラフ|フォスター調査]]（Foster census）の皮切りとして、立方体[[対称グラフ]]の例の集計をはじめた<ref name="Ref_Foster">{{Citation|first1=R. M.|last1=Foster|title=Geometrical Circuits of Electrical Networks|journal=[[:en:Transactions of the American Institute of Electrical Engineers|Transactions of the American Institute of Electrical Engineers]]|volume=51|pages=309–317|year=1932|doi=10.1109/T-AIEE.1932.5056068|issue=2}}.</ref>。[[設備グラフ]]や[[ピーターセングラフ]]、[[ヒーウッドグラフ]]、{{仮リンク|メビウス-カントールグラフ|en|Möbius–Kantor graph}}、{{仮リンク|パップスグラフ|en|Pappus graph}}、{{仮リンク|デザルググラフ|en|Desargues graph}}、{{仮リンク|ナウルグラフ|en|Nauru graph}}、{{仮リンク|コクセターグラフ|en|Coxeter graph}}、{{仮リンク|トゥッテ-コクセターグラフ|en|Tutte–Coxeter graph}}、{{仮リンク|ディックグラフ|en|Dyck graph}}、{{仮リンク|フォスターグラフ|en|Foster graph}}、{{仮リンク|ビッグス-スミスグラフ|en|Biggs-Smith graph}}など、多くの有名なグラフは立方体かつ対称的であった。

{{仮リンク|ウィリアム・トーマス・タット|en|W. T. Tutte}}は、長さ ''s'' の各二つの有向路が、ちょうど一回のグラフの対称性によって互いに写される時、そのような ''s'' の最小のものによって対称立方体グラフを分類した。彼は、そのような ''s'' は多くとも 5 であることを示し、''s'' が 1 から 5 であるような各グラフの例を提示した<ref>{{Citation
 | doi = 10.4153/CJM-1959-057-2
 | last = Tutte | first = W. T.
 | journal = Canad. J. Math
 | pages = 621–624
 | title = On the symmetry of cubic graphs
 | url = http://cms.math.ca/cjm/v11/p621
 | volume = 11
 | year = 1959}}.</ref>。

[[半対称グラフ|半対称]]立方体グラフには、{{仮リンク|グレイグラフ|en|Gray graph}}（最小の半対称立方体グラフ）や{{仮リンク|リュブリャナグラフ|en|Ljubljana graph}}、{{仮リンク|トゥッテ12-ケージ|en|Tutte 12-cage}}が含まれる。

{{仮リンク|フルフトグラフ|en|Frucht graph}}は、対称性を持たない最小の立方体グラフの二つの内の一つである。それは、単一の{{仮リンク|グラフ自己同型|en|graph automorphism}}として、恒等自己同型のみを備える。

== 彩色と独立集合 ==
{{仮リンク|ブルックスの定理 (グラフ理論)|label=グラフ理論|en|Brooks' theorem}}によると、[[完全グラフ]] ''K''<sub>4</sub> 以外のすべての立方体グラフは、多くとも 3色によって[[グラフ彩色|彩色]]される。したがって、''K''<sub>4</sub> 以外のすべての立方体グラフは、少なくとも ''n''/3 個の頂点の[[独立集合]]を持つことになる。ここで ''n'' はそのグラフ内の頂点の数とする：例えば、3-彩色における最大の色の類は、少なくともこのくらい多くの頂点を含む。

{{仮リンク|ビジングの定理|en|Vizing's theorem}}によると、すべての立方体グラフは、その辺彩色のために 3色か 4色を必要とする。3-辺彩色はテイト彩色として知られ、そのグラフの辺を三つの[[マッチング (グラフ理論)|完全マッチング]]へと区分する。{{仮リンク|ケーニヒの定理 (グラフ理論)|label=ケーニヒの線彩色定理|en|König's theorem (graph theory)}}によれば、すべての2部立方体グラフにはテイト彩色が存在する。

テイト彩色が存在しない、橋のない立方体グラフは{{仮リンク|スナーク (グラフ理論)|label=スナーク|en|Snark (graph theory)}}として知られる。[[ピーターセングラフ]]や、{{仮リンク|ティーツェのグラフ|en|Tietze's graph}}、{{仮リンク|ブラヌサスナーク|en|Blanuša snarks}}、{{仮リンク|フラワースナーク|en|flower snark}}、{{仮リンク|ダブルスタースナーク|en|double-star snark}}、{{仮リンク|スゼッケルスナーク|en|Szekeres snark}}、{{仮リンク|ワトキンススナーク|en|Watkins snark}}などが、これに該当する。スナークは無数に存在する<ref>{{citation
 | doi = 10.2307/2319844
 | last = Isaacs | first = R.
 | issue = 3
 | journal = [[:en:American Mathematical Monthly|American Mathematical Monthly]]
 | pages = 221–239
 | title = Infinite families of nontrivial trivalent graphs which are not Tait colorable
 | jstor = 2319844
 | volume = 82
 | year = 1975}}.</ref>。

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

二次元平面上の任意の{{仮リンク|グラフ埋め込み|en|graph embedding}}は、graph-encoded map として知られる立方体グラフの構造によって表現される。この構造において、立方体グラフの各頂点は埋め込みの{{仮リンク|旗 (幾何学)|label=旗|en|Flag (geometry)}}、すなわち、互いに付帯した頂点、辺および平面の表面からなる組を表す。各旗の三つの隣（neighbor）は、その組の内のどれか一つを変更し、他の二つはそのままにしたものとして得られるような三つの旗である<ref>{{citation
 | last1 = Bonnington | first1 = C. Paul
 | last2 = Little | first2 = Charles H. C.
 | publisher = Springer-Verlag
 | title = The Foundations of Topological Graph Theory
 | year = 1995}}.</ref>。

== ハミルトン性 ==
立方体グラフの[[ハミルトン閉路|ハミルトン性]]については多くの研究結果がある。1980年に[[ピーター・ガスリー・テイト|P.G. テイト]]は、すべての立方[[多面体グラフ]]は[[ハミルトン閉路]]を持つと予想した。この[[テイトの予想]]に対する反例は、{{仮リンク|ウィリアム・トーマス・トゥッテ|en|William Thomas Tutte}}の 46-頂点[[タットグラフ]]によって、1946年に挙げられた。そのトゥッテは 1971年、すべての 2部立方体グラフはハミルトンであると予想した。しかし、ジョセフ・ホートンは 96-頂点{{仮リンク|ホートングラフ|en|Horton graph}}をこの反例として挙げた<ref name="Ref_a">Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.</ref>。その後、マーク・エリンガムはさらに二つの反例を挙げた：{{仮リンク|エリンガム-ホートングラフ|en|Ellingham-Horton graph}}である<ref name="Ref_b">Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.</ref><ref name="Ref_c">{{Citation|last1=Ellingham|first1=M. N.|last2=Horton|first2=J. D.|title= Non-Hamiltonian 3-connected cubic bipartite graphs|journal=[[:en:Journal of Combinatorial Theory|Journal of Combinatorial Theory]]|series=Series B| volume=34| pages=350–353| year=1983| doi=10.1016/0095-8956(83)90046-1|issue=3}}.</ref>。未だに解決のなされていない、テイトとトゥッテの予想の組合せである{{仮リンク|バーネットの予想|en|Barnette's conjecture}}では、すべての二部立方多面体グラフはハミルトンである、としている。立方体グラフがハミルトンであるとき、{{仮リンク|LCF表記|en|LCF notation}}によってそれを正確に表現することが出来る。

すべての ''n''-頂点立方体グラフの中から{{仮リンク|ランダムグラフ|label=一様にランダムに|en|random graph}}一つの立方体グラフが選ばれるとき、それはハミルトンであることが非常に多い： ''n'' が無限大へと向かう極限において、''n''-頂点立方体グラフがハミルトンである割合は 1 となる<ref>{{citation
 | last1 = Robinson | first1 = R.W.
 | last2 = Wormald | first2 = N.C.
 | doi = 10.1002/rsa.3240050209
 | issue = 2
 | journal = Random Structures and Algorithms
 | pages = 363–374
 | title = Almost all regular graphs are Hamiltonian
 | volume = 5
 | year = 1994}}.</ref>。

{{仮リンク|デビッド・エプシュタイン|en|David Eppstein}}は、すべての ''n''-頂点立方体グラフは多くとも 2<sup>''n''/3</sup> 個（およそ 1.260<sup>''n''</sup> 個）の異なるハミルトン閉路を含むと予想し、そのような多くの閉路を含む立方体グラフの例を提供した<ref>{{citation
 | last = Eppstein | first = David | authorlink = :en:David Eppstein
 | arxiv = cs.DS/0302030 | issue = 1
 | journal = [[:en:Journal of Graph Algorithms and Applications|Journal of Graph Algorithms and Applications]]
 | pages = 61–81
 | title = The traveling salesman problem for cubic graphs
 | url = http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf
 | volume = 11
 | year = 2007}}.</ref>。異なるハミルトン閉路の数について証明された最良の上界は、1.276<sup>''n''</sup> である<ref>{{citation
 | last = Gebauer | first = H.
 | contribution = On the number of Hamilton cycles in bounded degree graphs
 | title = Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08)
 | url = http://zeno.siam.org/proceedings/analco/2008/anl08_023gebauerh.pdf
 | year = 2008}}.</ref>。

== 他の性質 ==
任意の ''n''-頂点立方体グラフの{{仮リンク|パス幅|en|pathwidth}}は、最大でも ''n''/6 である。しかし、立方体グラフのパス幅の知られている下界のうち最良のものは、より小さく、0.082''n'' である<ref name="fh06">{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Høie | first2 = Kjartan
 | doi = 10.1016/j.ipl.2005.10.012
 | issue = 5
 | journal = [[:en:Information Processing Letters|Information Processing Letters]]
 | pages = 191–196
 | title = Pathwidth of cubic graphs and exact algorithms
 | volume = 97
 | year = 2006}}.</ref>。

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

[[ジュリウス・ピーターセン]]の定理は、{{仮リンク|橋 (グラフ理論)|label=橋|en|bridge (graph theory)}}の無いすべての立方体グラフには[[マッチング (グラフ理論)|完全マッチング]]が存在する、というものである<ref name="Pet1891">{{Citation
 | last1 = Petersen | first1 = Julius Peter Christian
 | issue = 15
 | journal = [[:en:Acta Mathematica|Acta Mathematica]]
 | pages = 193–220
 | title = Die Theorie der regulären Graphs (The theory of regular graphs)
 | doi=10.1007/BF02392606
 | year = 1891
 | volume = 15}}.</ref>。

[[ラースロー・ロヴァース|ロヴァース]]とプラマーは、すべての橋の無い立方体グラフには、指数関数的な数の完全マッチングが存在すると予想した。この予想は近年、すべての橋の無い ''n'' 頂点立方体グラフには少なくとも 2<sup>n/3656</sup> 個の完全マッチングが存在する、という結果とともに証明された<ref name="EKKKN11">{{citation
 | last1 = Esperer | first1 = Louis
 | last2 = Kardoš | first2 = František
 | last3 = King | first3 = Andrew D.
 | last4 = Král | first4 = Daniel
 | last5 = Norine | first5 = Serguei
 | doi = 10.1016/j.aim.2011.03.015
 | issue = 4
 | journal = [[:en:Advances in Mathematics|Advances in Mathematics]]
 | pages = 1646–1664
 | title = Exponentially many perfect matchings in cubic graphs
 | year = 2011
 | volume = 227}}.</ref>。

== アルゴリズムと計算量 ==
何人かの研究者は、立方体グラフに限定された[[指数関数時間]]アルゴリズムの計算量についての研究を行っている。例えば、グラフの{{仮リンク|パス分解|en|path decomposition}}に[[動的計画法]]を適用することにより、Fomin と Høie は時間 O(2<sup>''n''/6&nbsp;+&nbsp;o(n)</sup>) 内に彼らの[[独立集合|最大独立集合]]を見つける方法を示した<ref name="fh06"/>。[[巡回セールスマン問題]]は、立方体グラフによって時間 O(1.251<sup>''n''</sup>) 内に解くことが出来る<ref name="Iwama2007">{{citation|first1=Kazuo|last1=Iwama|first2=Takuya|last2=Nakashima|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|title=Computing and Combinatorics|contribution=An Improved Exact Algorithm for Cubic Graph TSP|year=2007|doi=10.1007/978-3-540-73545-8_13|volume=4598|pages=108–117|isbn=978-3-540-73544-1}}.</ref>。

いくつかの重要なグラフ最適化問題は[[APX困難]]である。すなわち、それらには[[近似アルゴリズム|近似率]]がある定数で評価されるような[[近似アルゴリズム]]が存在するが、（[[P=NP]]でない限り）近似率が 1 へと向かうような[[多項式時間近似スキーム]]は存在しない。そのような問題には、最小の[[頂点被覆]]を見つける問題や[[独立集合|最大独立集合]]、最小[[支配集合問題|支配集合]]、[[カット (グラフ理論)|最大カット]]を見つける問題などが含まれる<ref>{{citation
 | last1 = Alimonti | first1 = Paola
 | last2 = Kann | first2 = Viggo
 | doi = 10.1016/S0304-3975(98)00158-3
 | issue = 1–2
 | journal = [[:en:Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 123–134
 | title = Some APX-completeness results for cubic graphs
 | volume = 237
 | year = 2000}}.</ref>。立方体グラフの{{仮リンク|交差数 (グラフ理論)|label=交叉数|en|Crossing number (graph theory)}}（任意の{{仮リンク|グラフ描画|en|graph drawing}}において交叉する辺の最小数）もまた、[[NP困難]]であるが、近似出来ることもある<ref name="Hlinny2006">{{citation|first=Petr|last=Hliněný|title=Crossing number is hard for cubic graphs|journal=[[:en:Journal of Combinatorial Theory|Journal of Combinatorial Theory]]|series=Series B|volume=96|issue=4|pages=455–471|year=2006|doi=10.1016/j.jctb.2005.09.009}}.</ref>。

== 出典 ==
{{脚注ヘルプ}}
{{reflist}}

== 関連項目 ==
* {{仮リンク|単純立方体グラフの一覧|en|Table of simple cubic graphs}}

== 外部リンク ==
*{{mathworld|urlname=BicubicGraph|title=Bicubic Graph}}
*{{mathworld|urlname=CubicGraph|title=Cubic Graph}}

{{DEFAULTSORT:りつほうたいくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]