35. Ориентированные эйлеровы графы

Ориентированной эйлеровой цепью ориентированного графа G называется замкнутая ориентированная цепь, содержащая все дуги G.

Открытой ориентированной эйлеровой цепью называется открытая ориентированная цепь, содержащая все дуги графа G.

Ориентированный граф, обладающий ориентированной эйлеровой цепью, называется Ориентированным эйлеровым графом(рис. 28).

Рисунок 28

Ориентированным эйлеровым графом является граф, изображенный на рис. 28, поскольку дуги е1 e2, е3, е4, е5, е6 образуют в графе G ориентированную эйлерову цепь.

Теорема. Для связного ориентированного графа G следующие утверждения равносильны:

1) G - ориентированный эйлеров граф;

2) для любой вершины v графа G справедливо равенство d - (v) = d+(v);

3) G - объединение нескольких реберно-непересекающихся контуров.

Рассмотрим, например, ориентированный эйлеров граф G на рис. 28. Легко проверить, что он обладает свойством, сформулированным в п. 2 теоремы, и является также объединением реберно-непересекающихся контуров {е2, е3) и {e1, e4, e5, e6}.

Легко доказать и следующую теорему:

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

1) в графе G имеются такие две вершины v1 и v2, что d+ (v1)=d - (v1)+1 и d - (v2) = d+(v2)+1;

2) для любой вершины v, отличной от v1 и v2, справедливо равенство d - (v) - d+ (v).

Например, условиям этой теоремы удовлетворяет граф на рис. 29. Открытой ориентированной эйлеровой цепью графа G является последовательность e1, е2, e3, e4, е5, е6.

Рисунок 29

Эйлеров контур в орграфе D — это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур.

Для орграфа, показанного на рис. 30; в этом орграфе 14 эйлеровых контуров. Два из них такие: v1, v2, v3, v4, v2, v1, v3, v1, v4, v1 и v1, v2, v1, v4, v2, v3, v4, v1, v3, v1.

Рисунок 30

< Предыдущая		Следующая >