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

Материал из WEGA
Версия от 12:10, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Двойственный граф''' (''Dual graph'') - для данного плоского графа (геометрически)...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

Литература

[Лекции]