14.2. Транзитивная ориентация

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

Например, граф, изображенный на рис. 14.5, а, транзитивно ориентируем. Транзитивная ориентация этого графа представлена на рис. 14.5, б.

Рис. 14.5. а — граф ; б — транзитивная ориентация графа

В этом разделе мы обсудим алгоритм Пнуели, Лемпеля и Ивена [14.14], осуществляющий проверку, является ли простой неориентированный граф транзитивно ориентируемым и получающим транзитивную ориентацию G, если она существует. Для изложения этого алгоритма мы введем некоторые обозначения: означает, что вершины связаны ребром, ориентированным из i в определяется аналогично;

означает, что существует ребро, связывающее вершины i и означает, что не существует ребра, связывающего вершины i и

означает, что либо либо либо ребро не ориентировано.

и т. д. будут использоваться для обозначения соответствующих ребер.

Рассмотрим неориентированный граф , который транзитивно ориентируем. Пусть — транзитивная ориентация графа

Предположим, что существуют такие три вершины что тогда из транзитивности G должно следовать Аналогично если, для то из транзитивности G должно следовать Эти замечания приводят к следующим простым правилам, которые образуют основу алгоритма Пнуели, Лемпеля и Ивена. Правило При если и то ориентируем ребро как Правило При , если и то ориентируем ребро как

Рис. 14.6. а — правило б —

Эти два правила иллюстрируются рис. 14.6, на котором штриховые линии указывают на отсутствие соответствующего ребра. Представим описание алгоритма транзитивной ориентации графа.

Алгоритм 14.3. Транзитивная ориентация (Пнуели, Лемпеля и Ивена).

S1. Пусть дан простой неориентированный граф G. Положить

S2. (Начало фазы ) Выбрать реброе графа G и ориентировать его произвольным образом. Ориентировать, если возможно, ребра графа G, смежные с , используя правило или Ориентированное ребро пометить как «рассмотренное».

S3. Проверить, существует ли в графе G ориентированное ребро, которое не помечено как «рассмотренное»; если да, то идти к шагу Иначе идти к шагу

S4. Пусть — ориентированное ребро в графе G, которое не помечено как «рассмотренное». Тогда для каждого ребра в графе G, инцидентного i или выполнить следующие действия (всякий раз, когда они применимы) и пометить как «рассмотренное»:

Случай 1. Пусть рассматриваемое ребро. а. (Применение правила . Если и ребро не ориентировано, то ориентировать как

6. (Противоречие с правилом ) Если и ребро уже ориентировано как то возникло противоречие с правилом Идти к шагу

Случай 2. Пусть рассматриваемое ребро будет

а. (Применение правила ) Если и ребро не ориентировано, то ориентировать как

б. (Противоречие с правилом ) Если и ребро уже ориентировано как то возникло противоречие с правилом Идти к шагу

S5. Идти к шагу S3

S6. (Успешное окончание фазы .) Проверить, все ли ребра графа G уже ориентированы. Если да, то идти к шагу Иначе удалить из графа G все ориентированные ребра. Пусть G— полученный в результате граф.

S7. Положить Идти к шагу

S8. (Все ребра данного графа ориентированы в соответствии с правилами Это — транзитивная ориентация данного графа.) HALT.

S9. (Граф G не является транзитивно ориентируемым.) HALT.

Основная обработка в этом алгоритме производится на шаге На нем мы проверяем каждое ребро, смежное с ориентированным ребром Если это ребро уже ориентировано, то мы проверяем, согласуется ли его ориентация и ориентация ребра в соответствии с правилом или Если рассматриваемое ребро еще не ориентировано, то мы ориентируем его, если это возможно, используя правило или

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

Алгоритм заканчивается, 1) когда обнаруживается противоречие с правилом или либо 2) когда ориентированы все ребра данного графа, так что ориентация согласуется с правилами В первом случае граф не является транзитивно ориентируемым, а во втором — граф транзитивно ориентируем, и полученный ориентированный граф определяет его транзитивную ориентацию.

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

Проиллюстрируем алгоритм двумя примерами. Сперва рассмотрим граф, представленный на рис. 14.7, а.

Фаза 1. Мы начинаем, ориентируя ребро 7—2 как По правилу влечет ориентацию — ориентацию Правило не применимо ни к одному из ребер, смежных

(см. скан)

Рис. 14.7.

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

Рис. 14.8.

Удалим из графа G (рис. 14.7, а) все ребра, которые ориентированы в фазе 1. Полученный граф G представлен на рис. 14.7, в. С этого момента начинается фаза 2, на которой рассматривается граф

Фаза 2. Начнем с ориентации ребра 1—2 как Это приводит к следующей последовательности ориентаций:

Таким образом, все ребра графа G ориентированы, как показано на рис. 14.7, г. Эта ориентация графа G согласована с правилами Поэтому фаза 2 успешно завершается. Полученная транзитивная ориентация графа G представлена на рис. 14.7, д.

