Изменения

Перейти к: навигация, поиск
м
См. также
{{Определение
|definition=
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. <br> }}{{Утверждение|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>\Rightarrow</tex> <br>Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br>Рассмотрим <tex>G_1 = G/C</tex> (здесь и далее это означает удаление только ребер, не трогая вершины). Пусть При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно <tex>HG_1</tex> компонента связности {{---}} эйлеров. Тогда в <tex>G_1</tex>. <tex>H\exists</tex> эйлеров граф, а значит содержит эйлеров цикл . Если начать обход по эйлерову циклу из <tex>Pv</tex>. Будем считать началом , то и концом закончится он в <tex>Pv</tex> вершину . Если теперь вернуть цикл <tex>vC</tex>. Тогда , то мы никак не сможем продложить его обойти, так как из вершины <tex>Pv</tex> больше нет не посещенных ребер <tex>\Rightarrow</tex> в <tex>G</tex>, так как не свободно вычерчиваемый из <tex>v \notin C</tex>.<br>[[Файл:ATG_part2.jpg|200px|right]]<tex>\Leftarrow</tex> <br>Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br>Рассмотрим произвольную цепь произвольный путь <tex>P = (v,\leadsto w)</tex>. Пусть <tex>G_1 = G/P</tex>. В Возможны 2 случая: # Если <tex>v = w</tex>, то <tex>G_1P</tex> все {{---}} цикл, значит степени всех вершин четные (если в <tex>G_1</tex> остались четными <tex>\Rightarrow</tex> <tex>G_1</tex> {{---}} эйлеров.<br># Если <tex>v = \neq w</tex>) либо ровно 2 вершины имеют нечетную степень. Возьмем , то так как <tex>H_1G</tex> эйлеров граф <tex>-\exists</tex> компонента связности из эйлеров путь <tex>w \leadsto v \in G_1</tex>. Покажем, содержащая что в обоих случаях эйлеров обход пройдет по всем ребрам <tex>vG_1</tex>. Все ребра  В <tex>G_1G</tex> содержатся в <tex>H_1\exists</tex>единственная компонента связности, иначе существует цикл, проходящий через какую либо вершину из содержащая ребра. При удалении <tex>P</tex> кроме их количество не могло увеличится, иначе должен быть цикл, не содержащий <tex>v</tex> (следует из эйлеровости графа смотри рисунок). Значит в <tex>GG_1</tex>) что невозможно по условию.<brtex>\exists</tex>единственная компонента связности содержащая ребра, причем <tex>H_1G_1</tex> либо полуэйлеров граф содержащий все ребра , либо эйлеров <tex>\Rightarrow</tex> в <tex>G_1</tex>, значит в нем <tex>\exists</tex> эйлерова цепь <tex>Q=(w,\leadsto v)</tex> также содержащая все ребра <tex>G_1</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. — С. 36. — ISBN 5-93972-076-5
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]

Навигация