двойственный граф

Двойственный граф к планарному графу — это граф, в котором вершины соответствуют граням графа ; две вершины соединены ребром если и только если соответствующие им грани графа имеют общее ребро. Например, двойственны друг к другу графы куба и октаэдра. Термин двойственный используется ввиду того, что это свойство симметрично — если H двойственен G, то G двойственен H (при условии, что G связен). То же самое понятие можно использовать для вложения графов в многообразия.Понятие двойственности графов отличается от рёберно-вершинной двойственности (рёберный граф) графа и эти два понятия не следует путать.