Изменения
Нет описания правки
{{Определение
|definition=
[[Основные определения теории графов|Граф ]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. Разумеется, если граф произвольно вычерчиваем из вершины <tex>v</tex>, то он является эйлеровым графом. }}
{{Теорема
|statement=
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] <tex>G</tex> является произвольно вычерчиваемым из вершины <tex>v</tex> <tex>\Longleftrightarrow</tex> вершина <tex>v</tex> принадлежит всем циклам графа <tex>G</tex>.<br>
|proof=
<tex>\Leftarrow</tex> Пусть вершина <tex>v</tex> эйлерова графа <tex>G</tex> принадлежит любому циклу. Рассмотрим произвольную <tex>(v, w)</tex>-цепь <tex>P</tex> и покажем, что её можно продолжить до [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлерового цикла]]. Обозначим через <tex>G_1</tex> подграф графа <tex>G</tex>, полученный удалением из <tex>G</tex> всех рёбер цепи <tex>P</tex>. Если <tex>w=v</tex>, то все вершины подграфа <tex>G_1</tex> имеют чётную степень, если же <tex>w\ne v</tex>, то <tex>G_1</tex> содержит в точности две вершины нечётной степени. Пусть <tex>H_0</tex> — [[Отношение связности, компоненты связности|компонента связности ]] графа <tex>G_1</tex>, содержащая вершину <tex>v</tex>. Ясно, что вершина <tex>w</tex> принадлежит <tex>H_0</tex>. Следовательно, <tex>H_0</tex> — полуэйлеров граф, и потому в <tex>H_0</tex> существует эйлерова <tex>(v, w)</tex>-цепь <tex>Q</tex>.<br><tex>H_0</tex> содержит все рёбра графа <tex>G_1</tex>. Предположим, что <tex>G_1</tex> содержит неодноэлементную компоненту связности <tex>H</tex>, отличную от <tex>H_0</tex>. Тогда <tex>H</tex> — эйлеров граф, и потому в <tex>H</tex> содержится цикл. Этот цикл не проходит через вершину <tex>v</tex>, что невозможно. Следовательно, все компоненты связности подграфа <tex>G_1</tex>, отличные от <tex>H_0</tex>, одноэлементны.<br>
Таким образом, цепь <tex>Q</tex> содержит все рёбра графа <tex>G_1</tex>. Отсюда вытекает, что объединение цепей <tex>P</tex> и <tex>Q</tex> — эйлеров цикл в графе <tex>G</tex>, являющийся продолжением цепи <tex>P</tex>.<br>
<tex>\Rightarrow</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>.
[[Файл:ATGexample.jpg|right|300px]]
Опираясь на теорему несложно описать строение всех графов, произвольно вычерчиваемых из вершины <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>:
* Связен;
