頂点彩色
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
単にグラフの彩色(coloring)と言った場合、「頂点彩色」を意味することが多い。また、隣接する頂点が同じ色にならないよう彩色すること、すなわち最適彩色を意味する。隣接する頂点とは、同じ辺と接している頂点である。ある頂点から同じ頂点へ戻る辺（ループ）が存在する場合、頂点彩色問題は決して最適解を持たないので、以下ではループがないグラフのみを扱う。 頂点のラベルを「色」で表すのは地図の塗りわけに起源がある。「赤」や「青」といったラベルは色数が小さい場合のみ使われ、一般にはラベルとして整数 {1,2,3,...} を使う。 最大 k 色を使った彩色を k-彩色と言う。グラフ G の彩色に必要な最小の色数を彩色数(chromatic number)と呼び χ(G) で表す。例えば、n 個の頂点からなる完全グラフ（あらゆる頂点間に辺があるグラフ） K n {\displaystyle K_{n}} の彩色数は、 χ ( K n ) = n {\displaystyle \chi (K_{n})=n} である。k-彩色できるグラフをk-彩色可能(k-colorable)といい、そのkがそのグラフの彩色数であるとき、k-彩色的(k-chromatic)という。同じ色が割り当てられた頂点の集合を「色クラス」と呼び、色クラス同士は独立集合となっている。したがって、k-彩色することは、頂点集合を k 個の独立部分集合に分割するのと等価であり、k-部 (k-partite) グラフや k-彩色可能といった用語も同じ意味を持つ。
※この「頂点彩色」の解説は、「グラフ彩色」の解説の一部です。
「頂点彩色」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
- 頂点彩色のページへのリンク
