Эйлеровы графы

Определение 1. Эйлеровым путем в графе называется путь, содержащий все ребра графа и проходящий через каждое по одному разу.

Пример 1. Рассмотрим граф

Он имеет эйлеров путь (x ₄, x ₁, x ₃, x ₂, x ₁, x ₅, x ₃).

Определение 2. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа и проходящий через каждое по одному разу.

Определение 3. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Пример 2. Рассмотрим граф

Данный граф является эйлеровым, так как он имеет эйлеров цикл (x ₂, x ₅, x ₄, x ₁, x ₂, x ₃, x ₄, x ₂).

Теорема 1. Эйлеров граф связный, и все его вершины четны.

Доказательство.

Связность следует из определения эйлерового графа. Эйлеров цикл содержит каждое ребро и притом только один раз. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: количество входов в вершину и количество выходов из вершины.

Теорема 2. Если граф G(X,T) связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 3. Если граф G(X,T) обладает эйлеровым путем с концами А и В, то граф G(X,T) связный и А и В его единственные нечетные вершины.

Доказательство.

Если путь начинается в А и кончается в В, то А и В нечетные вершины, даже если путь неоднократно проходил через них. В любую другую вершину путь должен привести и вывести из нее, т.е. остальные вершины четные.

Теорема 4. Если граф G(X,T) связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.

Теорема 5. Если граф G(X,T) связный, то можно построить цикличный маршрут, содержащий все ребра в точности 2 раза, по одному в каждом направлении.