平面グラフの問いです。

質問

平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。
その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。
つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。

回答No.1

sunflower-san · ベストアンサー

ご質問の変換の定義から明らかにYESです。
元の平面グラフにおいて頂点A,Bが辺Lで結ばれているならば、変換後には凹凸多角形の境界線L*になるのでA, Bの変換後の凹凸多角形A*, B*は境界を共有して接していますよね。
また逆に、変換後の凹凸多角形X, Yが境界Hを共有して接しているならば、X, Yに変換される前の対応する頂点X*, Y*はHに変換される前の辺H*で結ばれていますよね。
つまり平面グラフ頂点の彩色問題は、地図の色分け問題に言い換えることができます。

ところで、ご質問の変換によって出来た凹凸多角形たちは、凹凸多角形の頂点や境界をそれぞれグラフの頂点や辺と考えれば、平面グラフとみなすことができます。

平面グラフGについて
(頂点、辺が与えられた時)
Gの「面」を、辺で囲まれた領域と定義することにします。(したがって一番外側の無限に広い領域も一つの面とみなします)

この時、
面Aを頂点A*に、
面A,Bの共有する境界の各辺Lを頂点A*, B*を結ぶ辺L*に、
置き換えて得られる平面グラフG*をGの双対グラフと言います。
G*の双対をとるとGに戻り、

Gの頂点とG*の面,
Gの辺とG*の辺,
Gの面とG*の頂点,

がそれぞれ一対一に対応しているのがわかると思います。

双対グラフを考えることで
Gの面に関する問題は、G*の頂点に関する問題に
Gの辺に関する問題は、G*の辺に関する問題に
Gの頂点に関する問題は、G*の面に関する問題に
言い換えることができます。

お礼

御回答を誠に有難う御座いました。