3.3. Разбиения дуг

Рассмотрим теперь аналогичную общую задачу для ориентированных графов. В этом случае реберное разделение представляет собой разбиение дуг на непересекающиеся пути и контуры. Формально задача остается же самой: дать характеристику минимальных ориентированных реберных разделений, покрывающих произвольный связный ориентированный граф.

Для удобства разобьем вершины произвольного ориентированного графа на непересекающиеся множества следующим образом:

Символы будут сохранять свои смысл до конца данного раздела. Ориентированный граф называется равновесным по вершине если Ориентированный граф, который является равновесным, по каждой вершине, называется ориентированным эйлеровым графом. (Заметим, что тогда соответствующий неориентированный граф обязательно является эйлеровым графом в неориентированном смысле.) Таким образом, ориентированный эйлеров граф является таким графом, для которого Ранее было показано (см. гл. 2), что для любого ориентированного графа мы имеем

Из этого следует, что 5 непусто тогда только тогда, когда непусто, кроме того, что

если —непустые множества. Свойства минимальных реберных разделений для ориентированных графов существенно зависят от того, являются ли пустыми или нет. Если они пустые, то справедлива следующая теорема.

Теорема 3.4. В связном ориентированном эйлеровом графе множество А образует контур и, следовательно, единственное минимальное реберное разделение

Доказательство полностью аналогично доказательству теоремы 3.1.

В случае непустых множеств имеет место следующее утверждение.

Теорема 3.5. Если ориентированный граф связен, но не является равновесным, то всякое минимальное реберное разделение состоит из путей, каждый из которых соединяет вершину из с вершиной из 7. При этом

Доказательство. В граф добавим дуг таким образом, чтобы расширенный граф стал ориентированным эйлеровым графом. Конкретно, каждая вершина должна быть начальной для новых дуг, оканчивающихся в некоторых вершинах множества Кроме того, новые дуги можно ввести так, чтобы точно дуг имели в качестве конечной вершины. Пусть В означает такое множество дуг, и пусть

Так как является ориентированным эйлеровым графом, то является контуром. Если удалить дугу то оставшиеся дуги образуют путь из некоторой вершины вершине Если удалить вторую дугу то этот путь разбивается на два пути, каждый из которых соединяет вершину в с вершиной в Этого не произойдет в единственном случае, если будут смежными дугами, но это невозможно (почему?). Таким образом, после удаления всех дуг мы получим путей, имеющих названное выше свойство. Эти пути образуют реберное разделение и покрывают граф

Нам осталось доказать, что реберное разделение такого типа является минимальным и что не существует других минимальных разделений. Заметим, что произвольное покрытие объединяет, по крайней мере, путей, имеющих в качестве начальной вершины. (Число путей будет больше тогда и только тогда,

когда некоторые пути реберного разделения имеют в качестве конечной вершины.) Таким образом, по крайней мере, путей берут начало в 5. По тем же самым причинам, по крайней мере, путей заканчиваются в Если рассматриваемое реберное разделение имеет более чем путей или содержит контуры, то оно не может быть минимальным, так как мы предварительно получили реберное разделение, имеющее путей. Если оно содержит точно путей и не содержит контуров, то путей, выходящих из путей, оканчивающихся в являются одними и теми же. В этом случае реберное разделение удовлетворяет условию теоремы. Таким образом, теорема доказана.

Следующий интересный класс задач, рассмотренный Бержем ([5] в библ. к гл. 1), связан применением теоремы 3.4. Ее использование в этих задачах показывает, что удачный выбор графа для анализа является часто решающим шагом для успешного применения теории графов и что такой граф не всегда очевиден из существа задачи. Будем рассматривать конечное множество в качестве «алфавита», элементами которого являются «буквы». Последовательность где каждый является буквой, будет рассматриваться как «слово из букв» в алфавите

Циклической последовательностью букв считается последовательность букв, в которой рассматривается как элемент, следующий за (так, например, рассматривается как последовательность четырех букв циклической последовательности).

Рассмотрим следующую задачу. Пусть задан алфавит X, имеющий букв и положительное целое число Требуется найти кратчайшую циклическую последовательность такую, в которой, по крайней мере, один раз появится каждое слово из букв. Заметим, что в алфавите X существует точно различных слов из букв. Таким образом, 5 обязательно содержит самое большее (так как мы можем просто перечислить по отдельности все слова одно за другим) и элементов. Далее будет показано, что для и последняя граница является точной, построена циклическая последовательность, содержащая лгое слово из букв и состоящая из элементов.

