5. Ориентированные графы

В предыдущих главах мы представили некоторые основные результаты теории неориентированных графов. Однако для описания некоторых ситуаций неориентированных графов недостаточно. Например, при представлении схемы уличного движения графом, ребра которого соответствуют улицам, для указания допустимого направления движения ребрам необходимо присваивать ориентацию. Другим примером является программа для ЭВМ, моделируемая графом, ребра которого представляют поток управления от одних множеств инструкций к другим. В таком представлении программы для указания направления потока управления ребрам также необходимо присвоить ориентацию. Еще одним примером физической системы, для представления которой требуется ориентированный граф, является электрическая цепь. Применения ориентированных графов и соответствующие алгоритмы рассматриваются в гл. 11—15.

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

5.1. Основные определения и понятия

Начнем с введения нескольких основных определений и понятий, относящихся к ориентированным графам.

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

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

В графическом представлении ориентированного графа вершины изображаются точками или кружками, а ребра (дуги) — отрезками

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

Например, если такие, что Их), ориентированный граф можно представить рис. 5.1. В этом графе — параллельные дуги, а — петля.

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

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

Дуга называется исходящей из своей начальной вершины и заходящей в свою конечную вершину. Верщина называется изолированной, если она не имеет инцидентных дуг.

Степенью вершины называется число инцидентных ей дуг. Полустепенью захода вершины является число заходящих в V] дуг, а полустепенью исхода — число исходящих из дуг. Символами и б" обозначают минимальнее полустепени исхода и захода ориентированного графа. Аналогично символами обозначают максимальные полустепени исхода и захода соответственно.

Множества любой вершины определяются следующим образом: . Например, в графе на рис. 5.1 .

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

Теорема 5.1. В ориентированном графе с дугами

Сумма полустепеней захода=Сумма полустепеней исхода=m.

Подграфы и порожденные подграфы ориентированного графа определяются так же, как и в случае неориентированных графов (разд. 1.2).

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

Ориентированным маршрутом ориентированного графа называется такая конечная последовательность вершин

, что является дугой графа G. Такой маршрут обычно называется ориентированным -маршрутом, причем начальная вершина, — конечная вершина маршрута, а все другие вершины — внутренние. Начальная и конечная вершины ориентированного маршрута называются его концевыми вершинами. Отметим, что дуги, а следовательно, и вершины могут появляться в ориентированном маршруте более одного раза.

Ориентированный маршрут называется открытым, если его концевые вершины различны, в противном случае — замкнутым.

Ориентированный маршрут называется ориентированной цепью, если все его дуги различны. Ориентированная цепь является открытой, если ее концевые вершины различны, в противном случае — замкнутой.

Открытая ориентированная цепь называется ориентированным путем, если различны все ее вершины.

Замкнутая ориентированная цепь называется ориентированным циклом или контуром, если ее вершины, за исключением концевых, различны.

Говорят, что ориентированный граф ациклический или бесконтурный, если он не имеет контуров. Например, ациклическим является ориентированный граф на рис. 5.2.

Рис. 5.2. Ациклический ориентированный граф.

Рис. 5.3. Сильно связный ориентированный граф.

Последовательность вершин ориентированного графа G называется маршрутом в G, если она является маршрутом лежащего в основе неориентированного графа Например, последовательность в графе на рис. 5.2 является маршрутом, но не ориентированным.

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

Ориентированный граф называется связным, если связным является лежащий в его основе неориентированный граф.

Подграф ориентированного графа G называется компонентой графа G, если он является компонентой графа

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

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

Ориентированный граф называется сильно связным, если сильно связны все его вершины. Например, сильно связным является граф на рис. 5.3.

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

Рассмотрим ориентированный граф . Легко видеть, что всякая его вершина принадлежит точно одной сильно связной компоненте графа G. Следовательно, множества вершин сильно связных компонент образуют разбиение множества вершин У графа

Рис. 5.4. Граф и его конденсация.

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

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

Таким образом, хотя свойство «сильной связности» влечет разбиение множества вершин графа, оно может не порождать разбиение множества дуг.

Объединение, пересечение, сумма по mod 2 и другие операции над ориентированными графами определяются точно так же, как и в случае неориентированных графов (разд. 1.5).

Граф, получающийся в результате стягивания всех дуг сильно связных компонент ориентированного графа G, называется конденсированным графом графа G. Конденсация графа, приведенного на рис. 5.4, а, представлена на рис. 5.4, б.

Вершины графа соответствуют сильно связным компонентам графа G и называются конденсированными образами компонент.

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

Теперь определим минимально связные ориентированные графы и изучим некоторые их свойства.

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

Рис. 5.5. Минимально связный ориентированный граф.

Минимально связным является, например, граф, представленный на рис. 5.5.

Очевидно, что минимально связные графы не могут иметь параллельных дуг и петель.

Мы знаем, что неориентированный граф минимально связен тогда и только тогда, когда он является деревом (упр. 2.13). По теореме 2.5 дерево имеет не менее двух вершин степени 1. Следовательно, минимально связные неориентированные графы имеют по крайней мере две вершины степени 1.

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

Теорема 5.2. Если минимально связный ориентированный граф G имеет более одной вершины, то в нем содержатся по крайней мере две вершины степени 2.

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

Докажем теорему индукцией по

Если то граф G является контуром, следовательно, в этом случае теорема верна.

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

Случай 1. Всякий контур G имеет длину 2.

В этом случае любые две смежные вершины соединены точно двумя дугами, имеющими противоположную ориентацию. Пусть — простой неориентированный граф на том же множестве вершин, что и граф G, а вершины в нем смежны тогда и только тогда, когда они смежны в графе G. Поскольку граф G — связный, то связен и граф G. Но так как в графе G нет контуров длины больше 2, то граф G не имеет циклов. Следовательно, G — дерево. По теореме 2.5 он имеет по меньшей мере две висячие вершины. В графе G они имеют степень 2, что доказывает теорему для этого случая.

Случай 2. В графе G имеется контур С длиной 13. Поскольку граф G — минимально связный, между любыми смежными вершинами контура С имеется единственная дуга, а между любыми не смежными в контуре С вершинами дуг нет.

Пусть G — граф, получающийся в результате стягивания дуг С. Граф G имеет дуг и вершин, где — число дуг и вершин графа G соответственно. Поэтому цикломатическое число графа G равно

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

С другой стороны, если ни ни не являются конденсированным образом контура С, то — вершины G степени 2, что доказывает теорему.

Завершаем этот раздел определением свойства «квазисильной связности»,

Рис. 5.6. Квазисильно связный граф.

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