Если представить приборы: вершины графа, а гальванические связи между ними – ребра графа, то задача размещения приборов сводится к такому изображению графа на плоскости, при котором никакие два ребра не пересекаются.
При большом числе приборов и гальванических соединений между ними задача представляется довольно сложной.
2. Основные определения
Граф G(V, X) укладывается на поверхности, если его можно на ней изобразить таким образом, что любое пересечение его ребер является вершиной графа.
Если граф укладывается на плоскости, то он называется планарным.
Граф, уложенный на плоскости называется плоским графом.
Плоский граф на плоскости определяет ее области. При этом неограниченная область называется внешней гранью графа, а остальные области – внутренние грани. Внешнюю грань обозначим S0, а внутренние S1, S2, …, Sk. На рисунке представлен планарный граф и соответствующий ему плоский граф с гранями:
Для плоских графов справедлива формула Эйлера: n + k = m + 2, где n – число вершин графа, k – число граней, m – число ребер.
Для представленного графа: число вершин равно 5, число ребер – 8, число граней – 5. проверим формулу Эйлера:
5 + 5 = 8 – 2 – равенство верно.
Вопрос о распознавании планарности графа являлся в свое время серьезной математической проблемой, которую на сегодняшний день удалось решить.
Для формулировки этого важного результата введем два понятия.
Элементарное стягивание ребра. Элементарным стягиванием ребра {v, w} называется отождествление вершин v и w:
 |
