組合せとグラフの理論(塩田)第10回 (5) 双対グラフの使いどころ

前へ / 戻る / 次へ $\newcommand{\as}{^{\ast}}$

双対グラフの使いどころ

 双対グラフは、プラトングラフの例のように理論的に興味深いという他に、例えば次のような応用を持ちます。
Ex.9 第1回で紹介した四色問題は面を塗り分ける問題でした。 面を塗り分けることはそのままでは表現しにくいのですが、 双対グラフの頂点を塗り分ける(点彩色と言います)ことに言い換えると処理し易くなります。
Ex.10 カットセットはコンピュータネットワークの強度(辺連結度)にかかわる重要な概念ですが、 扱いにくいものです。 もしネットワークが平面的であれば、双対グラフの閉路に読み替えられて、 第7回に扱った閉路部分空間で制御することが可能となります。