線形時間5彩色アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/20 08:01 UTC 版)
「五色定理」の記事における「線形時間5彩色アルゴリズム」の解説
1996年、Robertson, Sanders, Seymour, Thomas は "Efficiently four-coloring planar graphs" の中で、マルチグラフ（英語版）に対する2次多項式時間4彩色アルゴリズムを記述し、同論文の中で彼らは単純平面グラフを線形時間で5色彩色するアルゴリズムについて手短に述べている。これは漸近最適（英語版）であり、また次に述べるウェルニッケの定理（Wernicke's Theorem）に基づく。 ウェルニッケの定理: グラフ G {\displaystyle G} は平面的で、空集合でなく、2辺で囲まれるような面を持たず、かつ頂点の次数の最小値は5であるとする。このとき G {\displaystyle G} には次数が5または6の頂点と隣接しているような次数5の頂点が存在する。 アルゴリズムは、グラフに対し次の2種類の操作を再帰的に用いることで彩色を行う。 次数が4以下である頂点を削除する（この頂点は隣接していた頂点が使っていない色で塗れる）。 次数が5で、かつ次数6以下の頂点と隣接しているような頂点を削除し、隣接していた5頂点の中から辺で結ばれていない2頂点を選び、1頂点に合併（merge）する（合併した2頂点は同じ色で、最初に削除した頂点は隣接していた頂点が使っていない色で塗れる）。
※この「線形時間5彩色アルゴリズム」の解説は、「五色定理」の解説の一部です。
「線形時間5彩色アルゴリズム」を含む「五色定理」の記事については、「五色定理」の概要を参照ください。
- 線形時間5彩色アルゴリズムのページへのリンク
