Двойственный граф планарного графа

Эта статья находится в разработке!

Определение:

Граф G* называется двойственным к планарному графу G, если: Вершины G* соответствуют граням G Между двумя вершинами в G* есть ребро тогда и только тогда, когда соответствующие грани в G имеют общее ребро

Граф (белые вершины) и двойственный ему (полосатые вершины)

«…Для данного плоского графа G его двойственный граф G* строится следующим образом: поместим в каждую область G (включая внешнюю) по одной вершине графа G* и, если две области имеют общее ребро x, соединим помещенные в них вершины ребром x*, пересекающим только x. В результате всегда получится плоский псевдограф. Ясно, что G* имеет петлю тогда и только тогда, когда в G есть концевая вершина; G* имеет кратные рёбра тогда и только тогда, когда две области графа G содержат по крайней мере два общих ребра. Таким образом, двусвязный плоский граф имеет всегда в качестве двойственного или граф или мультиграф, в то время как двойственный граф трёхсвязного плоского графа всегда представляет собой граф. Другими примерами двойственных графов являются платоновы графы: тетраэдр — самодвойственный граф, куб и октаэдр — двойственные, так же как додекаэдр и икосаэдр…».

Свойства

• На самом деле, двойственный граф — мультиграф, поскольку в нём могут быть петли и кратные рёбра
• Если G* — двойственный к двусвязному графу G, то G — двойственный к G*