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