Родичев Ю.А. Компьютерные сети - архитектура, технологии, защита

Возможных циклических маршрутов шесть: ABCDA, ACDBA,

ADBCA, ACBDA, ABDCA, ADCBA. Однако для решения задачи

достаточно сравнить длины только первых трех: ABCDA, ACDBA,

ADBCA.

Эти длины равны соответственно:

11+6+10+17=44, 13+10+9+11=43, 17+9+6+13=45.

Тем самым, кратчайшим является любой из маршрутов дли-

ной 43 - ACDBA или ABDCA.

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

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

Как было отмечено ранее, при помощи неориентированных

графов моделируются различные задачи, в которых изучаются

совокупности объектов, между парами которых установлены свя-

зи. Сопоставив каждому объекту вершину, а каждой связи ребро,

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

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

существование связи

между объектами A и B, вообще говоря, не

означает существование связи между B и A. В подобных случаях,

чтобы подчеркнуть направленный характер связей, ребра в соот-

ветствующем графе удобно наделять стрелками. Граф, на ребрах

которого расставлены стрелки, называется ориентированным

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

Орграф и его элементы

Абстрактное определение ориентированного графа (орграфа)

формулируется аналогично определению обычного графа, дан-

ному в пункте 2.1.

Ориентированным графом или орграфом G(V, Е, f) называ-

ется совокупность непустого множества V, изолированного от

него произвольного множества Е и отображения f: Е→V×V

множества Е в V×V, которое каждому элементу из Е ставит в

соответствие некоторый

элемент из V×V, т.е. упорядоченную

пару элементов из V. При этом множества V и Е называются со-

ответственно множеством вершин и множеством дуг

орграфа G(V, Е, f), а отображение f называется отображени-

ем инциденции этого орграфа.

Если f(е) =(А, В), то вершина А называется началом дуги е,

а вершина В называется концом этой дуги. Также говорят, что

дуга е идет от вершины А к вершине В.

Отличие орграфа от неориентированного графа состоит в том

что если f(e)=(A, В), то отображение инциденции f указывает не

просто пару вершин А и В, соединенных е (как это было в случае

неориентированного графа), а еще к тому же сохраняет различие

между А и В, так как пары (А, В) и (В, А) являются различными

элементами множества V

×V.

Элементами орграфа являются вершины и дуги. Орграф назы-

вается конечным, если множества вершин V и ребер Е содер-

жат конечное число элементов.

Чтобы обеспечить наглядность графического изображения

орграфа, его дуги (т.е. кривые, соединяющие соответственные

вершины) снабжаются стрелками. На рис. 2.19 приведен пример

орграфа G(V, Е, f). Этот граф имеет 5 вершин

и 12 ребер:

V={A,В,С,D,Р}, E={a

,…,a

}. Отображение инциденции f оп-

ределяется следующим образом:

f: a

→(A, B); a

→(B, C); a

→(B, P); a

→(P, C); a

→(D,

C); a7→(D, C); a

→(A, P); a

→(P, D); a

→(A, D); a

→(D, D);

→(D, D).

Каждому орграфу G можно поставить в соответствие единст-

венный неориентированный граф G

, называемый симметри-

зацией орграфа G, если каждую дугу в G, ведущую из одной

вершины в другую, заменить неориентированным ребром, соеди-

няющим ту же пару вершин. Разным орграфам может соответст-

вовать одна и та же симметризация. Процесс перехода от неори-

ентированного графа к орграфу, симметризация которого совпа-

дает с исходным графом,

называется ориентацией графа.

Вершина и дуга в орграфе называются инцидентными, если

соответствующие им вершина и ребро инцидентны в его симмет-

ризации. Две вершины в орграфе называются смежными, если

смежными являются соответствующие им вершины в его сим-

метризации. Две дуги в орграфе называются смежными, если

смежными являются два соответствующих им ребра в

его сим-

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

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

его симметризации.

Рис. 2.19. Пример орграфа

В ориентированном графе параллельные дуги бывают двух

