- Двойственный граф
-
Двойственный граф к планарному графу — это граф, в котором вершины соответствуют граням графа ; эти вершины соединены ребром, только если соответствующие им грани графа имеют общее ребро. Например, двойственны друг к другу графы куба и октаэдра.
Двойственный граф является псевдографом: в нём могут быть петли и кратные рёбра.
В зависимости от укладки, к одному и тому же графу могут существовать несколько двойственных.
Самодвойственным называют граф, который изоморфен своему двойственному графу. Например, самодвойственен граф тетраэдра.
Ссылки
- Weisstein, Eric W. Dual graph (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. Self-dual graph (англ.) на сайте Wolfram MathWorld.
Категории:- Теория графов
- Теории двойственности
Wikimedia Foundation. 2010.