Ориентированный граф. Ориентированные графы Орграф примеры

Ориентированный граф (кратко орграф ) - (мульти) граф , рёбрам которого присвоено направление. Направленные рёбра именуются также дугами , а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом .

Основные понятия

Формально, орграф D = (V , E) {\displaystyle D=(V,E)} состоит из множества V {\displaystyle V} , элементы которого называются вершинами , и множества E {\displaystyle E} упорядоченных пар вершин u , v ∈ V {\displaystyle u,v\in V} .

Дуга (u , v) {\displaystyle (u,v)} инцидентна вершинам u {\displaystyle u} и v {\displaystyle v} . При этом говорят, что u {\displaystyle u} - начальная вершина дуги, а v {\displaystyle v} - конечная вершина .

Связность

Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг , вида v 0 { v 0 , v 1 } v 1 { v 1 , v 2 } v 2 . . . v n {\displaystyle v_{0}\{v_{0},v_{1}\}v_{1}\{v_{1},v_{2}\}v_{2}...v_{n}} (вершины могут повторяться). Длина маршрута - количество дуг в нём.

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

Контур есть замкнутый путь .

Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур .

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

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

Конденсацией орграфа D {\displaystyle D} называют орграф , вершинами которого служат сильные компоненты D {\displaystyle D} , а дуга в D ⋆ {\displaystyle D^{\star }} показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.

Дополнительные определения

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

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

Изображение и свойства всех орграфов с тремя узлами

Легенда: С - слабый, ОС - односторонний, СС - сильный, Н - является направленным графом, Г - является гамаком (ациклический), Т - является турниром

0 дуг	1 дуга	2 дуги	3 дуги	4 дуги	5 дуг	6 дуг
пустой, Н, Г	Н, Г		ОС	CC	CC	полный, CC
		ОС, Н, Г	CC, Н, Т	CC
		C, Н, Г	ОС, Н, Г, Т	ОС
		C, Н, Г	ОС

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

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

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

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

Например, при сложной оценке образцов (в геологии, например) направление ребра указывает предпочтение. В нормальной системе предпочтений не должно быть циклов

Таня Наташа

чтобы всегда можно было сделать выбор, иначе необходимо пересмотреть систему предпочтений.

Одностороннее движение.

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

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

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

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

Ребро Е = (А,В) будем называть связывающим ребром , или перешейком , если оно является единственным путем от А к В (или обратно).

Свюзывающее ребро делит все вершины графа на два множества: те, в которые можно прийти из А, не проходя по ребру Е, и те, в которые можно прийти из В, не проходя по Е. Граф в этом случае состоит из двух частей G 1 и G 2 соединенных только ребром Е (рис. a и a+1).

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

Если ребро Е i = (А i , В i) не является связывающим, то найдется другой путь, соединяющий А i и В i и не проходящий по Е i . Поэтому такое ребро будем называть циклическим ребром.

рис.2 Связывающее рис. 2+1 Конечное (связывающее) рис.2+2 Циклическое

Ребро ребро

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

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

Мы можем доказать эту теорему, указав спосмоб соответствующего ориентирования графа. Выберем в G произвольное ребро Е = (А,В) . Если Е - связывающее ребро, оно останется двухсторонним, и тогда можно будет перейти от А к В и обратно (рис.2+3).

рис.2+3 рис. 2+4

Если Е - циклическое ребро, то оно входит в некоторый цикл С, на котором можно установить циклическую ориентацию (рис.2+4).

Предположим, что мы уже ориентировали некоторую часть Н графа G , так, что из любой вершины графа Н можно пройти в любую другую его вершину с соблюдением правил одностороннего движения. Так как граф G является связным, то либо Н совпадает со всем графом G, либо найдется ребро Е= (А,В), которое не принадлежит Н , но одна из его вершин, скажем А , принадлежит Н .

Если Е - связывающее ребро АВ , то оно останется двухсторонним. Тогда для любой вершины X графа Н можно найти ориентированную цепь R , соединяющую Х с А , а значит (через ребро Е ) , и с В . Обратно от вершины В через ребро Е можно перейти к А , а затем - по ориентировочной цепи Z - от А к Х (рис a+5). Присоединяя Е к H , мы получим уже большую часть графа G , обладающую требуемым свойствам. Если же ребро Е= (А,В) является циклическим, оно принадлежит некоторому циклу С . Мы установили направление на С от А до В и далее вдоль С до первой вершины D из С , принадлежащей Н (рис. a+6).

