Произвольно вычерчиваемые из заданной вершины графы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники)
м
Строка 27: Строка 27:
 
Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины <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> (не исключая <tex>0</tex>), причем каждую изолированную вершину обязательно соединим с <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>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно.
 
Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно.
  

Версия 19:27, 28 января 2016

Определение:
Граф называется произвольно вычерчиваемым из вершины [math]v[/math] (англ. Arbitrarily traceable graph), если любая цепь с началом в вершине [math]v[/math] может быть продолжена до эйлерового цикла графа [math]G[/math].


Любой произвольно вычерчиваемый из вершины [math]v[/math] граф является эйлеровым графом.

Теорема:
Эйлеров граф [math]G[/math], содержащий хотя бы одно ребро, является произвольно вычерчиваемым из вершины [math]v[/math] [math]\Longleftrightarrow[/math] вершина [math]v[/math] принадлежит всем циклам графа [math]G[/math].
Доказательство:
[math]\triangleright[/math]
ATG part1.jpg

[math]\Rightarrow[/math] Пусть в [math]G[/math] [math]\exists[/math] цикл [math]C, v \notin C[/math].
Рассмотрим [math]G_1 = G/C[/math] (здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно [math]G_1[/math] — эйлеров. Тогда в [math]G_1[/math] [math]\exists[/math] эйлеров цикл. Если начать обход по эйлерову циклу из [math]v[/math], то и закончится он в [math]v[/math]. Если теперь вернуть цикл [math]C[/math], то мы никак не сможем его обойти, так как из вершины [math]v[/math] больше нет не посещенных ребер [math]\Rightarrow[/math] [math]G[/math] не свободно вычерчиваемый из [math]v[/math].

ATG part2.jpg

[math]\Leftarrow[/math] Пусть дан эйлеров граф [math]G[/math], вершина [math]v[/math] принадлежит всем его циклам.
Рассмотрим произвольный путь [math]P = (v,w)[/math]. Пусть [math]G_1 = G/P[/math]. Возможны 2 случая:

  1. 1. Если [math]v = w[/math], то [math]P[/math] — цикл, значит степени всех вершин в [math]G_1[/math] остались четными [math]\Rightarrow[/math] [math]G_1[/math] — эйлеров.
  2. 2. если [math]v \neq w[/math], то так как [math]G[/math] эйлеров граф [math]\exists[/math] эйлеров путь [math](w,v) \in G_1[/math].

Покажем, что в обоих случаях эйлеров обход пройдет по всем ребрам [math]G_1[/math].

В [math]G[/math] [math]\exists[/math] единственная компонента связности, содержащая ребра. При удалении [math]P[/math] их количество не могло увеличится, иначе должен быть цикл, не содержащий [math]v[/math](смотри рисунок). Значит в [math]G_1[/math] [math]\exists[/math] единственная компонента связности содержащая ребра, причем [math]G_1[/math] либо полуэйлеров, либо эйлеров [math]\Rightarrow[/math] в [math]G_1[/math] [math]\exists[/math] эйлерова цепь [math]Q = (w,v)[/math] [math]\Rightarrow[/math] [math]P+Q[/math] эйлеров цикл в графе [math]G[/math].
[math]\triangleleft[/math]

Строение

ATGexample.jpg

Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины [math]v[/math].
Возьмем произвольный лес [math]H[/math], не содержащий вершину [math]v[/math]. Каждую вершину нечетной степени соединим некоторым нечетным числом кратных ребер с [math]v[/math], а каждую вершину четной степени [math]-[/math] четным числом кратных ребер с [math]v[/math] (не исключая [math]0[/math]), причем каждую изолированную вершину обязательно соединим с [math]v[/math].
Полученный граф [math]G[/math]: связен, имеет только вершины четной степени и является произвольно вычерчиваемым из [math]v[/math], как эйлеров граф, у которого [math]v[/math] принадлежит всем циклам. Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины [math]v[/math]. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины [math]v[/math] и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит [math]v[/math]. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно.

См. также

Источники информации

  • Асанов М., Баранский В., Расин В. Дискретная математика: Графы, матроиды, алгоритмы., Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. ISBN 5-93972-076-5