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

Широкий класс задач из различных областей деятельности человека приводит к изучению ориентированных графов. Граф называется ори­ентированным графом (сокращенно орграфом), если на каждом из его ребер введена ориентация, т. е. указано, какая из двух инцидент­ных ребру вершин является началом, а какая — концом ребра. Ори­ентированные ребра называются дугами. Обозначать дугу с началом в вершине V и концом в вершине V] будем через V —+ 14 или У'Ш (подобно

вектору АВ, имеющему начальную точку А и конечную точку В). В отдельных случаях, когда нет необходимости конкретно указывать образующие дугу вершины, дуги орграфа могут обозначаться одним символом, например г. На схемах и чертежах дуги изображаются прямыми или кривыми линиями со стрелками. Относительно дуги тп говорят, что она исходит из вершины у и заходит в вершину ш; при этом вершина у предшествует вершине ш, а вершина ш следует за вершиной V. Например, рис. 1.1 гл.1, иллюстрирующий многоша­говый процесс, представляет, по существу, ориентированный граф.

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

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

Проиллюстрируем введенные понятия на орграфе, изображенном на рис. 3.13. В данном примере:

—               дуга 4 —> 2 исходит из вершины 4 и заходит в вершину 2;

—               вершина 3 предшествует вершинам 4 и 5;

—               вершина 2 следует за вершинами 1 и 4;

 Данный маршрут является также путем, поскольку не содержит повторяющихся вершин; — маршрут 2—>3—>5—>4—>2 является простым контуром. Как и неориентированным графам, орграфам могут быть постав­лены в соответствие матрицы. Пусть В) ~ некоторый орграф, со­держащий п вершин г'1, И'2,..., ь_п и тп дуг г_ьг₂,...,г_то. Матрицей смемсности орграфа Д) называется квадратная матрица 5 по­рядка п (по числу вершин), элементы которой определяются сле­дующим образом:

1, если вершина г;-, предшествует вершине г;_?; О, если вершина г/_г не предшествует вершине г;_?.

Матрицей инцидентности орграфа £г(У, 7?) называется мат­рица <5 размерности п х т, элементы % которой определяются сле­дующим образом:

если вершина г;_г является началом дуги г_?; если вершина г/_г является концом дуги г_г; если вершина ^ и дуга г_? не инцидентны.

Например, для приведенного на рис. 3.13 орграфа, для которого принято

VI = 1, VI = 2, ..., г>5 = 5, г_х = 1 -> 2, г₂ = 2 - 3, гз = 3 -> 4, г₄ = 3 5, г₅ = 4 2, г₆ = 5 4,

матрицы смежности и инцидентности имеют вид

 

Кроме того, орграфы могут быть заданы и списками смежности.

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

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

Рис. 3.14

Для выяснения, является ли связный орграф сетью (для орграфов, имеющих сложную структуру или заданных в виде матриц, данный вопрос не является очевидным), применяется алгоритм Фалкерсона. С помощью этого алгоритма проводится разбиение множества всех вершин орграфа на группы Л\, .7-2, ■ • •, Л, Для которых выполняются свойства:

—               вершины из первой группы 3\ не имеют предшествующих вер­шин, а вершины из последней группы .//,■ — последующих;

—               вершины из любой группы не имеют предшествующих вершин в последующих группах;

—               вершины из одной группы не являются смежными.

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

Алгоритм Фалкерсона включает следующие пункты.

1.               Начало работы алгоритма. Считаем все вершины орграфа неот­меченными и полагаем номер формируемой группы равным 1.

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

3.               Выбранные вершины относим в формируемую группу и отмечаем.

4.               Если в орграфе имеются неотмеченные вершины, то номер фор­мируемой группы увеличиваем на 1 и переходим к п. 2 алго­ритма. Если же все вершины орграфа уже отмечены, то разбиение на группы завершено. Конец работы алгоритма.

Если орграф не является сетью, то на одном из шагов алгоритма сформировать очередную группу не удастся. Работа алгоритма завер­шается «досрочно» до окончания разбиения всех вершин на группы.

Рассмотрим алгоритм Фалкерсона на примере графа, изображен­ного на рис. 3.15. Результат работы алгоритма зависит от ориентации ребра 3 — 5. Если это ребро ориентировано в направлении 3 —> 5, то применение алгоритма позволит сформировать следующие группы:

Л = {1,2}, 7₂ = {3}, -7з = {4}, = {5,6}, 7₅ = { 7};

отметим, что входы сети 1 и 2 вошли в одну группу «/і, а выходы сети 6 и 7 — в разные группы.

Если же изменить ориентацию ребра 3 — 5 на противоположную, т. е. рассмотреть дугу 5 —> 3, то алгоритм завершит работу «досрочно»: после формирования первой группы «/і = {1,2} окажется невозмож­ным сформировать следующую группу, поскольку у всех неотмеченных на данный момент вершин 3, 4, 5, 6, 7 имеются неотмеченные пред­шествующие. Орграф не является сетью, так как содержит контур 3 4 5 3.