ビジングの定理
グラフの辺の色付けについて

それぞれクラス1とクラス2のグラフ

グラフ理論において、ヴィジングの定理は、すべての単純な無向グラフは、グラフの最大次数Δより最大で1大きい色数で辺を彩色できると述べている。少なくともΔ色は常に必要なので、無向グラフはΔ色で十分な「クラス1」グラフとΔ + 1色必要な「クラス2」グラフの2つのクラスに分けられる。ヴィジングの定理のより一般的なバージョンは、ループのないすべての無向多重グラフは最大でΔ+µ色で彩色できると述べている。ここで、 µは多重グラフの多重度である。 [1]この定理は、1964年に発表したVadim G. Vizingにちなんで名付けられた。

発見

ソビエトの数学者ヴァディム・G・ヴィジングによって発見された定理は、 1964年にヴィジングがノボシビルスクで研究していたときに発表され[2] [3]、ヴィジングの定理として知られるようになりました。インドの数学者R.P.グプタは、博士号取得課程（1965～1967年）中に、この定理を独自に発見しました[4] [5]

例

Δ = 1のとき、グラフG自体はマッチンググラフでなければならず、2つの辺が隣接しておらず、その辺彩色数は1です。つまり、Δ( G ) = 1であるすべてのグラフはクラス1です

Δ = 2の場合、グラフG はパスとサイクルの互いに素な和集合でなければならない。すべてのサイクルが偶数であれば、各サイクルの周囲で2色を交互に塗り分けることで2辺彩色できる。しかし、少なくとも1つの奇数サイクルが存在する場合、2辺彩色は不可能である。つまり、Δ = 2のグラフがクラス1に属するのは、それが二部グラフである場合のみである。

証明

この証明はDiestel (2000)に着想を得たものです。[6]

G  = ( V ,  E )を単純無向グラフとします。辺の数mについて帰納的に説明します。グラフが空であれば、定理は自明に成り立ちます。m  > 0とし、すべてのG  −  xy （xy  ∈  E）に対して 適切な(Δ+1)辺彩色が存在すると仮定します

すべてのy  ∈ N( x )に対してc ( xy ) ≠ α であるとき、 x  ∈  Vにおいて適切な(Δ+1)辺彩色cに関して色α ∈ {1,...,Δ+1 } が欠落しているといえます。また、xからのα/βパスは、 xからα色の辺で始まり、辺の色が交互に変わる（2番目の辺は色β、3番目の辺は色αなど）唯一の最大パスを表し、その長さは0になる場合があります。cがGの適切な(Δ+1)辺彩色である場合、すべての頂点はcに関して欠落した色を持つことに注意してください。

Gの適切な(Δ+1)辺彩色が存在しないと仮定する。これは以下の命題と等価である。

(1) xy  ∈  EとcをG  −  xyの任意の固有(Δ+1)辺彩色とし、cに関してxからαが欠落し、yからβ が欠落しているとします。このとき、yからのα/βパスはxで終わります。

これは等価です。なぜなら、(1)が成り立たない場合、α/βパス上の色αとβを入れ替え、 xyの色をαに設定することで、cからGの適切な(Δ+1)辺彩色を作成できるからです。逆に、適切な(Δ+1)辺彩色が存在する場合、 xyを削除して彩色を制限すると、(1)も成り立ちません。

ここで、xy 0  ∈  E、c 0をG  −  xy 0の適切な(Δ+1)辺彩色とし、αはc 0に関してxに欠落しているとします。y 0 , ..., y k を、すべての0 <  i  ≤  kに対してc 0 ( xy i )がy i −1に関してc 0に関して欠落するようなxの近傍の最大列と定義します。

色付けc 1 ,..., c kを次のように 定義する。

c i ( xy j )= c 0 ( xy j +1 ) （0 ≤  j  <  iのすべてについて）
c i ( xy i )は定義されていません。
それ以外の場合はc i ( e )= c 0 ( e )です。

このとき、c iはy 0 ,..., y kの定義により、G  −  xy iの適切な(Δ+1)辺彩色となる。また、 xにおける欠落色は、すべての0 ≤  i  ≤  kにおいてc iに関して同じであることに注意する。

y kにおけるc 0に関する欠落色をβとすると、0 ≤  i  ≤  kのいずれにおいても、 y kにおけるc iに関する欠落色はβとなる。β は x において欠落してはならないことに注意されたい。そうでなければc k を容易に拡張することができ、したがって、すべてのc jにおいて、色βの辺はxに接続される。kの最大値から、 1 ≤  i  <  kが存在し、 c 0 ( xy i ) = βとなる。c 1 , ..., c kの定義から、以下が成り立つ。

c 0 ( xy i ) =  c i −1 ( xy i ) =  c k ( xy i −1 ) = β

