Изменения

[[Основные определения теории графов|Граф ]] называется '''произвольно вычерчиваемым из вершины <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>v\Rightarrow</tex> эйлерова графа <br>Пусть в <tex>G</tex> принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь <tex>P\exists</tex> и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через цикл <tex>G_1C, v \notin C</tex> подграф графа .<br>Рассмотрим <tex>G_1 = G/C</tex>(здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, полученный удалением из и следовательно <tex>GG_1</tex> всех рёбер цепи {{---}} эйлеров. Тогда в <tex>PG_1</tex>. Если ''w=v'', то все вершины подграфа <tex>G_1\exists</tex> имеют чётную степень, если же эйлеров цикл. Если начать обход по эйлерову циклу из <tex>w≠vv</tex>, то и закончится он в <tex>G_1v</tex> содержит в точности две вершины нечётной степени. Пусть Если теперь вернуть цикл <tex>H_0C</tex> – компонента связности графа , то мы никак не сможем его обойти, так как из вершины <tex>G_1v</tex> , содержащая вершину больше нет не посещенных ребер <tex>v\Rightarrow</tex>. Ясно, что вершина <tex>wG</tex> принадлежит не свободно вычерчиваемый из <tex>H_0v</tex> . Следовательно, [[Файл:ATG_part2.jpg|200px|right]]<tex>H_0\Leftarrow</tex> – полуэйлеров <br>Пусть дан эйлеров граф, и потому в <tex>H_0G</tex> существует полу-эйлерова (''w,v'')-цепь вершина <tex>Qv</tex>принадлежит всем его циклам. Очевидно, что <br>Рассмотрим произвольный путь <tex>H_0P = v \leadsto w</tex> содержит все рёбра графа . Пусть <tex>G_1= G/P</tex>. Предположим, что Возможны 2 случая: # Если <tex>G_1v = w</tex> содержит неодноэлементную компоненту связности , то <tex>HP</tex>{{---}} цикл, отличную от значит степени всех вершин в <tex>H_0G_1</tex> . Тогда остались четными <tex>H\Rightarrow</tex> – эйлеров граф, и потому в <tex>HG_1</tex> содержится цикл{{---}} эйлеров. Этот цикл не проходит через вершину <texbr>v</tex>, что невозможно. Следовательно, все компоненты связности подграфа # Если <tex>G_1v \neq w</tex>, отличные от то так как <tex>H_0G</tex>, одноэлементны.<br>Таким образом, цепь эйлеров граф <tex>Q\exists</tex> содержит все рёбра графа эйлеров путь <tex>w \leadsto v \in G_1</tex>. Отсюда вытекает Покажем, что объединение цепей в обоих случаях эйлеров обход пройдет по всем ребрам <tex>PG_1</tex> и . В <tex>QG</tex> – эйлерова цепь в графе <tex>G\exists</tex>единственная компонента связности, являющаяся продолжением цепи содержащая ребра. При удалении <tex>P</tex>.<br>Обратноих количество не могло увеличится, пусть в графе <tex>G</tex> существует иначе должен быть цикл <tex>C</tex>, не содержащий вершину <tex>v</tex>(смотри рисунок). Рассмотрим подграф Значит в <tex>G_1</tex>, полученный удалением из <tex>G</tex> всех ребер цикла <tex>C</tex>. Пусть <tex>H\exists</tex> – единственная компонента связности подграфа содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, содержащая вершину либо эйлеров <tex>v\Rightarrow</tex>. Легко понять, что в <tex>HG_1</tex> – эйлеров граф. Обозначим через <tex>P\exists</tex> эйлерову эйлерова цепь подграфа . Можно считать, что началом и концом цепи <tex>P</tex> является вершина <tex>v</tex>. Поскольку <tex>Q = w \leadsto v</tex> не принадлежит циклу <tex>C\Rightarrow</tex>, цепь <tex>P+Q</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> (не исключая <tex>0</tex>), причем каждую изолированную вершину обязательно соединим с <tex>v</tex>.<br>Полученный граф <tex>G</tex>:* связен,* имеет только вершины четной степени,* является произвольно вычерчиваемым из <tex>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам.Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно. ==См. также==* [[Покрытие рёбер графа путями]]* [[Алгоритм построения Эйлерова цикла]] ==Источники информации==* Асанов М., Баранский В., Расин В. - ''Дискретная математика: Графы, матроиды, алгоритмы — .'', Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.ISBN 5-93972-076-5 [[Категория: Алгоритмы и структуры данных]][[Категория: Обходы графов]][[Категория: Эйлеровы графы]]