рис. a+5 рис. a+6

Все эти ребра присоединим к Н . Пусть Х - произвольная вершина из Н , а У - любая вершина из С ; можно найти ориентированную цепь R , принадлежащую Н и соединяющую Х с А , а затем вдоль С пройти к вершине У из С . Обратно, от У можно пройти вдоль С к вершине D , а от нее - принадлежащей Н ориентированной цепью Z - от D к Х . Поэтому ориентированный граф, полученный добавлением к Н указанных ребер цикла С , также удовлетворяет требуемым условиям. Продолжая этот процесс, мы в конце концов ориентируем требуемым образом исходный граф G .

Степени вершин.

Для ориентированных графов мы имеем в каждой вершине число р(А) выходящих и число р * (А) входящих ребер. Общее число ребер равно:

N = р(А 1) + р(А 2) +... + р(А n) = p * (A 1)+p * (A 2)+...+p * (A n)

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

р(А) = р * (А) = r

Упражнение

Постройте однородные ориентированные графы степени r = 2 с числом вершин n = 2,6,7,8.

ОТНОШЕНИЯ.

Отношения и графы.

Всякая математическая система имеет дело с множеством каких-то объектов, или элементов. (Приметы: алгебра, геометрия)

Для того чтобы построить математическую теорию, нам нужны не только сами эти элементы, но также и отношения между ними. (Примеры: для чисел а > в; в геометрии -равенство треугольников, // прямых; в теории множеств - равенство и включения множеств.)

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

Введем общее определение бинарного отношения R: аRв - в находится в отношении R к а.

Например, отношение а > в означает, что в принадлежит множеству всех чисел, меньших а

Фактически, каждый ориентированный граф G определяет некоторое отношение в множестве его вершин. Это отношение можно записать в виде: аGв. Оно означает, что на графе имеется ориентированное ребро, идущее от а к в.

Специальные условия.

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

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

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

Для каждого отношения R можно определить обратное отношение R * , считая, что аR * в тогда и только тогда, когда аRв.

Из определения обратного отношения видно, что если на графе G, соответствующем R, имеется ребро (а,в), то на графе G * , соответствующем R * , должно быть ребро (в,а). Иными словами, граф G * обратным для G, т.е. графом с теми же ребрами, что и G, но противоположно ориентированными.

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

Симметрическому отношению соответствует граф с неориентированными ребрами; обратно, граф с неориентированными ребрами определяет некоторое симметрическое отношение.

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

Отношение R транзитивно , если из двух условий аRв и вRс следует, что аRc.

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

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

Отношения эквивалентности.

Отношение эквивалентности, обычно обозначаемое символом ~ , характеризуется следующими тремя свойствами:

1). Рефлексивностью: а ~ а;

2). Симметричностью: из а ~ в Þ в ~ а;

3). Транзитивностью: из а ~ в и в ~ с Þ а ~ с.

Фактически отношение эквивалентности - обобщение свойства равенства.

Отношение эквивалентности вводит в множестве вершин разбиение на непересекающиеся классы эквивалентности .

Пусть В i - множество вершин графа эквивалентности G, эквивалентных вершине i. Тогда все вершины, принадлежащие В i , соединены между собой ребрами, т.е. В i - полный граф G i . В каждой вершине такого графа-петля.Граф G распадается на множество связных компонент G i .

Частичная упорядоченность.

Отношение частичной упорядоченности - это (на примере множеств):

1). Рефлексивность: А Ê А

2). Транзитивность: если А Ê В и В Ê С Þ А Ê С

3). Тождественность: если А Ê В и В Ê АÞ А = В

Отношения строгого включения -

1). Антирефлексивность: А ÉА никогда не имеет места;

2). Транзитивность: если А É В и В É С, то А É С

Отношение упорядоченности (в строгом смысле) называется строгая упорядоченность, а>в, для которой в дополнение к предыдущим условиям выполнено также следующее:

Условие полноты. Для любых двух несовпадающих элементов в и а всегда выполнено одно из двух соотношений а>в или в>а.

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

ПЛОСКИЕ ГРАФЫ.

Условия для плоских графов.

Граф Куратовского К 3,3

Граф задача о трех домах и трех колодцах

Граф Куратовского К 5