P をy kからc kに関するα/βパスとします。(1) より、P はxで終わらなければなりません。しかし、 αはxに欠けているので、色βのエッジで終わらなければなりません。したがって、 Pの最後のエッジはy i −1 xです。ここで、P'をy i −1からc i −1に関するα/βパスとします。P'は一意に決定され、 Pの内側のエッジはc 0 ,..., c kで変更されないので、パスP'はPと同じエッジを逆の順序で使用してy kを訪れます。 y kにつながるエッジは明らかに色αを持ちます。しかし、βはy kに欠けているので、P' はy kで終わります。これは上記 (1) と矛盾しています。

グラフの分類

いくつかの著者は、いくつかのグラフをクラス1またはクラス2に分類する追加条件を提示していますが、完全な分類は提供していません。例えば、グラフGの最大次数Δの頂点が独立集合を形成する場合、またはより一般的には、この頂点集合の誘導部分グラフがフォレストである場合、Gはクラス1でなければなりません。[7]

エルデシュとウィルソン (1977) は、ほぼすべてのグラフがクラス1であることを示した。つまり、すべてのn頂点グラフが等確率で出現するランダムグラフのエルデシュ・レーニモデルにおいて、この分布から抽出されたn頂点グラフがクラス1である確率をp ( n )とすると、 nが無限大に近づくにつれてp ( n )は極限で1に近づく。[8] p ( n )が1に収束する速度に関するより正確な限界については、Frieze et al. (1988) を参照のこと。[9]

グラフをクラス1とクラス2に分類する一般的な問題は、1981年にNP完全であることが示されました。[10]

平面グラフ

Vizing (1965) は、平面グラフの最大次数が8以上の場合、そのグラフはクラス1に属することを示しました。対照的に、彼は、最大次数が2から5の範囲であれば、クラス2の平面グラフが存在することを観察しました。次数2の場合、任意の奇数サイクルがそのようなグラフであり、次数3、4、5の場合、これらのグラフは、プラトン立体の1つの辺を隣接する2つの辺のパスに置き換えることで 構築できます

ヴィイジングの平面グラフ予想において、ヴィイジング（1965）は、最大次数が6または7である単純な平面グラフはすべてクラス1であると述べており、残りの可能性のある場合を解決した。一方、張（2000）とサンダース＆チャオ（2001）は、最大次数が7であるすべての平面グラフがクラス1であることを示して、ヴィイジングの平面グラフ予想を部分的に証明した。[11] [12] したがって、この予想で未解決のまま残っているのは、最大次数が6の場合のみである。この予想は、全彩色予想に影響を与える。

プラトン立体の細分によって構成されるクラス2の平面グラフは正則ではない。つまり、2次以上の頂点だけでなく、2次以上の頂点も持つ。平面グラフの頂点彩色に関する4色定理（Appel & Haken (1976) によって証明された）[13]は、すべての橋なし3次正則平面グラフがクラス1であるという命題と同値である。[14]

非平面上のグラフ

1969 年、ブランコ・グリュンバウムは、トーラスなどの任意の 2 次元有向多様体上に多面体埋め込みを持つすべての 3 正則グラフはクラス 1 でなければならないと予想しました。この文脈では、多面体埋め込みとは、埋め込みのすべての面が位相的にディスクであり、埋め込みの双対グラフが単純で、自己ループや多重隣接がないようなグラフ埋め込みです。正しい場合、これは 4 色定理の一般化になります。4 色定理は、球面上に多面体埋め込みを持つ 3 正則グラフはクラス 1 であるという命題と同等であると Tait によって示されました。しかし、Kochol (2009)は、高種数の有向曲面上に多面体埋め込みを持つスナークを見つけることで、この予想が誤りであることを示しました。[15]この構成に基づいて、彼はまた、多面体に埋め込まれたグラフがクラス 1 であるかどうかを判断することが NP 完全であることを示しました。[16]

アルゴリズム

一般的なクラス 1 またはクラス 2 への分類問題は NP 完全であるため、最適なエッジ彩色のための多項式時間アルゴリズムは期待できません。しかし、すでに Vizing による定理の最初の証明はアルゴリズム的であり、任意のグラフのエッジをΔ + 1色で彩色する多項式時間アルゴリズムを記述しています。ここでΔはグラフの最大次数です。つまり、このアルゴリズムはクラス 2 のグラフに最適な色数を使用し、すべてのグラフに必要な色よりも最大で 1 色多く使用します。つまり、色付けされていないグラフから開始し、色付けされたエッジの数を 1 つ増やすためにグラフの色付け方法を繰り返し見つけます。このようにして、このアルゴリズムはエッジを彩色しますが、このような色付けのたびに時間がかかり、全体の時間計算量は になります。 m {\displaystyle m} O （ n ） {\displaystyle O(n)} O （ m n ） {\displaystyle O(mn)}