Два графа G' и G'' называютя гомеоморфными, если они могут быть получены из некоторого графа с помощью последовательности элементарных стягиваний его ребер.
Выше приведенные графы гомеоморфны. Никакие другие вершины стягивать нельзя, так как это повлечет за собой отождествление ребер, что недопустимо.
Сформулируем необходимое и достаточное условие планарности графа.
Для того чтобы граф G(V, X) был планарным, необходимо и достаточно, чтобы он не содержал подграфа, гомеоморфного либо полному графу К5, либо графу К3,3 .
Граф К5
3. Алгоритм плоской укладки графа
Изложим алгоритм, с помощью которого устанавливается возможность получения плоской укладки графа, если он является планарным, и невозможность укладки в противном случае.
Пусть даны граф G(V, X) и его подграф 
Этот подграф называется начальным и должен быть планарным (в качестве такого подграфа можно взять простой цикл, простую цепь). Через G'(V', X') обозначим подграф графа G, порожденный удалением из него вершин 
(напомним, что при удалении вершины удаляются и все инцидентные ей ребра). Пример представлен на рисунке.
Граф G' может быть не связным, т. е. иметь Р компонент связности. Обозначим компоненты связности G'i(V’i, X’i), где i =1 – р. Множество ребер X’I дополним всеми ребрами, инцидентными в G вершинам V’i, а множество вершин V’i дополним соответствующими вершинами этих ребер и назовем их контактными вершинами. Полученный таким образом подграф 
назовем куском графа G относительно подграфа 
Объединением всех кусков графа должен быть исходный граф G. На рисунке представлены куски данного графа, относительно подграфа
Грань, определяемую графом 
на плоскости, и кусок назовем совместимыми, если все контактные вершины куска являются граничными точками этой грани.
Алгоритм плоской укладки графа состоит в последовательном присоединении к любому уже уложенному подграфу графа G простой цепи L, обе концевые вершины которой - единственные ее вершины, принадлежащие уложенному графу. Выбор простой цепи осуществляется после того, как будет проанализирована совместимость каждого куска и граней уложенного графа. При анализе совместимости возможны варианты:
1. кусок совместим с единственной гранью;
2. каждый кусок совместим более чем с одной гранью;
3. существует кусок, с которым каждая грань уложенного подграфа несовместима.
В первом случае в куске находится простая цепь, обе концевые вершины которой (и только они) являются вершинами уложенного подграфа, и эта цепь укладывается в совместимую грань.
Во втором случае простая цепь выбирается в любом из кусков и выполняется такое же действие, как и в первом случае.
Третий случай говорит о том, что граф G не является планарным.
Рассмотрим работу алгоритма при получении плоской укладки графа, изображенного на рисунке
1. В качестве начального планарного подграфа возьмем простой цикл v1 v2 v5 v6 v1 , и обозначим его . Удалим все вершины этого подграфа и получим подграф G'(V', X') c двумя компонентами связности:
2. Получим два куска, дополняя каждую компоненту связности графа G'(V', X'), и добавляя ребро {v1, v5}:
|
3. Начинаем плоскую укладку. Простой цикл образует две грани:
|
|
Заполним таблицу:
Вершины куска | Контактные вершины | Совместимые грани |
v1, v5 | v1, v5 | S0, S1 |
v3, v7, v2, v6 | v2, v6 | S0, S1 |
v4, v1, v2, v5 | v1, v2, v5 | S0, S1 |
4. Все куски совместимы с двумя гранями. Возьмем ребро {v1, v5} и уложим его в грани S0, которая разбивается на две грани S2 и S3.
Вершины куска | Контактные вершины | Совместимые грани |
v3, v7, v2, v6 | v2, v6 | S1 |
v4, v1, v2, v5 | v1, v2, v5 | S1, S2 |
5. Рассмотрим первый кусок, который совместим только с гранью S1. Выбираем в нем простую цепь v2 v7 v3 v6 и укладываем ее в грани S1 , которая разбивается на две грани S4 и S5.
Вершины куска | Контактные вершины | Совместимые грани |
v7, v6 | v7, v6 | S4, S5 |
v4, v1, v2, v5 | v1, v2, v5 | S2 |
6. Первый кусок совместим с двумя гранями. Поместим ребро {v6, v7} в грань S4, она разбивается на две новые грани S6 и S7.
Вершины куска | Контактные вершины | Совместимые грани |
v4, v1, v2, v5 | v1, v2, v5 | S2 |
7. Имеем один кусок, который совместим с единственной гранью. Выделяем в нем простую цепь v5 v4 v1 и укладываем ее в грань S2, разбивая ее на грани S8 , S9.
Вершины куска | Контактные вершины | Совместимые грани |
v4, v2 | v4, v2 | S8 |
8. Последний кусок совместим с гранью S8 , значит граф планарный. Укладываем ребро {v2, v4} в грань S8, заканчивая плоскую укладку графа.
Контрольные вопросы
Какой граф называется планарным и плоским? Какие области определяет плоский граф на поверхности? Какие вершины называются контактными? Что такое кусок графа? В каком случае кусок графа и грань графа совместимы. Какое равенство справедливо для планарного графа? Сформулировать алгоритм плоской укладки графа.ЛЕКЦИЯ 22
ТЕМА: ОРИЕНТИРОВАННЫЙ ГРАФ
ПЛАН:
Основные понятия Способы задания ориентированного графа Путь в ориентированном графе Связность. Компоненты связности в орграфеГлавная
Основные понятия
Напомним определение ориентированного графа:
Непустое множество V = {v1, v2,…,vn} и набор Х упорядоченных пар объектов (vi, vi+1) , где viÎV, vi+1ÎV, называется ориентированным графом и обозначается D(V, X).
Пары х = (v, w) называются дугами и изображаются на диаграмме следующим образом:
v– начало дуги х, w – конец дуги х.
Говорят: дуга исходит из v и заходит в w.
Пусть х – дуга. Если v конец или начало дуги, то v и х инцидентны.
Вершины v и w смежны, если (v, w) Î X.
Для ориентированного графа аналогично определяются понятия: петли, кратные дуги, псевдограф, мультиграф, граф.
Рассмотрим понятия: полустепень исхода и полустепень захода:
Полустепенью исхода вершины v называется число d+(v) дуг орграфа D, исходящих из вершины v.
Полустепенью захода вершины v называется число d-(v) дуг орграфа D, заходящих в вершину v.
Замечание: вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в d+(v), так и в d-(v).
Для орграфа, представленного на рисунке найти полустепени захода и исхода:
|
d+(u1) = 2
d-(u1) = 0
d+(u2) = 2
d-(u2) = 3
d+(u3) = 0
d-(u3) = 1
d`+(u4) = 0
Найдем суммы степеней исходов и сумму степеней заходов:
еd+(u) = 2 + 2 + 0 + 0 = 4;
еd-(u) = 0 + 3 + 1 = 4 .
В данном графе 4 ребра. Замечаем, что еd+(u) = еd+(u) = m .Действительно, для орграфа справедливо утверждение:
Для любого ориентированного графа выполняется равенство
еd+(u) = еd+(u) = m,
где m – количество дуг.
Способы задания ориентированного графа
Ориентированный граф как и неориентированный можно задать с помощью его диаграммы или в матричной форме.
Матрица инцидентности графа.
Пусть задан граф D(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.
Матрицей инцидентности графа D(V, X) называется матрица размера m´ n, элементы которой определяются следующим образом:
Замечание: если хj – петля для vi, то bij – любое число, отличное от 1, -1 и 0.
Матрица инцидентности однозначно определяет структуру графа, что позволяет читать всю необходимую информацию о графе. Информация о дугах считывается по строкам, о вершинах – по столбцам.
Составим матрицу инцидентности для орграфа из предыдущего примера. Это матрица размера 4´ 4:
Элемент b32 = 2 показывает, что дуга х3 является петлей. Найдем полустепени исхода и захода, например, для вершины v2 : полустепень исхода - d+(v2) = 2, т. к. в соответстующем этой вершине столбце одна «-1» и еще учитываем петлю; полустепень захода - d-(v2) = 3, т. к в столбце две единицы и петля.
Матрица смежности
Пусть задан граф D(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.
Матрицей смежности графа D(V, X) называется квадратная матрица n´ n, элементы которой определяются следующим образом:
k – количество дуг, соединяющих вершины vi и vj.
Составим матрицу смежности для орграфа. Это квадратная матрица размера 4´ 4:
Матрица смежности ориентированного графа не симметрична относительно главной диагонали, как матрица смежности для неорграфа.
3. Путь в ориентированном графе
Определение: Путем, соединяющим вершины v1 и vk+1 , называется последовательность v1x1v2x2…vkxkvk+1 , где k³ 1, vi Î V, xiÎ X, дуга xi соединяет вершины vi с вершиной viВершина v1 (v нач)– начало пути (начальная вершина), vk+1 (v кон)– конец пути (конечная вершина). Остальные вершины называются внутренними вершинами пути.
Найдем какой-либо путь из v1 в v3 : v1x1v2x3v2x4v3 .
Допускается краткая запись пути. В том случае, если в пути нет кратных дуг, то составляют последовательность только из вершин.
Если в пути есть кратные дуги, то в последовательность включают начальную вершину, дуги и конечную вершину. Или пользуются комбинированной записью: в последовательность включают все вершины и только кратные ребра.
Перепишем наш путь, использую комбинированную запись: v1x1v2v2v3. В последовательность включено только кратное ребро x1 .
Длиной пути l называется количество дуг в нем.
В нашем пути 3 дуги, значит его длина l =3.
Познакомимся с видами путей.
Если vнач = vкон, то путь называется замкнутым.
Если vнач ¹ vкон, то путь называется незамкнутым.
Виды незамкнутых путей:
Незамкнутый путь, в котором все дуги попарно различны называется цепью.
Цепь, в которой все вершины попарно различны называется простой цепью.
Виды замкнутых путей:
Замкнутый путь, в котором все дуги попарно различны называется контуром.
Контур, в котором все вершины попарно различны называется простым контуром.
Заметим, что петля являются простым контуром.
Составим различные пути для приведенного выше орграфа :
v1x1v2x3v2x4v3 – незамкнутый путь, являющийся цепью (в нем все дуги попарно различны);
v2x3v2 – простой контур;
v1x2v2x4v3 – простая цепь (все вершины и дуги попарно различны).
Для графа D(V, X) справедливы утверждения:
Из любого контура можно выделить простой контур.
Из любого незамкнутого пути можно выделить простую цепь с теми же начальной и конечной вершинами.
4. Связность. Компоненты связности в орграфе
Вершина w орграфа D достижима из вершины v, если:
а) v = w ;
б) существует путь из v в w.
Орграф называется сильно связным, если для любых его вершин v, w существует путь из v в w, и из w в v.
Орграф называется односторонне связным, если для любых двух вершин хотя бы одна достижима из другой.
Пример:
u2
u1 сильно связный граф
u3
u2
u1 односторонне связный граф
u3
Псевдографом, ассоциированным с ориентированным псевдографом D(V, X), называется псевдограф G(V, X0), в котором Х0 получается заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w}.
Пример: Дан орграф D(V, X):
Для него G (V, X0):
Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.
В рассмотренном выше примере граф G (V, X0) связный, значит орграф D(V, X) – слабо связный.
Если орграф не является слабо связным, то он называется несвязым.
Пример:
Представленный на этом рисунке граф D(V, X) – несвязный, т. к. ассоциированный ему граф G(V, X0) – несвязный, т. к. р(G) = 2.
Компонентой сильной связности графа D называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа орграфа D.
Пример:
Этот орграф имеет две компоненты сильной связности:
 |
 |
D1 D2
Значит Р (D) = 2.
Замечание: Вершина достижима сама для себя, поэтому является сильно связным подграфом.
Орграф D(V, X) Компоненты сильной связности орграфа D(V, X)
Этот граф имеет три компоненты сильной связности.
Из определения компоненты сильной связности следует справедливость утверждений:
Пусть D1(V1, X1) – компонента сильной связности орграфа D(V, X), тогда D1 – подграф орграфа D(V, X) , порожденный множеством V1.
Пусть D(V, X) – орграф с р компонентами сильной связности: D1(V1, X1) ,…, Dр(Vр, Xр) . Тогда:
1) V = V1 È…ÈVp, X Í X1 È…È Xp ;
2) Vi ÇVj = Æ, Xi ÇXj = Æ, если i ¹ j ;
3) n(D1) +…+ n(Dp) = n(D), m(D1) +…+ m(Dp) £ m(D).
Контрольные вопросы
Сформулировать определение орграфа. Элементы орграфа. Понятие полустепени вершин. Теорема о количестве дуг орграфа. Какие существуют способы задания орграфа? Виды связностей в орграфе. Какой подграф данного графа называется компонентой сильной связности? Теорема о свойствах компонент сильной связностиЛЕКЦИЯ 23
ТЕМА: ЗАДАЧИ НА ОРИЕНТИРОВАННЫЕ ГРАФЫ
ПЛАН:
1. Поиск путей с минимальным количеством дуг
2. Минимальные пути в нагруженных орграфах
3. Порядковая функция орграфов без контуров
Главная
1. Поиск путей с минимальным количеством дуг
Путь в орграфе D(V, X) из вершины v в вершину w (v ¹ w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.
Справедливо утверждение:
Любой минимальный путь является простой цепью.
Для решения задачи поиска минимального пути, введем обозначения:
пусть D(V, X) – граф, v Î V, V1 Í V; обозначим D(v) = {wÎV|(v, w)Î X} – образ вершины v; D(V1) = 
- образ множества вершин V1 ; D-1(v) = { wÎV|(w, v)Î X} – прообраз вершины v; D-1(V1) = 
- прообраз множества вершин V1 .
Пусть D(V, X) – орграф с n ³ 2 вершинами и v и w – заданные вершины из данного графа. Причем v ¹ w. Опишем алгоритм поиска минимального маршрута в графе D (алгоритм фронта волны).
Шаг1. Помечаем вершину v индексом 0. затем помечаем вершины, принадлежащие образу вершины v, индексом 1. Множество вершин с индексом 1 обозначим FW1(v). Полагаем к =1.
Шаг 2. Если FWk(v) = Æ или выполняется к = n –1, wÏ FWk(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.
Шаг 3. Если wÏ FWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины к, и этот путь является минимальным. Последовательность вершин vw1w2…wk -1 w, где
wk-1 Î FWk-1ÇD-1(w);
wk-2 Î FWk-2ÇD-1(wk-1);
……………………….
w1 Î FW1ÇD-1(w2);
и есть искомый минимальный путь из v в w.
Шаг 4. Помечаем индексом к+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом к. Множество вершин с индексом к+1 обозначим FWk+1(v). Присваиваем к: = к+1 и переходим к шагу 2.
Множество FWk(v) называют фронтом волны к - го уровня.
Замечание: Вершины w1, w2,…w k-1 могут быть выделены неоднозначно, в случае, если существует несколько минимальных путей из v в w.
Пример: Граф задан матрицей смежности: 
Построим минимальный путь из u1 в u7. Присвоим u1 индекс 0.
1) Составим множество образов вершины u1 (поиск осуществляем по строкам)
FW1 (u1) = {u4, u5}. u4 и u5 присвоим индекс 1.
2) Ищем образы для u4 и u5, не включая сами эти вершины
FW2 (u1) = {u6};
3) FW3 (u1) = {u2, u3}
4) FW4 (u1) = {u7}.
u7 достигнута.
Построим путь:
Каждую вершину выбираем из пересечения множеств образов с индексом k – 1 и прообразов D-1 (ui) с индексом k. Включаем в путь любую вершину из этого пересечения.
Прообразы для ui – по столбцам.
FW3 (u1) З D-1 (u7) = {u2, u3} З {u2, u3} = {u2, u3}, включим в путь u3.
FW2 (u1) З D-1 (u3) = {u6} З {u2, u6} = {u6}.
Включим u6.
FW1 (u1) ÇD-1 (u6) = {u4, u5} Ç {u2, u4, u5, u7} = {u4, u5}. Включим u5.
Тогда получим путь u1 u5 u6 u3 u7. Этот путь длиной 3.
2. Минимальные пути в нагруженных орграфах
Орграф D(V, X) называется нагруженным, если на множестве дуг X определена функция, называемая весовой, ставящая в соответствие каждой дуге некоторое действительное число l(x). Значение l(x) будем называть длиной дуги х.
Обозначим какой-либо путь в орграфе D через p, тогда l(p) – длина этого пути, равная сумме длин входящих в p дуг. Заметим, что если длины всех дуг в орграфе равны 1, то длина любого пути будет равна числу дуг в этом пути. Таким образом, можно считать ненагруженный орграф нагруженным с длинами дуг, равными 1.
Путь в нагруженном орграфе D из вершины v в вершину w (v ¹ w) называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.
Длины дуг могут быть как положительными, так и отрицательными. Рассмотрим только такие орграфы, длины дуг которых есть числа l(x) > 0.
Приведем некоторые свойства минимальных путей в нагруженных орграфах:
если для любой хÎ Х l(x) > 0, то любой минимальный путь является простой цепью; если v1v2…vk – минимальный путь, то для любых номеров i и j таких, что 1£ i£ j£ k, путь vi vi+1…vj также – минимальный; если v…uw – минимальный путь среди путей из v в w, содержащих не более k + 1 дуг, то v..u – минимальный путь среди путей из v в u, содержащих не более k дуг.Рассмотрим теперь задачу поиска минимальных путей в орграфах.
Пусть D(V, X) – нагруженный орграф, n ³ 2. Введем величины lik, где i = 1, …, n, k = 1, 2…Для каждых фиксированных i и k величина lik равна длине минимального пути среди всех путей из v1 в vi (v1 - начало пути), содержащего k дуг. Если таких путей нет, то lik = ¥. Если произвольную вершину v считать путем из v в v нулевой длины, то величины lik можно ввести для k = 0, при этом l10 = 0, li0 = ¥, i = 2,…,n.
Введем также квадратную матрицу С(D) = [cij], порядка n, называемую матрицей длин дуг:
l(vi, vj) – длина дуги (vi, vj).
Для вычисления lik используем формулы:
При i = 2, …,n, k ³ 0 выполняется равенство:
lik+1 = min{ljk + cji},
1£ j £ n
где ljk – это величины всех вершин кроме i - ой, cji – это длины дуг из каждой j – ой вершины в i – ую, для которой вычисляется lik+1.
при i = 1, k ³ 0 верно равенство:
l1k+1 = min{0; min{ljk + cj1}, если нет дуг отрицательной длины, то l1k+1 = 0.
1£ j £ n
Приведем алгоритм, позволяющий по таблице величин lik, i = 1, 2,…,n, k = 0, 1, …, n – 1, определить минимальный путь в нагруженном графе D из v1 в любую достижимую вершину, причем алгоритм выделяет путь с наименьшим числом дуг.
Алгоритм носит название алгоритма Форда – Беллмана.
Шаг1. Пусть составлена таблица величин lik, i = 1, 2,…,n, k = 0, 1, …, n – 1. Если li1n-1 = ¥, то вершина vi1 не достижима из v1. Работа алгоритма заканчивается.
Шаг2. Пусть li1n-1< ¥, тогда число li1n-1 выражает длину минимального пути из вершины v1 в вершину vi1. Определим минимальное число дуг k1 ³ 1, при котором выполняется равенство li1k1 = li1n-1. Получаем, что k1 - минимальное число дуг в минимальном пути.
Шаг3. Последовательно определим номера вершин в этом пути i2, … , ik1+1:
li2k1-1 + ci2, i1 = li1k1;
li3k1-2 + ci3, i2 = li2k1-1;
………………………
lik1+10 + cik1+1 = lik11.
Пример:
Определить минимальный путь из v1 в v6 в нагруженном орграфе D, изображенном на рисунке:
Составим матрицу длин дуг графа и рядом таблицу величин lik, содержащую шесть столбцов k = 0, 1, …, 5, используя соотношения:
При i = 2, …,n, k ³ 0 выполняется равенство
lik+1 = min{ljk + cji},
1£ j £ n
при i = 1, k ³ 0 верно равенство
l1k+1 = min{0; min{ljk + cj1},
1£ j £ n
V1 | V2 | V3 | V4 | V5 | V6 | li0 | li1 | li2 | li3 | li4 | li5 | ||
V1 | ¥ | ¥ | 5 | 5 | 2 | 12 | 0 | 0 | 0 | 0 | 0 | 0 | |
V2 | ¥ | ¥ | ¥ | ¥ | ¥ | 2 | ¥ | ¥ | 7 | 5 | 5 | 5 | |
V3 | ¥ | 2 | ¥ | ¥ | ¥ | ¥ | ¥ | 5 | 3 | 3 | 3 | 3 | |
V4 | ¥ | 2 | ¥ | ¥ | ¥ | ¥ | ¥ | 5 | 4 | 4 | 4 | 4 | |
V5 | ¥ | ¥ | 1 | 2 | ¥ | ¥ | ¥ | 2 | 2 | 2 | 2 | 2 | |
V6 | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | 12 | 12 | 9 | 7 | 7 |
Первый столбец значений lik : l10= 0 (начало пути), остальные - ¥. Вся первая строка содержит нули, т. к. это начало пути и 0 – наименьшая длина из v1 в v1.
Второй столбец: li1 – это длины дуг, соединяющих v1 с другими вершинами и, начиная со второй вершины, заносим значения из первой строки матрицы длин дуг.
Третий столбец: l22 = min{0+¥, 5+2, 5+2, 2+¥, 12+¥}= 7;
l32 = min {0+5, ¥+¥, 5+¥, 2+1, 12+¥}=3;
l42 = min{0+5, ¥+¥, 5+¥, 2+2,12+¥}= 4;
l52 = min{0+2, ¥+¥,5+¥,5+¥,12+¥} = 2;
l62 = min{0+12, ¥+2,5+¥,5+¥,2+¥} = 12.
Четвертый столбец:
l23 = min{0+¥, 3+2, 4+2, 2+¥, 12+¥}= 5;
l33 = min {0+5, 7+¥, 4+¥, 2+1, 12+¥}=3;
l43 = min{0+5, 7+¥, 3+¥, 2+2,12+¥}= 4;
l53 = min{0+2, 7+¥,3+¥,4+¥,12+¥} = 2;
l63 = min{0+12, 7+2,3+¥,4+¥,2+¥} = 9.
Пятый столбец:
l24 = min{0+¥, 3+2, 4+2, 2+¥, 9+¥}= 5;
l34 = min {0+5, 5+¥, 4+¥, 2+1, 9+¥}=3;
l44 = min{0+5, 5+¥, 3+¥, 2+2,9+¥}= 4;
l54 = min{0+2, 5+¥,3+¥,4+¥,9+¥} = 2;
l64 = min{0+12, 5+2,3+¥,4+¥,2+¥} = 7.
Последний шестой столбец:
l25 = min{0+¥, 3+2, 4+2, 2+¥, 7+¥}= 5;
l35 = min {0+5, 5+¥, 4+¥, 2+1, 7+¥}=3;
l45 = min{0+5, 5+¥, 3+¥, 2+2,7+¥}= 4;
l55 = min{0+2, 5+¥,3+¥,4+¥,7+¥} = 2;
l65 = min{0+12, 5+2,3+¥,4+¥,2+¥} = 7.
Итак, минимальный путь из v1 в v6 равен 7 и содержит 4 дуги, т. к. первый раз 7 появилось в столбце li4, т. е. для вершины v6 l64 = 7.
Найдем последовательность вершин, входящих в этот путь:
l64 = 7= l23 + с26 =5+2;
l23 = 5 = l32 + с32 = 3+2;
l32 = 3 = l51 + с53 = 2+1;
l51 = l10 + с15 = 0+2.
Получили путь v1v5v3v2v6 .
3. Порядковая функция орграфа без контуров
Рассмотрим орграф D(V, X) , не содержащий контуров, и определим множества
Граф D (V, X) не содержащий контуров – бесконтурный орграф.
Определим для него множества:
V0 = {u О V | D (u) = Ж};
|
V2 = {u О V \ (V0 И V1) | D (u) Н V0ÈV1};
…………………………………….
Vr = {u О V \ И Vk | D (u) Н ÈVk},
Где D(v) – множество образов, r – наименьшее число, такое, что V \ И Vk = Ж (k = 0, 1,…, r).
V0, V1, …, Vr – уровни графа.
Уровни образуют разбиение множества вершин V, то есть
И Vk = V (k = 0,1,…,r).
Справедливо утверждение:
Пусть D(V, X) – орграф, r ³ 0, V0, …, Vr – непустые множества, удовлетворяющие (*), такие, что И Vk = V (k = 0,1,…, r). Тогда D – орграф без контуров.
Функция q (u), определенная на множестве вершин V орграфа без контуров D(V, X) и ставящая в соответствие любой вершине v Î V номер уровня, которому она принадлежит, называется порядковой функцией орграфа D (V, X).
Пример:
Разбить граф D (V, X) на уровни и изобразить в уровневом представлении.
1) Найдём вершины, не имеющие образов и присвоим номер уровня 0:
V0 = {u Î V | D (u) = Æ} = {u4, u6}. Порядковые функции для v4 и v6 равны
q (u4) = 0, q (u6) = 0.
2) Найдём вершины, образами которых являются u4 и u6:
V1 = {u ÎV \ V0 | D(u) Н {u4, u6}} = {u1, u5}. q (u1) = 1, q (u5) = 1.
3) V2 = {u ÎV \ V0 È D (u) Н {u4, u6, u1, u5}} = {u3}, q (u3) = 2.
4) Тогда V3 = {u2}, q (u2) = 3.
Итак, получили множества V0, V1, V2 и V3 такие, что их взаимное пересечение пусто, а объединение есть множество вершин V графа. Следовательно граф - без контуров.
Рассмотрим алгоритм выделения уровней орграфа D(V, X) без контуров, использующий задание графа матрицей смежности. Этот алгоритм легко реализуется на ЭВМ:
Шаг 1. Составим матрицу смежности. Образуем под этой матрицей строку l0, в i – том месте которой укажем число единиц в i – той строке матрицы. Уровень V0 образуют вершины, которым в строке l0 соответствует 0. если V = V0, то задача решена и V0 – единственный уровень орграфа D. В противном случае переходим к шагу 2.
Шаг 2. Образуем под строкой l0 строку l1, ставя под каждым нулем строки символ ´, а на любом другом i – том месте – число единиц в i – ой строке матрицы, не учитывая единицы в столбцах над символами ´ в строке l1. Уровень V1 образуют вершины, которым в строке l1 соответствует число 0. Полагаем j = 1.
Шаг 3. Пусть при некотором j ³ 1уже построены строки l0 , l1,…, lj, по которым получены множества V0, …, Vj. Если строка lj состоит из нулей и символов ´ , то задача решена и при r = j V0, …, Vr – уровни орграфа. В противном случае переходим к шагу 4.
Шаг 4. Образуем под строкой lj строку lj+1, ставя под каждым нулем и символом ´ символ ´, а на любом другом i – том месте – число единиц в i – ой строке матрицы, не учитывая единицы в столбцах над символами ´ в строке lj+1. Уровень Vj+1 образуют вершины, которым в строке lj+1 соответствует число 0. Присваиваем j : = j + 1 и переходим к шагу 3.
Решим предыдущую задачу с помощью матрицы смежности и описанного алгоритма.
Согласно полученным строкам lj:
V0 = {u4, u6},
V1 = {u1, u5},
V2 = {u3},
V3 = {u2}.
Следовательно, для данного графа количество уровней – четыре. Изобразим граф в уровневом представлении:
 |
V3 V2 V1 V0
Наряду с нахождением уровней орграфа без контуров этот алгоритм позволяет проверить наличие контуров у произвольного графа. Справедливо утверждение:
Орграф D(V, X) содержит хотя бы один контур тогда и только тогда, когда в результате применения алгоритма к графу D появляется строка lj без нулей.
Такой граф не представим в виде уровней.
Рассмотрим пример. Проверить наличие контуров в орграфе D(V, X), заданном матрицей смежности:
Применяя алгоритм, получим:
Поскольку в строке l3 нет нулей, то орграф содержит хотя бы один контур.
Контрольные вопросы
Понятие пути в орграфе. Виды путей. Какой путь называется минимальным? Алгоритм построения минимального пути в ненагруженном графе. Какой граф называется нагруженным? Как составляется матрица длин дуг? Алгоритм выделения минимального пути в нагруженном орграфе. Какой орграф называется бесконтурным? Что такое уровни бесконтурного орграфа? Определение порядковой функции бесконтурного орграфа. Алгоритм разбиения орграфа на уровни и проверки наличия контуров с помощью матрицы смежности.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
