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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
|definition=
 
|definition=
 
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из  вершины <tex>v</tex>''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. <br>Любой произвольно вычерчиваемый из вершины <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=
 +
[[Файл:ATG_part1.jpg|200px|right]]
 +
<tex>\Longrightarrow</tex> Пусть в <tex>G</tex>  <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br>
 +
Рассмотрим <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>\Rightarrow</tex> <tex>G</tex> не свободно вычерчиваемый из <tex>v</tex>.
 +
[[Файл:ATG_part2.jpg|200px|left]]
 +
<tex>\Longleftarrow</tex> Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br>
 +
Рассмотрим произвольный путь <tex>P = (v,w)</tex>. Пусть <tex>G_1 = G/P</tex>. Возможно 2 случая:
 +
 +
1. если <tex>v = w</tex>, то <tex>P</tex> {{---}} цикл, значит степени всех вершин в <tex>G_1</tex> остались четными <tex>\Rightarrow</tex> <tex>G_1</tex> {{---}} эйлеров.<br>
 +
2. если <tex>v \neq w</tex>, то так как <tex>G</tex> эйлеров граф <tex>\exists</tex> эйлеров путь <tex>(w,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,v)</tex> <tex>\Rightarrow</tex> <tex>P+Q</tex> эйлеров цикл в графе <tex>G</tex>.
 
}}
 
}}
−
 
−
{|
 
−
|<tex>\Longrightarrow</tex> Пусть в <tex>G</tex>  <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br>
 
−
Рассмотрим <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>\Rightarrow</tex> <tex>G</tex> не свободно вычерчиваемый из <tex>v</tex>.
 
−
|[[Файл:ATG_part1.jpg|200px|right]]
 
−
|-
 
−
|<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>.
 
−
|[[Файл:ATG_part2.jpg|200px|right]]
 
−
|}
 
  
 
== Строение ==
 
== Строение ==

Версия 13:55, 9 марта 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]
ATG part1.jpg

[math]\Longrightarrow[/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]\Rightarrow[/math] [math]G[/math] не свободно вычерчиваемый из [math]v[/math].

ATG part2.jpg

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

1. если [math]v = w[/math], то [math]P[/math] — цикл, значит степени всех вершин в [math]G_1[/math] остались четными [math]\Rightarrow[/math] [math]G_1[/math] — эйлеров.
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] (не исключая 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=19013»