xanxys https://blog.hatena.ne.jp/xanxys/ ⊥=⊥ https://xanxys.hatenablog.jp/ 無向グラフについて、k色のうちいずれかをそれぞれの頂点に割り当てたとき、全ての辺の両端が異なる色ならばそのグラフをk-彩色可能といいます。平面埋め込み可能なグラフは全て4-彩色可能というのが、有名な四色定理です。 さて各頂点がある埋込みの中の位置を表していると考えると、隣接する位置の色が異なる、つまり互いに区別できるという解釈ができます。しかし、図の左上の水色の頂点がふたつの桃色の近傍をもっているように、微小な領域での「向き」を一意に区別することはできません。そこで、それを可能にする彩色を考えてみると、次のように表現できます。 すべての頂点について、自身とその近傍の色が全て異なるk色でこの条件… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fxanxys.hatenablog.jp%2Fentry%2F20110825%2F1314267327" title="グラフ彩色とパス表現 - ⊥=⊥" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/x/xanxys/20110825/20110825171130.png Hatena Blog https://hatena.blog 2011-08-25 19:15:27 rich https://xanxys.hatenablog.jp/entry/20110825/1314267327 1.0 100%