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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Гонево детектед)
Строка 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>. <!-- [Есть подозрение, что это ЛПП] Разумеется, если граф произвольно вычерчиваем из вершины <tex>v</tex>, то он является эйлеровым графом.--> }}
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=

Версия 04:40, 24 января 2011

Определение:
Граф называется произвольно вычерчиваемым из вершины [math]v[/math] (англ. Arbitrarily traceable graph), если любая цепь с началом в вершине [math]v[/math] может быть продолжена до эйлеровой цепи графа [math]G[/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 стр.