Произвольно вычерчиваемые из заданной вершины графы — различия между версиями
м |
|||
| Строка 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''. | + | Пусть вершина ''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:12, 13 октября 2010
| Определение: |
| Граф называется произвольно вычерчиваемым из вершины v (англ. Arbitrarily traceable graph), если любая цепь с началом в вершине v может быть продолжена до эйлеровой цепи графа G. Разумеется, если граф произвольно вычерчиваем из вершины v, то он является эйлеровым графом. |
| Теорема: |
Неодноэлементный эйлеров граф G является произвольно вычерчиваемым из вершины v тогда и только тогда, когда вершина v принадлежит любому циклу графа G. |
| Доказательство: |
|
Пусть вершина v эйлерова графа G принадлежит любому циклу. Рассмотрим произвольную (v, w)-цепь P и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через подграф графа G, полученный удалением из G всех рёбер цепи P. Если w=v, то все вершины подграфа имеют чётную степень, если же w≠v, то содержит в точности две вершины нечётной степени. Пусть – компонента связности графа , содержащая вершину v. Ясно, что вершина w принадлежит . Следовательно, – полуэйлеров граф, и потому в существует полуэйлерова (w,v)-цепь Q. Очевидно, что содержит все рёбра графа . Предположим, что содержит неодноэлементную компоненту связности H, отличную от . Тогда H – эйлеров граф, и потому в H содержится цикл. Этот цикл не проходит через вершину v, что невозможно. Следовательно, все компоненты связности подграфа , отличные от , одноэлементны. |
Источники:
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