типов – строго параллельные (одинаково ориентирован-

ные) и нестрого параллельные (ориентированные по-

разному). На рис. 2.20 дуги a и b строго параллельны, а дуги c и d

нестрого параллельны.

Рис. 2.20. Параллельные дуги

Степенью вершины орграфа называется количество ин-

цидентных ей дуг. Ясно, что степень вершины орграфа равна

степени соответствующей вершины в неориентированном графе,

который является симметризацией орграфа. Следовательно, для

ориентированного графа, точно так же, как для неориентирован-

ного, будет выполняться равенство (1.4.1) и, следовательно, орг-

раф может содержать лишь четное количество нечетных вершин.

В ориентированном графе G (V, A) дуги, инцидентные некото-

рой вершине A, можно разбить на два класса – входящие в эту

вершину и выходящие из

нее. В соответствии с этим степень

вершины расщепляется на два слагаемых: положительная и

отрицательная полустепень вершины. Положительной

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

отрицательной полустепенью называется количество дуг, выхо-

дящих из вершины.

Разность положительной и отрицательной полустепеней вер-

шины называется дефектом степени вершины. Вершина ориенти-

рованного графа называется

уравновешенной, если она име-

ет нулевой дефект степени. Ясно, что уравновешенная вершина

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

его вершины уравновешены. Сумма абсолютных величин дефек-

тов степеней всех вершин называется степенью неравно-

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

Формально изоморфизм орграфов определяется точно так же,

как и изоморфизм неориентированных графов. Ориентированные

графы G и

называются изоморфными (или равными) если

между их однотипными элементами можно установить взаимно

однозначное соответствие, сохраняющее отношение инциденции.

Заметим, что если два орграфа изоморфны, то изоморфными бу-

дут и неориентированные графы, являющиеся их симметриза-

циями. Обратное, вообще говоря, неверно. Так, на рис. 2.21 пред-

ставлены три попарно неизоморфных графа с изоморфными сим

метризациями.

Два ориентированных графа являются изоморфными, если

изоморфны их симметризации и, кроме того, граничные точки

соответствующих дуг упорядочены одинаково.

Изоморфные орграфы имеют одинаковые комбинаторные

свойства. В частности, при изоморфизме соответствующие вер-

шины имеют одинаковые положительные и одинаковые отрица-

тельные полустепени, изоморфизм сохраняет строгую (и нестро-

гую) параллельность дуг.

Рис. 2.21. Изоморфизм орграфа

Рассмотрим ориентированный граф G(V, Е, f) с множеством

вершин V={A

,…,A

,…}, множеством дуг E{a

,…,a

,…} и

отображением инциденции f.

Ориентированным маршрутом (или ормаршру-

том) длины k называется последовательность из k (не обязатель-

но различных) дуг а

,…,a

графа G, если для каждой пары со-

седних дуг этой последовательности конечная вершина преды-

дущей дуги является начальной вершиной последующей. Первая

и последняя вершины называются соответственно начальной

и конечной точкой ормаршрута. Остальные вершины последо-

вательности называются промежуточными точками этого

ормаршрута. Также говорят, что ормаршрут а

,…,a

. соединяет

вершины А

и А

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

конечная точки совпадают. В противном случае ормаршрут на-

зывается незамкнутым. Любая дуга в орграфе является не-

замкнутым ормаршрутом длины 1, соединяющим свои граничные

вершины. Любая петля в орграфе – это замкнутый ормаршрут

длины 1.

Любой ормаршрут (замкнутый или незамкнутый) в орграфе G

однозначно определяет неориентированный маршрут

в соответ-

ствующей симметризации G

. Однако, если некоторая последова-

тельность ребер в неориентированном графе G

образует мар-

шрут, то это вовсе не означает, что в орграфе G (для которого G

служит симметризацией) соответствующая последовательность

дуг определяет ормаршрут. Действительно, рассмотрим орграф G

и его симметризацию G

, (см. рис. 2.22). Последовательность дуг

, a

в G не образует ормаршрута, но в симметризации G

им со-

ответствующая последовательность ребер а

, a

, образует неори-

ентированный маршрут длины 2, соединяющий вершины A и B.