Эти два графа - НЕ ПЛОСКИЕ!

Расширение графа - на некоторые ребра поставили новые вершины, так что эти ребра

стали элементарными цепями, состоящими из нескольких ребер.

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

Теорема Куратовсого

Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал внутри себя никакого графа, который можно было сжать до графа К 3,3 или графа К 5 .

ФОРМУЛА ЭЙЛЕРА

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

Из определения многоугольных графов следует, что они связны. Потребуем также, чтобы ни один многоугольник не лежал внутри другого. Граничные ребра каждого такого многоугольника образуют цикл, иногда называемый минимальным циклом . Часть плоскости, заключенная внутри многоугольника, называется гранью графа . На графе имеется и максимальный цикл С 1 , окружающий весь граф со всеми его гранями. Будем рассматривать часть плоскости, лежащую вне С 1 , тоже как грань графа с границей С 1 - бесконечная грань F ¥ .

Обозначим через

число вершин, ребер и граней пространственного многоугольника. .

Теорема Эйлера

в - р + г = 2

Доказательство: Формула очевидна для многоугольника, имеющего n ребер. Действительно, n вершин и n ребер, а также две грани F 1 F ¥

Добавим новую грань к графу с г гранями, проводя по грани F ¥ некоторую элементарную цепь, соединяющую две вершины максимальног графа G. Если эта дуга имеет г ребер, то нам придется бобавить г - 1 новую вершину и одну новую грань. Но тогда

в’ - р’ + г’ = (в + г - 1) - (р + г) + (г + 1) = в - р + г (=2!)

по предположению индукции.

Матричные представления.

1. Матрица инциденций А.

а). Для неориентированного графа матрица инциденций представляет собой матрицу, строки которой соответствуют вершинам, а столбцы - ребрам. Элемент матрицы равен 1, если вершина инцидентна ребру. В противном случае элемент матрицы принимает значение 0.

б). Для ориентированного графа элемент матрицы инциденций равен +1, когда вершина, инцидентная дуге, является начальной вершиной дуги (т.е. дуга исходит из этой вершины). Элемент равен -1, когда дуга входит в вершину. Если вершина не инцидентна дуге, то элемент матрицы равен 0.

2. Матрица циклов С.

а). Для неориентированного графа строки матрицы циклов соответствуют простым циклам графа, а столбцы - его ребрам. Элемент матрицы a ij =1, если цикл С i содержит ребро e j . В противном случае a ij =0.

б). Для ориентированного графа a ij =1, -1 или 0 в зависимости от того, одинакова или противоположна ориентация цикла С i и дуги e j или же данный цикл вообще не содержит дуги e j .

3. Матрица смежности вершин (или просто матрица смежности) V представляет собой матрицу, строки и столбцы которой соответствуют вершинам, а элемент матрицы a ij в случае неориентированного графа равен числу ребер, соединяющих вершины i и j. Для ориентированного графа элемент a ij равен числу ребер, направленных от вершины i к вершине j.

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

1).Ранг (максимальное число линейно-независимых столбцов) матрицы инциденций А связного графа (ориентированного и неориентированного) с n вершинами равен (n-1).

2). Ранг матрицы циклов С связного графа с m ребрами и n вершинами равен (m-n+1).

Пример использования матрицы смежности.

Следующее отображение показывает, что графы G 1 и G 2 изоморфны

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

A 2 =PA 1 P", где

Р = , или p ij =d p(i),j (символ Кронекера)

и Р" - транспонированная матрица.

Нахождение матрицы Р может быть нелегким делом.

Изоморфность G 1 и G 2 означает, что А 1 и А 2 имеют одинаковые собственные значения. Однако это условие не является достаточным (пример внизу).

Пусть V, D - произвольные множества, причем V ??. Обозначим через V 2 декартов квадрат множества V .

Ориентированным графом или, короче, орграфом G называется тройка (V, D, ц ) : где ц - некоторое отображение множества D в множество V 2 . Элементы множеств V и D называются соответственно вершинами и дугами орграфа G . Множества вершин и дуг орграфа G удобно обозначать через VG и DG соответственно. Если f - дуга, то ц (f ) является упорядоченной парой (и, v ), где и : v Ј V . Дуга f выходит из вершины и и заходит в вершину v ; в свою очередь и и v называются концевыми вершинами дуги f ; в дальнейшем будем писать f = (а иногда даже - f = uv , если нет опасности возникновения путаницы).

