Изменения

Перейти к: навигация, поиск
м
См. также
{{Определение
|definition=
[[Основные определения теории графов|Граф ]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. Разумеется, если граф }}{{Утверждение|statement=Любой произвольно вычерчиваем вычерчиваемый из вершины <tex>v</tex>граф является [[Эйлеров цикл, Эйлеров путь, то он является Эйлеровы графы, Эйлеровость орграфов|эйлеровым графом]]. }} 
{{Теорема
|statement=
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров Эйлеров граф]] <tex>G</tex> , содержащий хотя бы одно ребро, является произвольно вычерчиваемым из вершины <tex>v</tex> тогда и только тогда, когда <tex>\Longleftrightarrow</tex> вершина <tex>v</tex> принадлежит любому циклу всем циклам графа <tex>G</tex>.<br>
|proof=
Пусть вершина [[Файл: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\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>.
}}
'''Источники:''' <br>
Асанов М., Баранский В., Расин В. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. — СПб.:Издательство «Лань», 2010. — 368 с.
== Строение ==
[[Файл: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. ISBN 5-93972-076-5
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]

Навигация