Изменения

[[Основные определения теории графов|Граф ]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' ('англ. ''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v </tex> может быть продолжена до эйлеровой цепи эйлерового цикла графа <tex>G</tex>. Разумеется, если граф }}{{Утверждение|statement=Любой произвольно вычерчиваем вычерчиваемый из вершины <tex>v</tex> граф является [[Эйлеров цикл, то он является Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеровым графом]]. }} 

Неодноэлементный эйлеров [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров граф '']] <tex>G'' </tex>, содержащий хотя бы одно ребро, является произвольно вычерчиваемым из вершины ''<tex>v'' тогда и только тогда, когда </tex> <tex>\Longleftrightarrow</tex> вершина ''<tex>v'' </tex> принадлежит любому циклу всем циклам графа ''<tex>G''</tex>.<br>

[[Файл:ATG_part1.jpg|200px|right]]<tex>\Rightarrow</tex> <br>Пусть вершина ''в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v'' эйлерова графа ''G'' принадлежит любому циклу\notin C</tex>. <br>Рассмотрим произвольную <tex>G_1 = G/C</tex> (''vздесь и далее это означает удаление только ребер, w''не трогая вершины)-цепь ''P'' и покажем. При удалении цикла все степени вершин остались четными, потому что её можно продолжить до эйлеровой цепикаждая вершина содержит четное количество ребер цикла, и следовательно <tex>G_1</tex> {{---}} эйлеров. Обозначим через Тогда в <mathtex>G_1</mathtex> подграф графа ''G'', полученный удалением из ''G'' всех рёбер цепи ''P''<tex>\exists</tex> эйлеров цикл. Если ''w=начать обход по эйлерову циклу из <tex>v''</tex>, то все вершины подграфа и закончится он в <tex>v</tex>. Если теперь вернуть цикл <mathtex>G_1C</mathtex> имеют чётную степень, если же ''w≠v''то мы никак не сможем его обойти, то так как из вершины <mathtex>G_1v</mathtex> содержит в точности две вершины нечётной степени. Пусть больше нет не посещенных ребер <mathtex>H_0\Rightarrow</mathtex> – компонента связности графа <mathtex>G_1G</mathtex> , содержащая вершину ''v''. Ясно, что вершина ''w'' принадлежит не свободно вычерчиваемый из <mathtex>H_0v</mathtex> . Следовательно, [[Файл:ATG_part2.jpg|200px|right]]<mathtex>H_0\Leftarrow</mathtex> <br> – полуэйлеров Пусть дан эйлеров граф, и потому в <mathtex>H_0G</mathtex> существует полуэйлерова (''w,вершина <tex>v'')-цепь ''Q''</tex> принадлежит всем его циклам. Нетрудно понять, что <mathbr>Рассмотрим произвольный путь <tex>H_0P = v \leadsto w</mathtex> содержит все рёбра графа . Пусть <mathtex>G_1= G/P</mathtex>. В самом деле, предположим, что Возможны 2 случая: # Если <mathtex>G_1v = w</mathtex> содержит неодноэлементную компоненту связности ''H'', отличную от то <mathtex>H_0P</mathtex> . Тогда ''H'' – эйлеров граф{{---}} цикл, и потому значит степени всех вершин в ''H'' содержится цикл. Этот цикл, очевидно, не проходит через вершину ''v'', что невозможно. Следовательно, все компоненты связности подграфа <mathtex>G_1</mathtex> остались четными <tex>\Rightarrow</tex>, отличные от <mathtex>H_0G_1</mathtex>, одноэлементны{{---}} эйлеров.<br>Таким образом# Если <tex>v \neq w</tex>, цепь ''Q'' содержит все рёбра графа то так как <tex>G</tex> эйлеров граф <tex>\exists</tex> эйлеров путь <mathtex>w \leadsto v \in G_1</mathtex>. Отсюда вытекает Покажем, что объединение цепей ''P'' и ''Q'' – эйлерова цепь в графе ''обоих случаях эйлеров обход пройдет по всем ребрам <tex>G_1</tex>. В <tex>G''</tex> <tex>\exists</tex> единственная компонента связности, являющаяся продолжением цепи ''содержащая ребра. При удалении <tex>P''.<br/tex>Обратноих количество не могло увеличится, пусть в графе ''G'' существует иначе должен быть цикл ''C'', не содержащий вершину ''<tex>v''</tex>(смотри рисунок). Рассмотрим подграф Значит в <mathtex>G_1</mathtex>, полученный удалением из ''G'' всех ребер цикла ''С''. Пусть ''H'' – <tex>\exists</tex> единственная компонента связности подграфа содержащая ребра, причем <mathtex>G_1</mathtex> либо полуэйлеров, содержащая вершину ''v''. Легко понять, что ''H'' – либо эйлеров граф. Обозначим через ''P'' эйлерову <tex>\Rightarrow</tex> в <tex>G_1</tex> <tex>\exists</tex> эйлерова цепь подграфа . Можно считать, что началом и концом цепи ''P'' является вершина ''<tex>Q = w \leadsto v''. Поскольку ''v'' не принадлежит циклу ''C'', цепь ''</tex> <tex>\Rightarrow</tex> <tex>P'' нельзя продолжить до эйлеровой цепи графа ''+Q</tex> эйлеров цикл в графе <tex>G''</tex>.