Изменения

[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из вершины <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>\LeftarrowRightarrow</tex> <br>Пусть вершина в <tex>vG</tex> эйлерова графа <tex>G\exists</tex> принадлежит любому циклу. Рассмотрим произвольную цикл <tex>(C, v, w)\notin C</tex>-цепь .<br>Рассмотрим <tex>PG_1 = G/C</tex> (здесь и покажемдалее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что её можно продолжить до [[Эйлеров циклкаждая вершина содержит четное количество ребер цикла, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлерового цикла]]. Обозначим через и следовательно <tex>G_1</tex> подграф графа {{---}} эйлеров. Тогда в <tex>GG_1</tex>, полученный удалением из <tex>G</tex> всех рёбер цепи <tex>P\exists</tex>эйлеров цикл. Если начать обход по эйлерову циклу из <tex>w=v</tex>, то все вершины подграфа и закончится он в <tex>G_1v</tex> имеют чётную степень, если же . Если теперь вернуть цикл <tex>w\ne vC</tex>, то мы никак не сможем его обойти, так как из вершины <tex>G_1v</tex> содержит в точности две вершины нечётной степени. Пусть больше нет не посещенных ребер <tex>H_0\Rightarrow</tex> — [[Отношение связности, компоненты связности|компонента связности]] графа <tex>G_1G</tex>, содержащая вершину не свободно вычерчиваемый из <tex>v</tex>. Вершины [[Файл:ATG_part2.jpg|200px|right]]<tex>v\Leftarrow</tex> и <texbr>w</tex> лежат на одном цикле в графе Пусть дан эйлеров граф <tex>G</tex>, значит вершина <tex>wv</tex> принадлежит <tex>H_0</tex>всем его циклам. Следовательно, <texbr>H_0Рассмотрим произвольный путь </tex> — полуэйлеров граф, и потому в <tex>H_0</tex> существует эйлерова <tex>(P = v, \leadsto w)</tex>-цепь <tex>Q</tex>.<br>Пусть <tex>H_0<G_1 = G/tex> содержит все рёбра графа <tex>G_1P</tex>. Предположим, что Возможны 2 случая: # Если <tex>G_1</tex> содержит неодноэлементную компоненту связности <tex>Hv = w</tex>, отличную от то <tex>H_0P</tex>. Тогда <tex>H</tex> — эйлеров граф{{---}} цикл, и потому значит степени всех вершин в <tex>HG_1</tex> содержится цикл. Этот цикл не проходит через вершину остались четными <tex>v\Rightarrow</tex>, что невозможно. Следовательно, все компоненты связности подграфа <tex>G_1</tex>, отличные от <tex>H_0</tex>, одноэлементны{{---}} эйлеров.<br>Таким образом, цепь # Если <tex>Q</tex> содержит все рёбра графа <tex>G_1v \neq w</tex>. Отсюда вытекает, что объединение цепей то так как <tex>PG</tex> и эйлеров граф <tex>Q\exists</tex> — эйлеров цикл в графе путь <tex>Gw \leadsto v \in G_1</tex>. Покажем, являющийся продолжением цепи что в обоих случаях эйлеров обход пройдет по всем ребрам <tex>PG_1</tex>.<br> В <tex>\RightarrowG</tex> Пусть в графе <tex>G\exists</tex> существует цикл единственная компонента связности, содержащая ребра. При удалении <tex>CP</tex>их количество не могло увеличится, иначе должен быть цикл, не содержащий вершину <tex>v</tex>(смотри рисунок). Рассмотрим подграф Значит в <tex>G_1</tex>, полученный удалением из <tex>G\exists</tex> всех рёбер цикла <tex>C</tex>. Пусть <tex>H</tex> — единственная компонента связности подграфа содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, содержащая вершину <tex>v</tex>. Легко понять, что <tex>H</tex> — либо эйлеров граф. Обозначим через <tex>P\Rightarrow</tex> эйлеров цикл подграфа. Можно считать, что началом и концом цикла в <tex>PG_1</tex> является вершина <tex>v\exists</tex>. Поскольку эйлерова цепь <tex>Q = w \leadsto v</tex> не принадлежит циклу <tex>C\Rightarrow</tex>, цепь <tex>P+Q</tex> нельзя продолжить до эйлерового цикла графа эйлеров цикл в графе <tex>G</tex>.

Опираясь на теорему несложно описать опишем строение всех графов, произвольно вычерчиваемых из вершины <tex>v</tex>. <br>Возьмем произвольный [[Дерево, эквивалентные определения|лес]] <tex>H</tex>, не содержащий вершину <tex>v</tex>. Каждую вершину нечетной степени соединим некоторым нечетным числом кратных ребер с <tex>v</tex>, а каждую вершину четной степени <tex>-</tex> четным числом кратных ребер с <tex>v</tex> (не исключая <tex>0</tex>), причем каждую изолированную вершину обязательно соединим с <tex>v</tex>.<br>

* Связен;связен,* Имеет имеет только вершины четной степени;,* Является является произвольно вычерчиваемым из <tex>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам.Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно. ==См. также==* [[Покрытие рёбер графа путями]]* [[Алгоритм построения Эйлерова цикла]]

==Источникиинформации==''* Асанов М., Баранский В., Расин В.'' Дискретная математика: Графы, матроиды, алгоритмы. — '', Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. — С. 36. — ISBN 5-93972-076-5