При записи произвольного орграфа он, как правило, будет представляться в виде G = (V, D ).

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

С каждым орграфом G = (V, D ) естественно связать граф G o = (V, Е ), называемый основанием данного орграфа. Для получения основания необходимо в орграфе G заменить каждую дугу f = ребром е = uv

На рис. 8 изображены орграф и его основание

Рисунок 8

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

В которой

Такой маршрут принято называть (v о , v t ) - ормаршрутом; вершины v o и v t называются соответственно начальной и конечной вершинами такого ормаршрута. Если v o = v t , то ормаршрут называют замкнутым. Количество дуг, составляющих ормаршрут, - это длина ормаршрута.

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

Нетрудно проверить, что существование (и, v ;) - ормаршрута гарантирует существование простой (и, v ) - орцепи.

Говорят, что вершина v достижима из вершины и , если существует (и, v) ормаршрут. Орграф G сильно связен или орсвязен, если любая его вершина достижима из любой другой вершины. Очевидно, сильно связный орграф является связным; обратное утверждение, разумеется, не верно.

Граф G называется ориентируемым, если он является основанием некоторого сильно связного орграфа.

Теорема 1.3 . Связный граф G ориентируем тогда и только тогда, когда каждое его ребро не является мостом.

Доказательство . Пусть граф G является основанием орграфа Н и G содержит мост е . Тогда в Н имеется дуга f =, где и, v - концы ребра е . Очевидно, в Н нет (u, v ) - ормаршрутов. Следовательно, граф G не является ориентируемым.

Обратно, пусть граф G не имеет мостов, т.е. каждое ребро графа G содержится в некотором цикле. Поскольку любой цикл является ориентируемым графом, в графе G существует максимальный ориентируемый подграф Н . Убедимся, что Н = G . Допустим, что это равенство не выполнено. В силу связности графа G существует ребро е, инцидентное вершине v из Н и не лежащее в Н . По предположению ребро е лежит в некотором цикле С . Обозначим через Q множество ребер цикла, не принадлежащих подграфу Н . Нетрудно понять, что, добавив к Н все ребра из множества Q , мы снова получим ориентируемый подграф в противоречие с выбором Н .

Пусть G - произвольный орграф. Полустепенью исхода degv вершины v называется число всех дуг, имеющих v в качестве начала. Аналогично, полустепень захода degv - это число всех дуг, для которых вершина v является концом. Орграф, содержащий п вершин и т дуг будем называть (n, т ) - орграфом.

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

Лемма 1 . Пусть G - произвольный (n, т ) - орграф. Тогда

Это утверждение аналогично лемме 1 из разд. 1.1; его часто называют орлеммой о рукопожатиях.

На первом занятии, вводя понятие графа, мы рассма­тривали в качестве примера состязания спортивных команд. Мы. соединяли две команды, скажем А и С, ребром АС в том случае, когда эти команды уже играли друг с другом. Однако такой граф не дает ответа на один весьма существен­ный вопрос: кто именно выиграл игру?
Этот недостаток легко может быть устранен. Если команда А выиграла у С, условимся ставить на ребре АС стрелку, направленную от А к С. Предположим, что нам известны результаты всех уже сыгранных игр, и добавим к графу рис. 1 соответствующие стрелки; пусть при этом получится граф, изображенный на рис. 58.

Рис 58.

На этом графе показано, что команда А выиграла у С, команда F проиграла А, а В вы­играла все игры - с С, Е, F и т. д.

Ребро графа называется ориентированным , если одну вершину считают началом ребра , а другую - концом .
Граф, все ребра которого ориентированы, называется ориенти рованным графом .
Одна и та же вершина ориентированного графа может служить началом для одних ребер и концом для других. Соответственно различают две степени вершины: степень выхода и степень входа.
Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер (обозначение: d+(A)).
Степенью входа вершины А ориентированного графа называ­ется число входящих в А ребер (обозначение: d-(A)).
А что, если какая-то игра окончилась вничью? Мы можем отразить ничейные результаты на графе, оставляя соответствующие ребра неориентирован­ными. При этом мы получим так называемый сме шанный граф , на котором имеются как ориенти­рованные, так и неориентированные ребра.
Путем в ориентированном графе G от А1 до Аn называется по­следовательность ориентированных ребер <А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, такая, что конец каждого предыдущего ребра совпадает с началом следующего и ни одно ребро не встречается более одного раза.

