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

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

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

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

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

В следующей теореме даются простые характеризации ориентированных эйлеровых графов. Теорема доказывается по той же схеме, что и теорема 3.1.

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

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

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

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

Рассмотрим, например, ориентированный эйлеров граф G на рис. 5.10. Легко проверить, что он обладает свойством, сформулированным в п. 2 теоремы, и является также объединением реберно-непересекающихся контуров

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

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

1) в графе G имеются такие две вершины что

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

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

Рис. 5.11. Граф с открытой ориентированной эйлеровой цепью.

Пусть S={0, 1.....s-1} - алфавит, состоящий из s букв. Очевидно, что, используя буквы этого алфавита S, можно построить s" различных слов длины n. Последовательность де Брёйна — это циклическая последовательности длины у которой для любого слова со длины существует такое единственное , что где значения индексов вычисляются по mod L. Последовательности де Брёйна находят применение в теории кодирования и при исследовании сетей связи. Подробную информацию об этих последовательностях можно найти в работах [5.1, 5.2]. Мы же рассмотрим следующую задачу:

Для любых ли и целых существует последовательность де Брёйна над алфавитом Как мы увидим далее, ответ на этот вопрос положителен.

Покажем, что для любых существует такой ориентированный эйлеров граф что всякая ориентированная эйлерова цепь в этом графе соответствует последовательности де Брёйна длины над алфавитом Граф строится следующим образом:

1) последовательность V образуется всеми словами длины над алфавитом ;

2) Е — множество всех слов длины над ;

3) дуга имеет начальную вершину и конечную вершину Заметим, что каждая вершина имеет s заходящих и S исходящих дуг. Таким образом, для каждой вершины v справедливо равенство

Графы представлены на рис. 5.12, а, б.

Рис. 5.12.

Допустим, в графе имеется ориентированная эйлерова цепь С. Если мы конкатенируем первые буквы слов, представленных дугами в том порядке, в котором дуги появляются в цепи С, то получим такую последовательность длины что любая ее подпоследовательность из последовательных букв будет соответствовать единственному слову, но никакие две различные подпоследовательности не будут соответствовать одному слову. Поэтому последовательность, построенная таким образом, будет последовательностью де Брёйна. Например, последовательность дуг 101, 010, 100 является ориентированной эйлеровой

цепью графа Конкатенация первых букв этих слов дает последовательность де Брёйна 00011101.

Таким образом, чтобы показать, что для любых существует последовательность де Брёйна, необходимо доказать, что — ориентированный эйлеров граф. Это мы сделаем в следующей теореме:

Теорема — ориентированный эйлероь граф.

Доказательство. -связный, так как для любых двух вершин существует ориентированный путь из вершины в вершину состоящий из следующих дуг:

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

Следствие 5.8.1. Для любых существует последовательность де Брёйна.