2011-08-25から1日間の記事一覧

グラフ彩色とパス表現

無向グラフについて、k色のうちいずれかをそれぞれの頂点に割り当てたとき、全ての辺の両端が異なる色ならばそのグラフをk-彩色可能といいます。平面埋め込み可能なグラフは全て4-彩色可能というのが、有名な四色定理です。 さて各頂点がある埋込みの中の位…