3彩色問題

ウィキペディア小見出し辞書

3彩色問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/25 16:14 UTC 版)

「四色定理」の記事における「3彩色問題」の解説

「与えられた地図Gに対し、Gを3色で塗り分けできるかどうかを決定せよ」という問題を3彩色問題という。四色問題のときと同じく隣り合う土地を同じ色で塗ってはならない。 3彩色問題はNP完全問題の一つであることが知られている。