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

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


==Литература==
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Навигация