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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Очень умно изменять список литературы)
Строка 6: Строка 6:
 
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] <tex>G</tex> является произвольно вычерчиваемым из вершины <tex>v</tex> тогда и только тогда, когда вершина <tex>v</tex> принадлежит любому циклу графа <tex>G</tex>.<br>
 
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] <tex>G</tex> является произвольно вычерчиваемым из вершины <tex>v</tex> тогда и только тогда, когда вершина <tex>v</tex> принадлежит любому циклу графа <tex>G</tex>.<br>
 
|proof=
 
|proof=
Пусть вершина <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>w</tex> принадлежит <tex>H_0</tex>. Следовательно, <tex>H_0</tex> — полуэйлеров граф, и потому в <tex>H_0</tex>  существует эйлерова <tex>(v, w)</tex> — цепь <tex>Q</tex>. Очевидно, что <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>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>w</tex> принадлежит <tex>H_0</tex> . Следовательно, <tex>H_0</tex> — полуэйлеров граф, и потому в <tex>H_0</tex>  существует эйлерова <tex>(v, w)</tex> — цепь <tex>Q</tex>. Очевидно, что <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>Q</tex> содержит все рёбра графа <tex>G_1</tex>. Отсюда вытекает, что объединение цепей <tex>P</tex> и <tex>Q</tex> — эйлеров цикл в графе <tex>G</tex>, являющийся продолжением цепи <tex>P</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>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</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>
 
'''Источники:''' <br>
Асанов М., Баранский В., Расин В. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. — СПб.:Издательство «Лань», 2010. — 368 с.
+
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
  
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]

Версия 06:15, 14 октября 2011

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

Пусть вершина [math]v[/math] эйлерова графа [math]G[/math] принадлежит любому циклу. Рассмотрим произвольную [math](v, w)[/math] — цепь [math]P[/math] и покажем, что её можно продолжить до эйлерового цикла. Обозначим через [math]G_1[/math] подграф графа [math]G[/math], полученный удалением из [math]G[/math] всех рёбер цепи [math]P[/math]. Если [math]w=v[/math], то все вершины подграфа [math]G_1[/math] имеют чётную степень, если же [math]w\ne v[/math], то [math]G_1[/math] содержит в точности две вершины нечётной степени. Пусть [math]H_0[/math] — компонента связности графа [math]G_1[/math] , содержащая вершину [math]v[/math]. Ясно, что вершина [math]w[/math] принадлежит [math]H_0[/math] . Следовательно, [math]H_0[/math] — полуэйлеров граф, и потому в [math]H_0[/math] существует эйлерова [math](v, w)[/math] — цепь [math]Q[/math]. Очевидно, что [math]H_0[/math] содержит все рёбра графа [math]G_1[/math]. Предположим, что [math]G_1[/math] содержит неодноэлементную компоненту связности [math]H[/math], отличную от [math]H_0[/math] . Тогда [math]H[/math] — эйлеров граф, и потому в [math]H[/math] содержится цикл. Этот цикл не проходит через вершину [math]v[/math], что невозможно. Следовательно, все компоненты связности подграфа [math]G_1[/math], отличные от [math]H_0[/math], одноэлементны.
Таким образом, цепь [math]Q[/math] содержит все рёбра графа [math]G_1[/math]. Отсюда вытекает, что объединение цепей [math]P[/math] и [math]Q[/math] — эйлеров цикл в графе [math]G[/math], являющийся продолжением цепи [math]P[/math].

Обратно, пусть в графе [math]G[/math] существует цикл [math]C[/math], не содержащий вершину [math]v[/math]. Рассмотрим подграф [math]G_1[/math], полученный удалением из [math]G[/math] всех ребер цикла [math]C[/math]. Пусть [math]H[/math] — компонента связности подграфа [math]G_1[/math], содержащая вершину [math]v[/math]. Легко понять, что [math]H[/math] — эйлеров граф. Обозначим через [math]P[/math] эйлеров цикл подграфа . Можно считать, что началом и концом цикла [math]P[/math] является вершина [math]v[/math]. Поскольку [math]v[/math] не принадлежит циклу [math]C[/math], цепь [math]P[/math] нельзя продолжить до эйлерового цикла графа [math]G[/math].
[math]\triangleleft[/math]

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