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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 6: Строка 6:
 
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] ''G'' является произвольно вычерчиваемым из вершины ''v'' тогда и только тогда, когда вершина ''v'' принадлежит любому циклу графа ''G''.<br>
 
Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] ''G'' является произвольно вычерчиваемым из вершины ''v'' тогда и только тогда, когда вершина ''v'' принадлежит любому циклу графа ''G''.<br>
 
|proof=
 
|proof=
Пусть вершина ''v'' эйлерова графа ''G'' принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь ''P'' и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <math>G_1</math> подграф графа ''G'', полученный удалением из ''G'' всех рёбер цепи ''P''. Если ''w=v'', то все вершины подграфа <math>G_1</math>  имеют чётную степень, если же ''w≠v'', то <math>G_1</math> содержит в точности две вершины нечётной степени. Пусть <math>H_0</math> – компонента связности графа <math>G_1</math> , содержащая вершину ''v''. Ясно, что вершина ''w'' принадлежит <math>H_0</math> . Следовательно, <math>H_0</math>  – полуэйлеров граф, и потому в <math>H_0</math>  существует полуэйлерова (''w,v'')-цепь ''Q''. Очевидно, что <math>H_0</math>  содержит все рёбра графа <math>G_1</math>. Предположим, что <math>G_1</math> содержит неодноэлементную компоненту связности ''H'', отличную от <math>H_0</math> . Тогда ''H'' – эйлеров граф, и потому в ''H'' содержится цикл. Этот цикл не проходит через вершину ''v'', что невозможно. Следовательно, все компоненты связности подграфа <math>G_1</math>, отличные от <math>H_0</math>, одноэлементны.<br>
+
Пусть вершина ''v'' эйлерова графа ''G'' принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь ''P'' и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <math>G_1</math> подграф графа ''G'', полученный удалением из ''G'' всех рёбер цепи ''P''. Если ''w=v'', то все вершины подграфа <math>G_1</math>  имеют чётную степень, если же ''w≠v'', то <math>G_1</math> содержит в точности две вершины нечётной степени. Пусть <math>H_0</math> – компонента связности графа <math>G_1</math> , содержащая вершину ''v''. Ясно, что вершина ''w'' принадлежит <math>H_0</math> . Следовательно, <math>H_0</math>  – полуэйлеров граф, и потому в <math>H_0</math>  существует эйлеров путь (''w,v'') ''Q''. Очевидно, что <math>H_0</math>  содержит все рёбра графа <math>G_1</math>. Предположим, что <math>G_1</math> содержит неодноэлементную компоненту связности ''H'', отличную от <math>H_0</math> . Тогда ''H'' – эйлеров граф, и потому в ''H'' содержится цикл. Этот цикл не проходит через вершину ''v'', что невозможно. Следовательно, все компоненты связности подграфа <math>G_1</math>, отличные от <math>H_0</math>, одноэлементны.<br>
 
Таким образом, цепь ''Q'' содержит все рёбра графа <math>G_1</math>. Отсюда вытекает, что объединение цепей ''P'' и ''Q'' – эйлерова цепь в графе ''G'', являющаяся продолжением цепи ''P''.<br>
 
Таким образом, цепь ''Q'' содержит все рёбра графа <math>G_1</math>. Отсюда вытекает, что объединение цепей ''P'' и ''Q'' – эйлерова цепь в графе ''G'', являющаяся продолжением цепи ''P''.<br>
 
Обратно, пусть в графе ''G'' существует цикл ''C'', не содержащий вершину ''v''. Рассмотрим подграф <math>G_1</math>, полученный удалением из ''G'' всех ребер цикла ''С''. Пусть ''H'' – компонента связности подграфа <math>G_1</math>, содержащая вершину ''v''. Легко понять, что ''H'' – эйлеров граф. Обозначим через ''P'' эйлерову цепь подграфа . Можно считать, что началом и концом цепи ''P'' является вершина ''v''. Поскольку ''v'' не принадлежит циклу ''C'', цепь ''P'' нельзя продолжить до эйлеровой цепи графа ''G''.
 
Обратно, пусть в графе ''G'' существует цикл ''C'', не содержащий вершину ''v''. Рассмотрим подграф <math>G_1</math>, полученный удалением из ''G'' всех ребер цикла ''С''. Пусть ''H'' – компонента связности подграфа <math>G_1</math>, содержащая вершину ''v''. Легко понять, что ''H'' – эйлеров граф. Обозначим через ''P'' эйлерову цепь подграфа . Можно считать, что началом и концом цепи ''P'' является вершина ''v''. Поскольку ''v'' не принадлежит циклу ''C'', цепь ''P'' нельзя продолжить до эйлеровой цепи графа ''G''.

Версия 00:14, 13 октября 2010

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

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

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

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