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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отмена правки 17269 участника Helm (обсуждение))
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из  вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. Разумеется, если граф произвольно вычерчиваем из вершины <tex>v</tex>, то он является эйлеровым графом. }}
+
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из  вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. <br>Любой произвольно вычерчиваемый из вершины <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=
−
<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> Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br>
−
Таким образом, цепь <tex>Q</tex> содержит все рёбра графа <tex>G_1</tex>. Отсюда вытекает, что объединение цепей <tex>P</tex> и <tex>Q</tex> — эйлеров цикл в графе <tex>G</tex>, являющийся продолжением цепи <tex>P</tex>.<br>
+
Рассмотрим <tex>G_1 = G/C</tex> (здесь и далее это означает удаление только ребер, не трогая вершины). Пусть <tex>H</tex> компонента связности <tex>G_1</tex>. <tex>H</tex> эйлеров граф, а значит содержит эйлеров цикл <tex>P</tex>. Будем считать началом и концом <tex>P</tex> вершину <tex>v</tex>. Тогда мы не сможем продложить <tex>P</tex> в <tex>G</tex>, так как <tex>v \notin C</tex>.
−
<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>.
+
<br>
−
}}
+
<tex>\Leftarrow</tex> Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br>
 +
Рассмотрим произвольную цепь <tex>P = (v,w)</tex>. Пусть <tex>G_1 = G/P</tex>. В <tex>G_1</tex> все степени вершин четные (если <tex>v = w</tex>) либо ровно 2 вершины имеют нечетную степень. Возьмем <tex>H_1</tex> <tex>-</tex> компонента связности из <tex>G_1</tex>, содержащая <tex>v</tex>. Все ребра <tex>G_1</tex> содержатся в <tex>H_1</tex>, иначе существует цикл, проходящий через какую либо вершину из <tex>P</tex> кроме <tex>v</tex> (следует из эйлеровости графа <tex>G</tex>) что невозможно по условию.<br>
 +
<tex>H_1</tex> полуэйлеров граф содержащий все ребра <tex>G_1</tex>, значит в нем <tex>\exists</tex> эйлерова цепь <tex>Q=(w,v)</tex> также содержащая все ребра <tex>G_1</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> (не исключая 0), причем каждую изолированную вершину обязательно соединим с <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>:

Версия 15:09, 23 февраля 2012

Определение:
Граф называется произвольно вычерчиваемым из вершины [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]

[math]\Rightarrow[/math] Пусть в [math]G[/math] [math]\exists[/math] цикл [math]C, v \notin C[/math].
Рассмотрим [math]G_1 = G/C[/math] (здесь и далее это означает удаление только ребер, не трогая вершины). Пусть [math]H[/math] компонента связности [math]G_1[/math]. [math]H[/math] эйлеров граф, а значит содержит эйлеров цикл [math]P[/math]. Будем считать началом и концом [math]P[/math] вершину [math]v[/math]. Тогда мы не сможем продложить [math]P[/math] в [math]G[/math], так как [math]v \notin C[/math].
[math]\Leftarrow[/math] Пусть дан эйлеров граф [math]G[/math], вершина [math]v[/math] принадлежит всем его циклам.
Рассмотрим произвольную цепь [math]P = (v,w)[/math]. Пусть [math]G_1 = G/P[/math]. В [math]G_1[/math] все степени вершин четные (если [math]v = w[/math]) либо ровно 2 вершины имеют нечетную степень. Возьмем [math]H_1[/math] [math]-[/math] компонента связности из [math]G_1[/math], содержащая [math]v[/math]. Все ребра [math]G_1[/math] содержатся в [math]H_1[/math], иначе существует цикл, проходящий через какую либо вершину из [math]P[/math] кроме [math]v[/math] (следует из эйлеровости графа [math]G[/math]) что невозможно по условию.

[math]H_1[/math] полуэйлеров граф содержащий все ребра [math]G_1[/math], значит в нем [math]\exists[/math] эйлерова цепь [math]Q=(w,v)[/math] также содержащая все ребра [math]G_1[/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] (не исключая 0), причем каждую изолированную вершину обязательно соединим с [math]v[/math].
Полученный граф [math]G[/math]:

  • Связен;
  • Имеет только вершины четной степени;
  • Является произвольно вычерчиваемым из [math]v[/math], как эйлеров граф, у которого [math]v[/math] принадлежит всем циклам.

Источники

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Произвольно_вычерчиваемые_из_заданной_вершины_графы&oldid=18231»