43
правки
Изменения
Нет описания правки
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] <tex>G</tex> является произвольно вычерчиваемым из вершины <tex>v</tex> <tex>\Longleftrightarrow</tex> вершина <tex>v</tex> принадлежит всем циклам графа <tex>G</tex>.<br>
|proof=
}} {||<tex>\RightarrowLongrightarrow</tex> Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br>Рассмотрим <tex>G_1 = G/C</tex> (здесь и далее это означает удаление только ребер, не трогая вершины). Пусть <tex>HG_1</tex> компонента связности {{---}} эйлеров, так как при удалении цикла все степени вершин остались четными. Значит в <tex>G_1</tex>. <tex>H\exists</tex> эйлеров граф, а значит содержит эйлеров цикл . Если начать обход по эйлерову циклу из <tex>Pv</tex>. Будем считать началом , то и концом закончится он в <tex>Pv</tex> вершину . Если теперь вернуть цикл <tex>vC</tex>. Тогда , то мы никак не сможем продложить его обойти <tex>P\Rightarrow</tex> в <tex>G</tex>, так как не свободно вычерчиваемый из <tex>v \notin C</tex>.<br>|[[Файл:ATG_part1.jpg|200px|right]]|-|<tex>\Leftarrow</tex> Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br>
Рассмотрим произвольную цепь <tex>P = (v,w)</tex>. Пусть <tex>G_1 = G/P</tex>. В <tex>G_1</tex> все степени вершин четные (если <tex>v = w</tex>) либо ровно 2 вершины имеют нечетную степень. Возьмем <tex>H_1</tex> <tex>-</tex> компонента связности из <tex>G_1</tex>, содержащая <tex>v</tex>. Все ребра <tex>G_1</tex> содержатся в <tex>H_1</tex>, иначе существует цикл, проходящий через какую либо вершину из <tex>P</tex> кроме <tex>v</tex> (следует из эйлеровости графа <tex>G</tex>) что невозможно по условию.<br>
<tex>H_1</tex> полуэйлеров граф содержащий все ребра <tex>G_1</tex>, значит в нем <tex>\exists</tex> эйлерова цепь <tex>Q=(w,v)</tex> также содержащая все ребра <tex>G_1</tex> <tex>\Rightarrow</tex> <tex>P+Q</tex> эйлеров цикл в графе <tex>G</tex>.
== Строение ==