Рис. 59
Если в ориентированном графе G нашелся путь от А до В, то обратного пути от В к А может и не быть (рис. 59).
Если существует ориентированный путь от А до В, то говорят, что В достижи­ ма из А,
В графе G на рисунке 38 В достижима
из А, А не достижима из В.
Простым путем в ориентированном гра­фе называется путь, в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется ориентированным циклом.
Длиной пути называется число ребер в этом пути.
Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В. Если пути от А до В не существует, то расстояние от А до В называют бесконечным и обо­значают?. Расстояние от А до В будем обозначать S (АВ). Для графа на рисунке 38
S (АВ) = 1, S (СВ) - 2, S (ВС) = ?.
Задача 9.1.
В приморском курортном городе после установления одностороннего движения оказалось, что число улиц, по которым можно въехать на каждый перекресток, равно числу улиц, по которым можно из него выехать. Докажите, что можно предложить такой маршрут патрулирования, который начинается и оканчивается в одном месте и проходит через каждый участок улиц ровно один раз.
Решение.
Построим орграф G, задающий движение в городе.
Орграф называется связным, если от любой его вершины до любой другой можно перейти по дугам без учета их ориентации. Связный орг­раф называется эйлеровым, если в нем есть эйлеров цикл.
Теорема 12. Связный орграф является эйлеровым тогда и только тогда, когда для каждой его вершины v выполняется равенство d - (v ) = d + (v ) .
Теорема доказывается точно так же, как и теорема в задаче 4.2.
Из условия задачи следует, что для вершин построенного графа G выполняется равенство d-(v) = d+(v). Следовательно, граф G эйлеров, и эйлеров цикл определит нужный маршрут патрулирования.
Задача 9.2.
На плоскости отмечено конечное число точек. Некоторые пары то­чек являются началами и концами векторов, причем число векторов, входящих в любую точку равно числу векторов, выходящих из нее. Найдите сумму векторов.
Решение.
Точки плоскости вместе с векторами образуют орграф G.Цикл орграфа, все вершины которого различные, называется контуром.
Теорема 13. Связный орграф G эйлеров тогда и только тогда, когда G является объединением контуров, попарно не имеющих общих ребер.
Доказательство. Необходимость.Пусть G - эйлеров орграф. Рассмотрим его любую вершину u1. Выйдем из вершины u1по некоторой дуге (u1, u2).Это возможно сделать, так как орграф Gсвязный. Поскольку d-(u2) = d+(u2), то из вершины u2можно выйти по дуге (u2, u3). Орграф Gимеет конечное число вершин, поэтому, в конце концов, мы попадем в не­которую вершину w, в которой были раньше. Часть цепи, которая начинается и оканчивается в вершине w, является контуром С1. Удалим дуги кон­тура С1 из орграфа G. В получившемся орграфе G1(возможно несвязном) степени входа и выхода вершин, принадлежавших С, уменьшились на единицу, степени входа и выхода остальных вершин не изменились. Следовательно, для любой вер­шины v орграфа С1 будет выполняться равенство d-(v) = d+(v). Поэтому в орграфе G1 можно выделить контур C2 и т.д.
Достаточность доказывается путем объединения контуров в эй­леров цикл (см. доказательство теоремы в задаче 4.2).
Теорема доказана. Возможно, орграф G, задающий векторы в нашей задаче, не явля­ется связным. Применив доказанную теорему к каждой связной части орграфа, получим разбиение векторов на контуры. Сумма векторов, при­надлежащих одному контуру, равна нулю. Следовательно, сумма всех векторов равна нулю.

В предыдущих главах мы представили некоторые основные результаты теории неориентированных графов. Однако для описания некоторых ситуаций неориентированных графов недостаточно. Например, при представлении схемы уличного движения графом, ребра которого соответствуют улицам, для указания допустимого направления движения ребрам необходимо присваивать ориентацию. Другим примером является программа для ЭВМ, моделируемая графом, ребра которого представляют поток управления от одних множеств инструкций к другим. В таком представлении программы для указания направления потока управления ребрам также необходимо присвоить ориентацию. Еще одним примером физической системы, для представления которой требуется ориентированный граф, является электрическая цепь. Применения ориентированных графов и соответствующие алгоритмы рассматриваются в гл. 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.