Двойственный граф: различия между версиями

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

ребер образует [[простой цикл]] тогда и только тогда, когда соответствующее ему (при некоторой биекции) подмножество ребер исходного графа образует [[простой разрез]] и наоборот. Справедливо

утверждение: граф, [[геометрически двойственный граф|геометрически двойственный]] плоскому графу, является абстрактно двойственным  ему.