Рис. 2.22. Орграф и его симметризация

Ориентированный незамкнутый маршрут называется путем

(или упорядоченной цепью), если в нем нет повторяющих-

ся дуг; если же в незамкнутом ормаршруте нет повторяющихся

вершин (а значит – и повторяющихся дуг), то он называется

простым путем.

Ориентированный замкнутый маршрут называется конту-

ром (или упорядоченным циклом), если в

нем нет повто-

ряющихся дуг; если же в замкнутом ормаршруте нет повторяю-

щихся промежуточных вершин (а значит – и повторяющихся

дуг), то он называется простым контуром.

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

симметризация G

является связным графом в смысле определе-

ния из пункта 2.1.8.

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

имеет один важный недостаток в приложениях. Если интерпре-

тировать дугу орграфа как прямую связь между объектами, а путь

из дуг – как сложную связь между начальным и конечным объек-

тами, то связность орграфа, в общем случае,

не будет означать,

что между любыми двумя объектами существует связь, как это

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

связи в ориентированном графе имеют «направленный» характер

и существование связи между объектами A и В не гарантирует

существование обратной связи между В и А.

В этой связи представим граф автомобильных дорог. Если

этот граф связен, то от любого перекрестка к любому другому

можно доехать по дорогам. Предположим теперь, что на всех до-

рогах разрешено движение только в одном

направлении. Граф

дорог в этом случае получит ориентацию. Он останется связным

орграфом, но теперь может случиться так, что от какого-то пере-

крестка к некоторому другому будет невозможно доехать, двига-

ясь по дорогам только в разрешенных направлениях. Чтобы су-

ществовала «направленная» связь между любой парой перекрест-

ков, необходимо потребовать, чтобы

в орграфе дорог для любой

пары вершин A и В существовал путь, ведущий от А к В, и путь,

ведущий от В к А. Это требование к орграфу является более

сильным, чем связность, и называется сильной связностью.

Итак, орграф называется сильно связным, если для любой

пары различных вершин A и B

существует путь, ведущий от A к B,

и существует путь, ведущий от B к A. Если граф сильно связен, то

он является связным. Обратное, вообще говоря, не верно.

Ориентированный граф называется сильно k-связным,

если для любой пары различных вершин A и В существует по

крайней мере k путей из А в

В, которые не имеют общих вершин

(а следовательно, и дуг), за исключением А и В. Если орграф

сильно k-связен, то его симметризация также является k-связным

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

ратное, вообще говоря, не верно. Если орграф автомобильных

дорог сильно k-связен, то от

любого перекрестка к любому дру-

гому можно проехать не менее чем k различными способами, не

нарушая при этом правила одностороннего движения.

2.3. Сети

В приложениях граф обычно интерпретируется как сеть, а его

вершины называют узлами. Рассмотрим несколько характер-

ных задач. При принятии важных решений для выбора наилуч-

шего направления действий из имеющихся вариантов использу-

ется так называемое дерево решений, представляющее собой

схематическое описание проблемы принятия решений. С деревь-

ями связана одна из проблем минимального соединения, внешне

напоминающая задачу о коммивояжере, но значительно проще

разрешаемая (для решения этой проблемы построены эффектив-

ные алгоритмы). Имеется п городов – А

, А

, ..., А

, которые нуж-

но связать между собой сетью дорог. Стоимость сооружения до-

роги, соединяющей города A

и A

, известна и равна C(A

, A

). Ка-

кой должна быть сеть дорог, связывающая все города, чтобы

стоимость ее сооружения была минимальной?

Граф наиболее дешевой соединяющей сети непременно дол-

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

один цикл. При удалении любого из звеньев этого цикла стои-

мость сети уменьшится, а города все еще

останутся соединен-

ными. Тем самым, число ребер искомого графа должно быть

равным n-1.

Алгоритм (план реализации)

На первом шаге связываем два города с наиболее дешевым

соединяющим звеном е

. На каждом следующем шаге добавляем

самое дешевое из звеньев е

(если имеется несколько звеньев с

одинаковой стоимостью, выбираем любое из них), в результате

