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

Двойственный граф (Dual graph) - для данного плоского графа (геометрически) двойственный граф есть снова плоский граф, вершины которого суть грани исходного графа и две вершины смежны, если соответствующие грани имеют общее ребро. (Абстрактно) двойственный граф --- это граф, у которого подмножество ребер образует простой цикл тогда и только тогда, когда соответствующее ему (при некоторой биекции) подмножество ребер исходного графа образует простой разрез и наоборот. Справедливо утверждение: граф, геометрически двойственный плоскому графу, является абстрактно двойственным ему.

Литература

[Лекции]