Misra & Gries (1992) は、Vizing のオリジナルの戦略と同じ戦略に従うアルゴリズムを説明しています。より具体的には、uv が部分的に色付けされたグラフ内の色付けされていない辺であるとします。Misra と Gries のアルゴリズムは、uの近傍に有向擬似フォレスト P (各頂点から最大で 1 つの出力辺しか出ないグラフ)を構築するものと解釈できます。 uの各近傍pについて、アルゴリズムはpに接続するどの辺にも使用されていない色cを見つけ、辺uq が色cを持つ頂点q (存在する場合)を見つけ、pq をPへの辺として追加します。次の 2 つのケースがあります。

  • このようにして構築された擬似森P に、 vからPに出ていく辺を持たない頂点wへの経路が含まれる場合、 uとw の両方で利用可能な色cが存在する。辺uw を色cで再着色すると、残りの辺の色をこの経路に沿って1ステップシフトすることができる。経路上の各頂点pについて、辺up は経路上のpの後継頂点で以前に使用されていた色を取得する。これにより、辺uvを含む新しい着色が得られる。[17]
  • 一方、擬似森Pにおいてvから始まるパスがサイクルにつながる場合、wをパスがサイクルに合流するuの隣接ノードとし、 cを辺uwの色とし、dを頂点uのどの辺にも使われていない色とする。ケンペ連鎖において色cとdを入れ替えると、サイクルが破壊されるか、パスがサイクルに合流する辺が破壊され、前述のケースに戻る。[17]

各頂点で使用されている色と利用可能な色を追跡するための単純なデータ構造を用いることで、Pの構築とアルゴリズムの色付けステップはすべてO( n )の時間で実装できる。ここでnは入力グラフの頂点数である。これらのステップはm回繰り返す必要があり、繰り返しごとに色付けされた辺の数が1ずつ増加するため、合計時間はO( mn )となる。[17]

ガボウら（1985）は未発表の技術報告書で、Δ+1色による着色という同じ問題に対して、より高速な時間制限 を主張した。 [18]同じ制限は、アルジョマンディの1982年の論文にも記載されている[19]。 O （ m n 対数 ⁡ n ） {\displaystyle O(m{\sqrt {n}}\log n)}

2024年には、いくつかの改良アルゴリズムが開発され、最終的には時間計算量を持つ確率的準線形時間アルゴリズムが完成しました。[20] [21] O （ m 対数 ⁡ Δ ） ＝ O 〜 （ m ） {\displaystyle O(m\log \Delta)={\widetilde {O}}(m)}

歴史

Gutin & Toft (2000)とSoifer (2008)の両方において、Vizingは、多重グラフは最大で(3/2)Δ色で彩色できることを示すShannon (1949) [22]の定理に触発されて研究を行ったと述べています。 [23] [24] Vizingの定理は現在、多くのグラフ理論の教科書の標準的な内容となっていますが、Vizingは当初その結果を発表するのに苦労し、その論文は無名のジャーナルであるDiskret. Analizに掲載されました。[25]

参照

参考文献

  1. ^ ベルジュ、クロード、フルニエ、ジャン・クロード (1991)、「ビイジングの定理の一般化のための簡潔な証明」、Journal of Graph Theory、15 (3): 333– 336、doi :10.1002/jgt.3190150309
  2. ^ Vizing, VG (1964)、「 pグラフの彩度クラスの推定について」、Diskret. Analiz.、3 : 25–30、MR  0180505
  3. ^ Vizing, VG ( 1965)、「与えられた彩色クラスを持つ臨界グラフ」、Metody Diskret. Analiz. (ロシア語)、5 : 9–17
  4. ^ スティビッツ、マイケル; シャイデ、ディエゴ; トフト、ビャルネ; ファヴルホルト、レーネ・M. (2012)、「グラフエッジカラーリング：ビイジングの定理とゴールドバーグの予想」、Wileyシリーズ、離散数学と最適化、John Wiley＆Sons、Inc.、ホーボーケン、ニュージャージー州、p. xii、ISBN 978-1-118-09137-1、MR  2975974
  5. ^ Toft, B; Wilson, R (2021年3月11日)、「エッジカラーリングの簡潔な歴史 – 個人的な回想を添えて」(PDF)、Discrete Mathematics Letters、6 : 38–46、doi : 10.47443/dml.2021.s105
  6. ^ Diestel、Reinhard ( 2000)、グラフ理論(PDF)、ベルリン、ニューヨーク: Springer-Verlag、pp.  103–104
  7. ^ フルニエ、ジャン＝クロード (1973)、「Colorations des arêtes d'ungraphe」、Cahiers du Centre d'Études de Recherche Opérationnelle、15 : 311–314、MR  0349458
  8. ^ エルデシュ, ポール;ウィルソン, ロビン J. (1977)、「ほとんどすべてのグラフの彩色指数に関する注記」(PDF)、Journal of Combinatorial Theory、シリーズB、23 ( 2–3 ): 255– 257、doi : 10.1016/0095-8956(77)90039-9
  9. ^ フリーズ、アラン・M. ; ジャクソン、B. ; マクダーミッド、CJH ;リード、B. (1988)、「エッジカラーリングランダムグラフ」、Journal of Combinatorial Theory、シリーズB、45 (2): 135– 149、doi : 10.1016/0095-8956(88)90065-2、MR  0961145
  10. ^ Holyer, Ian (1981)、「エッジカラーリングのNP完全性」、SIAM Journal on Computing、10 (4): 718– 720、doi :10.1137/0210055、MR  0635430
  11. ^ 張立民 (2000)、「最大次数7の平面グラフはすべてクラス1である」、グラフと組合せ論、16 (4): 467– 495、doi :10.1007/s003730070009、S2CID  10945647
  12. ^ サンダース、ダニエル・P. ; 趙、ユエ (2001)、「最大次数7の平面グラフはクラスIである」、組合せ理論ジャーナル、シリーズB、83 (2): 201– 212、doi : 10.1006/jctb.2001.2047
  13. ^ Appel, K. ; Haken, W. (1976)、「すべての平面写像は4色可能である」アメリカ数学会誌、82 (5): 711– 712、doi : 10.1090/S0002-9904-1976-14122-5、MR  0424602
  14. ^ Tait, PG (1880)、「地図の色彩に関する考察」、Proc. R. Soc. Edinburgh、10 : 729、doi :10.1017/S0370164600044643
  15. ^ ココール、マーティン (2009)、「有向面におけるスナークの多面体埋め込み」、アメリカ数学会誌、第137巻、 1613～ 1619頁 
  16. ^ Kochol, Martin (2010)、「有向面への多面体埋め込みを持つ立方グラフのクラスにおける3辺彩色の計算量」、離散応用数学、158 (16): 1856– 1860、doi : 10.1016/j.dam.2010.06.019、MR  2679785
  17. ^ abc Misra, J.; Gries, David (1992)、「Vizingの定理の構成的証明」、Information Processing Letters、41 (3): 131– 133、doi :10.1016/0020-0190(92)90041-S
  18. ^ Gabow, Harold N. ; Nishizeki, Takao ; Kariv, Oded ; Leven, Daniel ; Terada, Osamu (1985) 「グラフの辺彩色アルゴリズム」、技術報告書 TRECIS-8501、東北大学
  19. ^ Arjomandi, Eshrat (1982年5月)、「グラフの辺をΔ+1色で着色するための効率的なアルゴリズム」、INFOR: 情報システムとオペレーションズ・リサーチ、20 (2): 82– 101、doi :10.1080/03155986.1982.11731850、ISSN  0315-5986
  20. ^ Assadi, Sepehr; Behnezhad, Soheil; Bhattacharya, Sayan; Costa, Martín; Solomon, Shay; Zhang, Tianyi (2025)「近線形時間におけるVizingの定理」、Koucký, Michal; Bansal, Nikhil (編)、Proceedings of the 57th Annual ACM Symposium on Theory of Computing、STOC 2025、プラハ、チェコ共和国、2025年6月23～27日、Association for Computing Machinery、pp.  24～ 35、arXiv : 2410.05240、doi : 10.1145/3717823.3718265
  21. ^ Nadis, Steve (2025-05-12)「The Fastest Way Yet to Color Graphs」、Quanta Magazine 、2025年5月17日閲覧。
  22. ^ シャノン、クロード・E. (1949)、「ネットワークの線の色付けに関する定理」、J. Math. Physics、28 ( 1–4 ): 148– 151、doi :10.1002/sapm1949281148、MR  0030203
  23. ^ Gutin, Gregory; Toft, Bjarne (2000年12月)、「Vadim G. Vizing 氏へのインタビュー」(PDF)、欧州数学会ニュースレター、38 : 22–23
  24. ^ ソイファー、アレクサンダー（2008年）、数学ぬりえブック、シュプリンガー・フェアラーク、pp.  136– 137、ISBN 978-0-387-74640-1
  25. ^ この雑誌の正式名称はAkademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretny˘ı Analiz. Sbornik Trudovでした。1980年にMetody Diskretnogo Analiza （Gutin & Toft (2000) で与えられた名称）に改名され、1991年に廃刊となりました [1]
「https://en.wikipedia.org/w/index.php?title=Vizing%27s_theorem&oldid=1320475345」から取得