присоединения которого к уже построенным звеньям найденная

сеть удлиняется еще на одно звено, но никакого цикла не образу-

ется. При поиске добавляемого звена надо перебирать все ребра,

имеющие общую вершину с уже построенной сетью. Последний

шаг алгоритма

имеет номер п-1. Стоимость строительства полу-

ченной сети минимальна и равна

c(е

)+с(е

)+ ...+c(е

n-1

Пример 1. Пусть, например, нужно соединить города A, B, C

и D. Стоимость строительства дорог, соединяющих любые два

города, известна и в условных единицах представлена в таблице:

А В С D

А – 11 13 12

В 11 – 6 9

С 13 6 – 10

D 12 9 10 –

Рис. 2.24. Граф сети

Сеть дорог минимальной стоимости состоит из 3 (4-1=3)

звеньев и строится так: сначала выбирается самый дешевый уча-

сток дороги – ВС (его цена

равна 6), затем он удлиня-

ется на самый дешевый из

оставшихся – BD (его цена

равна 9). И на последнем,

третьем шаге вновь выби-

рается самый дешевый (но

так, чтобы

не образовалось

никакого цикла) – АВ (его

цена равна 11) (рис. 2.23).

Таким образом, стоимость

строительства равна 26

(6+9+11).

С теорией графов связана задача выбора кратчайшего пути

(маршрута) до узлов сети. Допустим, дана сеть, каждое ребро

которой помечено числом, равным его длине. Требуется найти

кратчайший маршрут, ведущий от выделенного узла к каждому

из узлов

сети. На практике алгоритмы выбора кратчайшего (оп-

тимального) пути решают специальные устройства, называемые

маршрутизаторами, автоматически по заданному алгоритму, ли-

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

выбирается не только длина

пути, но и другие параметры

(пропускная способность,

скорость и другие). Алгоритм

решения этой задачи состоит

из двух частей. Покажем, как

он работает, на следующем

примере.

Пример 2. Рассмотрим сеть,

заданную на рис. 2.24, с выде-

ленным узлом 1.

Рис. 2.23. Граф соединения городов

Прямой ход алгоритма

1-й шаг. Все узлы, которые соединены с выделенным узлом 1

одним ребром, метятся так, как это показано на рис. 2.25 – первое

число в метке равно расстоянию от помеченного узла до узла 1.

Ребро, связывающее узлы 1 и 3, является кратчайшим маршрутом

от узла 1 к узлу 3 (любой другой маршрут от узла 1 к узлу 3

длиннее), и поэтому

узлу 3 приписывается постоянная метка

(15,1). Таким образом, по окончании 1-го шага узлы 1 и 3 имеют

постоянные метки, узлы 2 и 4 – временные метки, а узлы 5, б и 7

никаких меток не имеют (рис. 2.26).

Замечание. При получении постоянной метки узел 3 выделя-

ется так же, как и узел 1.

Рис. 2.25. Шаг 1 (начало)

Рис. 2.26. Шаг 1 (конец)

2-й шаг. Отбираются все узлы, которые соединены с узлом 3

одним ребром и не имеют постоянных меток. Это узлы 2, 4 и 6.

Сравнивая длины маршрутов 1-2 и 1-3-2, замечаем, что длина

первого (20) меньше длины второго (15+10=25). Поэтому метка

(20,1) узла 2 остается неизменной.

Сравнивая длины маршрутов 1-4 и 1-3-4, замечаем, что длина

первого (25) больше длины второго (15 + 8 = 23).

Поэтому вре-

менная метка (25,1) узла 4 меняется на метку (23,3). Узел 6 полу-

чает метку (45,3).

Замечание. Первое число в метке указывает длину маршрута

от узла 1, а второе – номер предшествующего узла.

Ребро, связывающее узлы 1 и 2, является кратчайшим мар-

шрутом от узла 1 к узлу 2 (любой другой маршрут от узла 1 к уз-

лу 2 длиннее), и поэтому

узлу 2 приписывается постоянная метка

Родичев Ю.А. Компьютерные сети - архитектура, технологии, защита

Подождите немного. Документ загружается.