Рассмотрим другой граф, показанный на рис. 14.8. Начнем с ориентации ребра 1—2 как Это ведет к следующей последовательности ориентаций:

которая требует, чтобы ребро 1—2 было ориентировано как что противоречит ориентации, которая уже сопоставлена ребру 1—2. Таким образом, получено противоречие с правилом Следовательно, граф на рис. 14.8 не является транзитивно ориентируемым.

Теперь перейдем к доказательству корректности алгоритма 14.3. Для выполнения этого необходимо доказать два следующих утверждения:

Утверждение 1. Если алгоритм 14.3 завершается успешно (шаг ), то полученный ориентированный граф является транзитивной ориентацией исходного графа.

Утверждение 2. Если граф транзитивно ориентируем, то алгоритм 14.3 завершается успешно.

Рассмотрим сначала утверждение 1.

Дан неориентированный граф . Предположим, что алгоритм завершается успешно. Рассмотрим произвольную пару ребер которые ориентированы на одной и той же фазе алгоритма. Тогда мы можем построить последовательность выводов, которая начинается с ребра и заканчивается ориентацией ребра как . Такую последовательность мы будем называть цепью вывода из . Заметим, что может быть несколько цепей вывода из . Например, в ориентированном графе на рис. 14.7, г цепи вывода из могут иметь вид

Таким образом, ясно, что можно говорить о кратчайшей цепи вывода между любой парой ориентированных ребер, которые были ориентированы на одной и той же фазе алгоритма 14.3. Доказательство утверждения 1 основывается на следующей лемме:

Лемма 14.2. После успешного завершения фазы 1 в графе G не может быть таких трех вершин что

Доказательство. Напомним, что означает, что либо либо либо ребро не ориентировано. Ясно, что должно существовать ребро, связывающее вершины и k. Иначе мы получили бы противоречие, так как по правилу влечет

Предположим, что запрещенная ситуация типа возникает после завершения фазы 1 алгоритма 14.3. Тогда выберем среди всех цепей вывода, которые приводят к запрещенной ситуации, цепь, кратчайшую с минимальным числом ориентированных ребер, заходящих в k. Ясно, что любая такая цепь должна иметь длину не менее трех. Пусть одна из таких цепей имеет вид

При этом должно быть либо для некоторого либо для некоторого k. Таким образом, необходимо рассмотреть два случая.

Случай 1. Пусть Тогда вывод требует, чтобы Далее, так как иначе цепь вывода

приводила бы к запрещенной ситуации Однако эта цепь короче исходной, что противоречит предположению о ее минимальности,

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

Рис. 14.9.

Случай Как и в предыдущем случае, вывод требует, чтобы Далее так как иначе влекло бы I — что противоречит предположению, что Кроме того, из следует, что

Случай, иллюстрирующий эти рассуждения, представлен на рис. 14.9, б. Тогда цепь вывода

ведет к запрещенной ситуации имеет ту же длину, что и исходная цепь, но включает меньше ребер, входящих в k, на единицу. Это вновь противоречит предположению, которое было сделано относительно выбора исходной цепи вывода.

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

Теорема 14.3. Подграф является транзитивным.

Теорема 14.4. Если алгоритм 14.3 завершается успешно, то он обеспечивает транзитивную ориентацию графа.

Доказательство. Проводится индукцией по числу фаз в алгоритме. Если алгоритм ориентирует все ребра данного графа в фазе 1, то, согласно теореме 14.3, получаемая ориентация транзитивна.

Пусть данный граф ориентируется за фаз. Пусть Е — множество ребер, которые получают ориентацию на первой фазе. Тогда, согласно теореме 14.3, подграф транзитивен. Далее, так как подграф ориентируем за фаз, то из индуктивного предположения следует, что транзитивен. Теперь мы докажем, что ориентированный граф транзитивен.

Предположим, что граф G не транзитивен, т. е. в нем существуют такие три вершины что но Тогда оба ребра не могут принадлежать Е или так как оба графа G и G" транзитивны. Не нарушая общности, предположим, что принадлежат Е, а Тогда должно существовать ребро соединяющее вершины i и иначе

влекло бы по правилу Предположим, что ребро ориентировано как на фазе 1. Тогда граф G не транзитивен, и мы приходим к противоречию. С другой стороны, если оно ориентировано как на более поздней фазе, то граф G" не транзитивен — вновь приходим к противоречию.

Таким образом, невозможно существование в графе G таких трех вершин i, j, к, что но Следовательно, граф G транзитивен. Утверждение 1 доказано.

Перейдем к доказательству утверждения 2. Рассмотрим граф , который транзитивно ориентируем. Ясно, что если мы изменим ориентацию всех ребер в любой транзитивной ориентации графа G, то получаемый ориентированный граф также является транзитивной ориентацией графа

