Изменения

[[Основные определения теории графов|Граф ]] называется '''произвольно вычерчиваемым из вершины <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>.

'''Источники== Строение ==[[Файл:''' 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 [[Категория: Алгоритмы и структуры данных]][[Категория: Обходы графов]][[Категория: Эйлеровы графы]]