Построим ориентированный граф вершины которого соответствуют различным словам из буквы, а дуги различным словам из букв алфавита Начальная и конечная вершина дуги соответственно.

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

Описанное построение иллюстрируется рис. 3.4. В данном случае алфавитом является

Рис. 3.4.

Дуга из например, есть дуга (Для простоты запятые между буквами опущены.) Дуги, пронумерованные от 1 до 27, образуют эйлеров контур. Вообще говоря, найдя эйлеров контур, мы тем самым определим циклическую последовательность, имеющую элементов где первая буква дуги в эйлеровом контуре. Например, в нашем примере такой последовательностью (без запятых) является

Циклическая последовательность построенная таким образом, обладает требуемыми свойствами. Чтобы показать это, заметим, что дуг, которые следуют за любой дугой в эйлеровом контуре обязательно имеют вид

для выбранных букв Соответствующие члены имеют вид

т. е. образуют дугу (слово из букв), с которой мы произвольно начали рассмотрение. Таким образом 5, очевидно, содержит все слова из букв и является максимально короткой последовательностью. 5 является также решением задачи о нахождении длиннейшей циклической последовательности, в которой слово из букв не встречается более одного раза (почему?).

Заметим, что кратчайшая циклическая последовательность, содержащая все слова из букв, имеет элементов и в случае, когда (Если то любая последовательность из букв удовлетворяет нашему условию, а если то единственная буква алфавита составляет соответствующую последовательность.) В частности, приведенное выше построение очень просто осуществляется при

Упражнения

(см. скан)

теорему, характеризующую уникурсальные ориентированные графы.

Теорема 3.6. Ориентированный связный граф является уникурсальным тогда и только тогда, когда он является либо ориентированным эйлеровым графом, либо таким, что для единственной вершины

Теоремы 3,5 и 3.6 играют основную роль при описании потоков в сетях, о чем речь будет идти ниже, В той же связи полезна следующая теорема.

Теорема 3.7. Если -ориентированный граф, для которого обозначают единственные вершины 5 и соответственно и

то может быть покрыт элементарными путями из возможно, в сочетании с некоторым числом контуров.

Доказательство. Если граф связен, то теорема 3,5 утверждает, что может быть покрыт путями, принадлежащими требуемому множеству. Раньше было показано, что любой простой путь может быть разбит на простой путь, соединяющий те же самые вершины одним или более простых контуров. Если несвязен, то пусть обозначают его компоненты. Вершины обязательно принадлежат одной компоненте (почему?). Эта компонента, как мы только что видели, может быть покрыта простыми путями из возможно, некоторым числом контуров. Каждая оставшаяся компонента является ориентированным эйлеровым графом, который связен. А раз это так, то его дуги образуют контур. Если этот контур окажется непростым, то он может быть разбит на простые контуры. Теорема доказана.

Упражнения

(см. скан)

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

Например, найти, при каких условиях все улицы города можно перевести на одностороннее движение, сохранив возможность проезда из любой точки города в любую другую точку? Эти условия задаются [11] следующей теоремой.

Теорема 3.8. Связный граф является ориентируемым (в вышеупомянутом смысле) тогда и только тогда, когда каждое ребро принадлежит, по крайней мере, одному циклу.

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

Чтобы доказать обратное, рассмотрим построение, которое дает требуемую ориентацию. Возьмем некоторый простой цикл включающий вершины

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

Предположим, что в графе существует, по крайней мере, одна вершина отличная от (В противном случае теорема доказана.) Тогда, по крайней мере, одна вершина смежна с некоторой вершиной Пусть будет такое ребро, что По сделанному предположению содержится в некотором простом цикле С. Ориентируем все ребра С, не имевшие до сих пор направления. Припишем им направления, соответствующие обходу С в любом направлении. Полученный в результате расширенный ориентированный граф является также сильно связным ,

(проверьте это) и содержит, по крайней мере, одну новую вершину, а именно, Если не все вершины включены в расширенный граф, то выбирается новая вершина и процесс повторяется до тех пор, пока все вершины не будут просмотрены.