Выберем какое-либо ребро графа G и ориентируем его произвольным образом. Пусть это будет ребро Теперь если мы приступим к ориентации других ребер, используя правила то ребра, ориентированные таким образом, будут иметь ту же самую ориентацию во всех возможных транзитивных ориентациях графа, в которых ребро ориентировано как . Это верно потому, что если ориентация ребра определена, то ориентации, выведенные по правилам обязательны для транзитивной ориентируемости. Поэтому отсюда вытекает, что если мы применим алгоритм 14.3 к транзитивно ориентируемому графу, то фаза 1 закончится успешно без появления противоречий с правилом или Ребра, ориентированные на первой фазе, будут иметь эту же ориентацию в некоторой транзитивной ориентации графа

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

Назовем ребра множества Е помеченными ребрами, а инцидентные им вершины — помеченными вершинами. Обозначим множество помеченных вершин через V. Отметим, что непомеченные ребра могут быть инцидентны помеченным вершинам.

Лемма 14.3. В графе G не может быть трех таких помеченных вершин i, j, k, что ребра не помечены, а ребро помечено.

Доказательство. Предположим, что запрещенная ситуация указанного в лемме типа существует.

Рис. 14.10.

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

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

Следующее после помеченное ребро в кратчайшей цепи Р есть либо либо для некоторого . Мы, не нарушая общности, предположим, что это ребро есть Следовательно так как иначе ребро не было бы помечено из-за присутствия ребра Далее, существует ребро соединяющее i и так как иначе ребро было бы помечено.

Таким образом, различны. Ребро также присутствует в графе, так как иначе ребро было бы помечено.

Соотношения, установленные до этого момента, изображены на рис. 14.10, б. Ребро не может быть помеченным, так как из этого следовало бы, что ребро было бы помеченным. Таким образом, мы имеем более короткую цепь вывода из ребра к ребру ведущую к другой запрещенной ситуации, когда ребро помечено, а ребра не помечены. Это противоречит допущению.

Теорема 14.5. Если граф транзитивно ориентируем, то граф также транзитивно ориентируем.

Доказательство. Так как правила помечают только смежные ребра, то граф связен. Рассмотрим произвольную вершину Если v связана с какой-либо вершиной v? V, то она должна быть связана со всеми вершинами V, которые смежны с v, так как иначе ребро было бы помечено. Поскольку граф G связен, то отсюда следует, что вершина v должна быть смежна со всеми вершинами в V.

Пусть G — транзитивная ориентация графа G, в которой ориентация ребер из Е согласуется с ориентацией в графе

Разобьем множество на четыре подмножества следующим образом:

Отметим, что D состоит из всех тех вершин множества , которые смежны со всеми вершинами множества V, но не все ребра, соединяющие вершину в D и вершины в ориентированы в одном и том же направлении.

Транзитивность G влечет следующие соотношения между различными подмножествами V.

1) для всех

2) для всех

3) все ребра, связывающие А и С, ориентированы из А в С.

4) все ребра, связывающие В и С, ориентированы из С в В.

Эти соотношения представлены на рис. 14.11, а.

Изменим ориентацию всех ребер, ориентированных из V в D, так что все ребра, связывающие V и D, станут ориентированы из D в V. Полученная ориентация показана на рис. 14.11, б. Мы утверждаем, что эта ориентация транзитивна. Для доказательства этого мы должны показать, что если в графе на рис. 14.11, б то для любых i, j и k. Ясно, что это верно, если ни у одного из этих ребер не менялась ориентация.

Таким образом, мы должны рассмотреть только четыре следующих случая:

Во всех четырех случаях как показано на рис. 14.11, б. Таким образом, ориентация, изображенная на рис. 14.11, б, транзитивна. Удалим из графа с рис. 14.11, б все ребра а именно все помеченные ребра.

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

Рис. 14.11.

Если ребро не принадлежит то оно должно принадлежать , в противном случае ориентация, изображенная на рис. 14.11, б, вновь была бы нетранзитивной. Таким образом, i и к принадлежат V.

Так как не существует вершины вне V, которая имела бы ребро, заходящее в нее из V, и ребро, исходящее из нее в V, то также принадлежит

Таким образом, мы имеем помеченные вершины i, j, k, непомеченные ребра и помеченное ребро . Это невозможно в силу леммы 14.3.

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

Теперь должно быть ясно, что алгоритм транзитивной ориентации, рассмотренный выше, является примером алгоритма, который прост, но доказательство корректности которого очень запутанно. Более ранний алгоритм для решения этой задачи приведен в работе [14.15]. Авторы работ [14.14, 14,16] ввели понятие «графы перестановок» и установили структурное соответствие между данными и транзитивно ориентируемыми графами. Они рассмотрели также алгоритм, позволяющий проверить, является ли данный граф графом перестановок.

Некоторые задачи графов, которые трудноразрешимы в общем случае, становятся простыми при рассмотрении лишь транзитивно ориентируемых графов. Примерами таких задач могут служить задачи выделения максимальной клики и минимальной раскраски. Эти задачи возникают при изучении размещения памяти и решении задачи траесировки [14.16]. Изложение этих задач можно найти в работах [14.17, 14.18].