Изменения

Перейти к: навигация, поиск

Произвольно вычерчиваемые из заданной вершины графы

1134 байта добавлено, 04:32, 17 декабря 2011
Нет описания правки
<tex>\Leftarrow</tex> Пусть в графе <tex>G</tex> существует цикл <tex>C</tex>, не содержащий вершину <tex>v</tex>. Рассмотрим подграф <tex>G_1</tex>, полученный удалением из <tex>G</tex> всех рёбер цикла <tex>C</tex>. Пусть <tex>H</tex> — компонента связности подграфа <tex>G_1</tex>, содержащая вершину <tex>v</tex>. Легко понять, что <tex>H</tex> — эйлеров граф. Обозначим через <tex>P</tex> эйлеров цикл подграфа. Можно считать, что началом и концом цикла <tex>P</tex> является вершина <tex>v</tex>. Поскольку <tex>v</tex> не принадлежит циклу <tex>C</tex>, цепь <tex>P</tex> нельзя продолжить до эйлерового цикла графа <tex>G</tex>.
}}
 
== Строение ==
Опираясь на теорему несложно описать строение всех графов, произвольно вычерчиваемых из вершины <tex>v</tex>. <br>
Возьмем произвольный лес <tex>H</tex>, не содержащий вершину <tex>v</tex>. Каждую вершину нечетной степени соединим некоторым нечетным числом кратных ребер с <tex>v</tex>, а каждую вершину четной степени <tex>--</tex> четным числом кратных ребер с <tex>v</tex> (не исключая 0), причем каждую изолированную вершину обязательно соединим с <tex>v</tex>.<br>
Полученный граф <tex>G</tex>:
* Связен;
* Имеет только вершины четной степени;
* Является произвольно вычерчиваемым из <tex>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам.
 
==Источники==
43
правки

Навигация