Произвольно вычерчиваемые из заданной вершины графы

Определение:

Граф называется произвольно вычерчиваемым из вершины [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]\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].

[math]\Leftarrow[/math] Пусть дан эйлеров граф [math]G[/math], вершина [math]v[/math] принадлежит всем его циклам. Рассмотрим произвольную цепь [math]P = (v,w)[/math]. Пусть [math]G_1 = G/P[/math]. В [math]G_1[/math] все степени вершин четные (если [math]v = w[/math]) либо ровно 2 вершины имеют нечетную степень. Возьмем [math]H_1[/math] [math]-[/math] компонента связности из [math]G_1[/math], содержащая [math]v[/math]. Все ребра [math]G_1[/math] содержатся в [math]H_1[/math], иначе существует цикл, проходящий через какую либо вершину из [math]P[/math] кроме [math]v[/math] (следует из эйлеровости графа [math]G[/math]) что невозможно по условию. [math]H_1[/math] полуэйлеров граф содержащий все ребра [math]G_1[/math], значит в нем [math]\exists[/math] эйлерова цепь [math]Q=(w,v)[/math] также содержащая все ребра [math]G_1[/math] [math]\Rightarrow[/math] [math]P+Q[/math] эйлеров цикл в графе [math]G[/math].

Строение

Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины [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