Имя материала: Динамическое программирование в экономических задачах

Автор: Лежнёв А. В.

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

Широкий класс задач из различных областей деятельности человека приводит к изучению ориентированных графов. Граф называется ориентированным графом (сокращенно орграфом), если на каждом из его ребер введена ориентация, т. е. указано, какая из двух инцидентных ребру вершин является началом, а какая — концом ребра. Ориентированные ребра называются дугами. Обозначать дугу с началом в вершине v и концом в вершине w будем через v —► w или vw (подобно вектору АВ, имеющему начальную точку А и конечную точку В) В отдельных случаях, когда нет необходимости конкретно указывать образующие дугу вершины, дуги орграфа могут обозначаться одним символом, например т. На схемах и чертежах дуги изображаются прямыми или кривыми линиями со стрелками. Относительно дуги vw говорят, что она исходит из вершины v и заходит в вершину w при этом вершина v предшествует вершине w, а вершина w следует за вершиной v. Например, рис. 1.1 гл.1, иллюстрирующий многошаговый процесс, представляет, по существу, ориентированный граф.

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

V[0]    ->  ... ->V[fc],

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

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

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

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

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

последовательность вершин 1^2^3^5-^4 образует маршрут с началом в вершине 1 и концом в вершине 4; в соответствии с принятым соглашением об обозначениях для данного маршрута

V[0] = 1,    v[l] = 2'    •••> и[4]=4-

Данный маршрут является также путем, поскольку не содержит повторяющихся вершин;

маршрут 2—>3-^5—>4->2 является простым контуром.

Как и неориентированным графам, орграфам могут быть поставлены в соответствие матрицы. Пусть G(V, R) — некоторый орграф, содержащий п вершин vi,v2,..-,vn и m дуг гъ Г2,..., г т. Матрицей смежности орграфа G(V,R) называется квадратная матрица S порядка п (по числу вершин), элементы Sij которой определяются следующим образом:

Sij —

1,   если вершина Vi предшествует вершине Vj-

О,     ЄСЛИ ВерШИНа Vi  Не Предшествует  ВерШИНе Vj.

Матрицей инцидентности орграфа G(V, R) называется матрица Q размерности n х т, элементы qij которой определяются следующим образом:

1,   если вершина Vi является началом дуги г у -1,   если вершина г>; является концом дуги г у О,   если вершина Vi и дуга fj не инцидентны.

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

vi = 1,   v2 = 2,    ...,   v5 = 5, ri = 1 -»• 2,   ?2 = 2 -* 3,   f3 = 3 4, f4 = 3 -»• 5,   f5 = 4 -+ 2,   f6 = 5 -»• 4,

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

 

" 0

1

0

0

0 "

 

1

0

0

0

0

0

0

0

1

0

0

 

-1

1

0

0

-1

0

0

0

0

1

1

,  Q =

0

-1

1

1

0

0

0

1

0

0

0

 

0

0

-1

0

1

-1

0

0

0

1

0

 

0

0

0

-1

0

1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ji = {l,2},   J2 = {3},   J3 = {4},   J4 = {5,6},   J5 = {7};

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

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

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |