Изменения

[[Основные определения теории графов|Граф ]] называется '''произвольно вычерчиваемым из вершины <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> принадлежит любому циклу. Рассмотрим произвольную <tex>(v, w)\exists</tex> — цепь цикл <tex>PC, v \notin C</tex> и покажем, что её можно продолжить до [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеровой цепи]]. Обозначим через <br>Рассмотрим <tex>G_1= G/C</tex> подграф графа (здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно <tex>GG_1</tex>, полученный удалением из {{---}} эйлеров. Тогда в <tex>GG_1</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>w\Leftarrow</tex> принадлежит <br>Пусть дан эйлеров граф <tex>H_0G</tex> . Следовательно, вершина <tex>H_0v</tex> – полуэйлеров граф, и потому в принадлежит всем его циклам.<texbr>H_0Рассмотрим произвольный путь </tex> существует полу-эйлерова <tex>(P = v, \leadsto w)</tex> — цепь . Пусть <tex>QG_1 = G/P</tex>. Очевидно, что Возможны 2 случая: # Если <tex>H_0v = w</tex> содержит все рёбра графа , то <tex>G_1P</tex>. Предположим{{---}} цикл, что значит степени всех вершин в <tex>G_1</tex> содержит неодноэлементную компоненту связности остались четными <tex>H\Rightarrow</tex>, отличную от <tex>H_0G_1</tex> {{---}} эйлеров. Тогда <texbr>H</tex> – эйлеров граф, и потому в <tex>H</tex> содержится цикл. Этот цикл не проходит через вершину # Если <tex>v\neq w</tex>, что невозможно. Следовательно, все компоненты связности подграфа то так как <tex>G_1G</tex>, отличные от эйлеров граф <tex>H_0\exists</tex>, одноэлементны.<br>Таким образом, цепь <tex>Q</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\exists</tex>. Пусть <tex>H</tex> – единственная компонента связности подграфа содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, содержащая вершину либо эйлеров <tex>v\Rightarrow</tex>. Легко понять, что в <tex>HG_1</tex> – эйлеров граф. Обозначим через <tex>P\exists</tex> эйлерову эйлерова цепь подграфа . Можно считать, что началом и концом цепи <tex>P</tex> является вершина <tex>Q = w \leadsto v</tex>. Поскольку <tex>v\Rightarrow</tex> не принадлежит циклу <tex>C</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 [[Категория: Алгоритмы и структуры данных]][[Категория: Обходы графов]][[Категория: Эйлеровы графы]]