立方体グラフ

ピーターセングラフは立方体グラフである。

完全2部グラフ $K_{3,3}$ は2部立方体グラフの一例である。

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

対称性

1932年、テンプレート:仮リンクは、フォスター調査（Foster census）の皮切りとして、立方体対称グラフの例の集計をはじめた。設備グラフやピーターセングラフ、ヒーウッドグラフ、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンクなど、多くの有名なグラフは立方体かつ対称的であった。

テンプレート:仮リンクは、長さ s の各二つの有向路が、ちょうど一回のグラフの対称性によって互いに写される時、そのような s の最小のものによって対称立方体グラフを分類した。彼は、そのような s は多くとも 5 であることを示し、s が 1 から 5 であるような各グラフの例を提示した。

半対称立方体グラフには、テンプレート:仮リンク（最小の半対称立方体グラフ）やテンプレート:仮リンク、テンプレート:仮リンクが含まれる。

テンプレート:仮リンクは、対称性を持たない最小の立方体グラフの二つの内の一つである。それは、単一のテンプレート:仮リンクとして、恒等自己同型のみを備える。

彩色と独立集合

テンプレート:仮リンクによると、完全グラフ K₄ 以外のすべての立方体グラフは、多くとも 3色によって彩色される。したがって、K₄ 以外のすべての立方体グラフは、少なくとも n/3 個の頂点の独立集合を持つことになる。ここで n はそのグラフ内の頂点の数とする：例えば、3-彩色における最大の色の類は、少なくともこのくらい多くの頂点を含む。

テンプレート:仮リンクによると、すべての立方体グラフは、その辺彩色のために 3色か 4色を必要とする。3-辺彩色はテイト彩色として知られ、そのグラフの辺を三つの完全マッチングへと区分する。テンプレート:仮リンクによれば、すべての2部立方体グラフにはテイト彩色が存在する。

テイト彩色が存在しない、橋のない立方体グラフはテンプレート:仮リンクとして知られる。ピーターセングラフや、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンクなどが、これに該当する。スナークは無数に存在する。

位相と幾何

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

二次元平面上の任意のテンプレート:仮リンクは、graph-encoded map として知られる立方体グラフの構造によって表現される。この構造において、立方体グラフの各頂点は埋め込みのテンプレート:仮リンク、すなわち、互いに付帯した頂点、辺および平面の表面からなる組を表す。各旗の三つの隣（neighbor）は、その組の内のどれか一つを変更し、他の二つはそのままにしたものとして得られるような三つの旗である。

ハミルトン性

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

すべての n-頂点立方体グラフの中からテンプレート:仮リンク一つの立方体グラフが選ばれるとき、それはハミルトンであることが非常に多い： n が無限大へと向かう極限において、n-頂点立方体グラフがハミルトンである割合は 1 となる。

テンプレート:仮リンクは、すべての n-頂点立方体グラフは多くとも 2^n/3 個（およそ 1.260ⁿ 個）の異なるハミルトン閉路を含むと予想し、そのような多くの閉路を含む立方体グラフの例を提供した。異なるハミルトン閉路の数について証明された最良の上界は、1.276ⁿ である。

他の性質

任意の n-頂点立方体グラフのテンプレート:仮リンクは、最大でも n/6 である。しかし、立方体グラフのパス幅の知られている下界のうち最良のものは、より小さく、0.082n である。

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

ジュリウス・ピーターセンの定理は、テンプレート:仮リンクの無いすべての立方体グラフには完全マッチングが存在する、というものである。

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

アルゴリズムと計算量

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

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

関連項目

• テンプレート:仮リンク

外部リンク

• テンプレート:Mathworld
• テンプレート:Mathworld