Редактирование: Произвольно вычерчиваемые из заданной вершины графы

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из  вершины <tex>v</tex>''' (англ. ''Arbitrarily traceable graph''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. }}
+
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из  вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. Разумеется, если граф произвольно вычерчиваем из вершины <tex>v</tex>, то он является эйлеровым графом. }}
{{Утверждение
 
|statement=Любой произвольно вычерчиваемый из вершины <tex>v</tex> граф является [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеровым графом]].
 
}}
 
 
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
[[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров граф]] <tex>G</tex>, содержащий хотя бы одно ребро, является произвольно вычерчиваемым из вершины <tex>v</tex> <tex>\Longleftrightarrow</tex> вершина <tex>v</tex> принадлежит всем циклам графа <tex>G</tex>.<br>
+
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] <tex>G</tex> является произвольно вычерчиваемым из вершины <tex>v</tex> <tex>\Longleftrightarrow</tex> вершина <tex>v</tex> принадлежит всем циклам графа <tex>G</tex>.<br>
 
|proof=
 
|proof=
[[Файл:ATG_part1.jpg|200px|right]]
+
<tex>\Leftarrow</tex> Пусть вершина <tex>v</tex> эйлерова графа <tex>G</tex> принадлежит любому циклу. Рассмотрим произвольную <tex>(v, w)</tex>-цепь <tex>P</tex> и покажем, что её можно продолжить до [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлерового цикла]]. Обозначим через <tex>G_1</tex> подграф графа <tex>G</tex>, полученный удалением из <tex>G</tex> всех рёбер цепи <tex>P</tex>. Если <tex>w=v</tex>, то все вершины подграфа <tex>G_1</tex> имеют чётную степень, если же <tex>w\ne v</tex>, то <tex>G_1</tex> содержит в точности две вершины нечётной степени. Пусть <tex>H_0</tex> — [[Отношение связности, компоненты связности|компонента связности]] графа <tex>G_1</tex>, содержащая вершину <tex>v</tex>. Вершины <tex>v</tex> и <tex>w</tex> лежат на одном цикле в графе <tex>G</tex>, значит вершина <tex>w</tex> принадлежит <tex>H_0</tex>. Следовательно, <tex>H_0</tex>  — полуэйлеров граф, и потому в <tex>H_0</tex> существует эйлерова <tex>(v, w)</tex>-цепь <tex>Q</tex>.<br><tex>H_0</tex>  содержит все рёбра графа <tex>G_1</tex>. Предположим, что <tex>G_1</tex> содержит неодноэлементную компоненту связности <tex>H</tex>, отличную от <tex>H_0</tex>. Тогда <tex>H</tex> — эйлеров граф, и потому в <tex>H</tex> содержится цикл. Этот цикл не проходит через вершину <tex>v</tex>, что невозможно. Следовательно, все компоненты связности подграфа <tex>G_1</tex>, отличные от <tex>H_0</tex>, одноэлементны.<br>
<tex>\Rightarrow</tex> <br>
+
Таким образом, цепь <tex>Q</tex> содержит все рёбра графа <tex>G_1</tex>. Отсюда вытекает, что объединение цепей <tex>P</tex> и <tex>Q</tex> эйлеров цикл в графе <tex>G</tex>, являющийся продолжением цепи <tex>P</tex>.<br>
Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br>
+
<tex>\Rightarrow</tex> Пусть в графе <tex>G</tex> существует цикл <tex>C</tex>, не содержащий вершину <tex>v</tex>. Рассмотрим подграф <tex>G_1</tex>, полученный удалением из <tex>G</tex> всех рёбер цикла <tex>C</tex>. Пусть <tex>H</tex> компонента связности подграфа <tex>G_1</tex>, содержащая вершину <tex>v</tex>. Легко понять, что <tex>H</tex> эйлеров граф. Обозначим через <tex>P</tex> эйлеров цикл подграфа. Можно считать, что началом и концом цикла <tex>P</tex> является вершина <tex>v</tex>. Поскольку <tex>v</tex> не принадлежит циклу <tex>C</tex>, цепь <tex>P</tex> нельзя продолжить до эйлерового цикла графа <tex>G</tex>.
Рассмотрим <tex>G_1 = G/C</tex> (здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно <tex>G_1</tex> {{---}} эйлеров. Тогда в <tex>G_1</tex> <tex>\exists</tex> эйлеров цикл. Если начать обход по эйлерову циклу из <tex>v</tex>, то и закончится он в <tex>v</tex>. Если теперь вернуть цикл <tex>C</tex>, то мы никак не сможем его обойти, так как из вершины <tex>v</tex> больше нет не посещенных ребер <tex>\Rightarrow</tex> <tex>G</tex> не свободно вычерчиваемый из <tex>v</tex>.
 
[[Файл: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>P</tex> {{---}} цикл, значит степени всех вершин в <tex>G_1</tex> остались четными <tex>\Rightarrow</tex> <tex>G_1</tex> {{---}} эйлеров.<br>
 
# Если <tex>v \neq w</tex>, то так как <tex>G</tex> эйлеров граф <tex>\exists</tex> эйлеров путь <tex>w \leadsto v \in G_1</tex>.
 
 
 
Покажем, что в обоих случаях эйлеров обход пройдет по всем ребрам <tex>G_1</tex>.
 
 
 
В <tex>G</tex> <tex>\exists</tex> единственная компонента связности, содержащая ребра. При удалении <tex>P</tex> их количество не могло увеличится, иначе должен быть цикл, не содержащий <tex>v</tex>(смотри рисунок). Значит в <tex>G_1</tex> <tex>\exists</tex> единственная компонента связности содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, либо эйлеров <tex>\Rightarrow</tex> в <tex>G_1</tex> <tex>\exists</tex> эйлерова цепь <tex>Q = w \leadsto v</tex> <tex>\Rightarrow</tex> <tex>P+Q</tex> эйлеров цикл в графе <tex>G</tex>.
 
 
}}
 
}}
  
 
== Строение ==
 
== Строение ==
 
[[Файл:ATGexample.jpg|right|300px]]
 
[[Файл:ATGexample.jpg|right|300px]]
Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины <tex>v</tex>. <br>
+
Опираясь на теорему несложно описать строение всех графов, произвольно вычерчиваемых из вершины <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>H</tex>, не содержащий вершину <tex>v</tex>. Каждую вершину нечетной степени соединим некоторым нечетным числом кратных ребер с <tex>v</tex>, а каждую вершину четной степени <tex>-</tex> четным числом кратных ребер с <tex>v</tex> (не исключая 0), причем каждую изолированную вершину обязательно соединим с <tex>v</tex>.<br>
 
Полученный граф <tex>G</tex>:
 
Полученный граф <tex>G</tex>:
* связен,
+
* Связен;
* имеет только вершины четной степени,
+
* Имеет только вершины четной степени;
* является произвольно вычерчиваемым из <tex>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам.
+
* Является произвольно вычерчиваемым из <tex>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам.
Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно.
 
 
 
==См. также==
 
* [[Покрытие рёбер графа путями]]
 
* [[Алгоритм построения Эйлерова цикла]]
 
  
==Источники информации==
+
==Источники==
* Асанов М., Баранский В., Расин В. ''Дискретная математика: Графы, матроиды, алгоритмы.'', Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. ISBN 5-93972-076-5
+
''Асанов М., Баранский В., Расин В.'' Дискретная математика: Графы, матроиды, алгоритмы. Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. — С. 36. — ISBN 5-93972-076-5
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)