グラフ彩色

ウィキペディア

グラフ彩色

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/17 10:14 UTC 版)

グラフ彩色（グラフさいしょく、英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色（ちょうてんさいしょく）という。同様に辺彩色（へんさいしょく）は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色（めんさいしょく）は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。