Носырева Л.Л. Дискретная математика. Графы - файл n1.doc

приобрести
Носырева Л.Л. Дискретная математика. Графы
скачать (2117.2 kb.)
Доступные файлы (1):
n1.doc3305kb.17.04.2010 11:37скачать

n1.doc

  1   2   3   4
Иркутский государственный технический университет

Факультет Кибернетики

Кафедра Автоматизированных систем


Носырева Л.Л.
ДИСКРЕТНАЯ МАТЕМАТИКА


Конспективный материал к лекциям


(рабочий вариант)
Для специальностей АСУ, МЭИ, ИП, АСОК

Часть 4

Графы
Иркутск 2006

Введение.

Теория графов, как раздел дискретной математики, имеет многочисленные предметные интерпретации. Среди дисциплин и методов дискретной математики теория, графов и особенно алгоритмы на графах находят наиболее широкое примене­ние в программировании. Как показано в разделе 7.5, между понятием графа и понятием отношения, рассмотренным в главе 1, имеется глубокая связь — в сущности это равнообъемные понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь явное предпочтение? Дело в том, что тео­рия графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества (см. замечание в подразделе 1.5.1 и далее). Однако независимое определение понятия отношения удобнее — введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений тео­рии графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа (подраздел 7.1.4). Само название «граф» подразумевает наличие графической ин­терпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказатель­ства и сложные формулы.

Эта глава практически полностью посвящена описанию языка теории графов.

1. Определения графов

Как это не удивительно, но для понятия "граф" нет общепризнанного единого определения. Разные авторы, особенно применительно к разным приложениям, называют «графом» очень похожие, но все-таки различные объекты. Здесь используется терминология [26], которая была выбрана из соображений макси­мального упрощения определений и доказательств.

История теории графов

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

1. Задача о Кёнuгсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 7.1). Эта задача была решена Эйлером в 1736 году.



Рис. 1. Иллюстрация к задаче о Кенигсбергских мостах

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Про­вести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 7.2). Эта задача была решена Куратовским в 1930 году.



Рис.2. Иллюстрация к задаче о трех домах и трех колодцах

3. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом (рис. 7.3).



Рис..3. Иллюстрация к задаче о четырех красках

Основное определение

Графом G(U, V) называется совокупность двух множеств — непустого множества U (множества вершин) и множества V бинарного отношения, определённого на множестве U.

Число вершин графа G обозначим n, а число ребер - m:
Смежность

Пусть u1, u2 — вершины, e = (v2, v1) — соединяющее их ребро. Тогда вершина u1 и ребро е инцидентны, вершина u2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Множество вершин, смежных с вершиной u, называется множеством смежности вершины u и обозначается Г+(u):

ЗАМЕЧАНИЕ

Если не оговорено противное, то подразумевается Г+ и обозначается просто Г.

Диаграммы

Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.

Пример

На рис. 7.4 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины u1 и u2, u2 и u3, u3 и u4, u4 и u1, u2 и u4 смежны, а вершины u1 и u3 не смежны. Смежные ребра: e1 и е2, е2 и е3, е3 и е4, е4 и e1, e1 и е5, е2 и е5, е3 и е5, е4 и е5. Несмежные ребра: e1 и е3, е2 и е4.



Рис.4. Диаграмма графа

Виды графов

1. Если элементами множества Е являются упорядоченные пары, то граф назы­
вается ориентированным (или орграфом). В этом случае элементы множества
V называются узлами, а элементы множества Е — дугами.

2. Если элементом множества Е может быть пара одинаковых (не различных)
элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф назы­вается мулътшрафом.

4. Если элементами множества Е являются не обязательно двухэлементные, а
любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.

5.Если задана функция F: V?М и/или F: Е?М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

Изоморфизм графов

Говорят, что два графа G1(V1,E1) и G2(V2,E2) изоморфны (обозначается G1 ~ G2), если существует биекция h: V1 ? V2, сохраняющая смежность:

e1 = (u,v) ∊ Е1<=>e2 = (h(u),h(v)) ∊ E2,

Изоморфизм графов есть отношение эквивалентности. Действительно, изомор­физм обладает всеми необходимыми свойствами:

рефлексивность: G ~ G, где требуемая биекция суть тождественная функция;

симметричность: если G1 ~ G2 с биекцией h, то G2 ~ G1 с биекцией h-1;

транзитивность: если g1 ~ G2 с биекцией h и G2 ~ G3 с биекцией g, то
g1 ~ G3 с биекцией g∙h.

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма (см. раздел 2.2).

Элементы графов

После рассмотрения определений, относящихся к графам как к цельным объек­там, естественно дать определения различным составным элементам графов.

Подграфы

Граф G'(V’, E') называется подграфом графа G(V, E) (обозначается G’ G), если V’ V и/или Е'  Е.

Если V’ = V, то G' называется остовным подграфом G.

Если V’ V &Е'  E&(V’? V  Е' ? Е), то граф G' называется собственным подграфом графа G.

Подграф G'(V',E'} называется правильным подграфом графа G(V,E), если G' содержит все возможные ребра G:

u,v∊V’ (u,v) ∊ E(u,v) ∊E'.

Правильный подграф G'(V’, E') графа G(V, E) определяется подмножеством вер­шин V’.

Валентность

Количество ребер, инцидентных вершине v, называется степенью (или валент­ностью) вершины v и обозначается d(v):

 ∊ V0?d()?p - l, d() = Г+().

Обозначим минимальную степень вершины графа G через ?(G), а максималь­ную — через ∆(G):

 

Если степени всех вершин равны k, то граф называется регулярным степени k:

?(G) = (G) = k.

Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

Пример



Рис. 7.7. Диаграмма регулярного графа степени 3

Если степень вершины равна 0 (то есть d(v) = 0), то вершина называется изолиро­ванной. Если степень вершины равна 1 (то есть d(v) = 1), то вершина называется концевой, или висячей.

Для орграфа число дуг, исходящих из вершины v, называется полустепенъю исхо­да, а входящих — полустепенью захода. Обозначаются эти числа, соответственно, d-(v) и d+(v).

ТЕОРЕМА (Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер:

= 2q.

доказательство

При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого. 

Маршруты, цепи, циклы

Маршрутом в графе называется чередующаяся последовательность вершин и ребер v0,e1,v1,e2,v2,...,ek,vk, в которой любые два соседних элемента инцидентны.

ЗАМЕЧАНИЕ

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

Если 0 = k, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи 0,el,... ,ek,k вершины v0 и vk называются концами цепи. Говорят, что цепь с концами и и v соединяет вершины и и v. Цепь, соединяющая вершины и и v, обозначается (и, v). Очевиднб, что если есть цепь, соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.

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

Пример

В графе, диаграмма которого приведена на рис. 7.8:

1.1, 3, 1, 4 — маршрут, но не цепь;

2. 1, 3, 5, 2, 3, 4 — цепь, но не простая цепь;

3. 1, 4, 3, 2, 5 — простая цепь;

4. 1, 3, 5, 2,3, 4, 1 — цикл, но не простой цикл;

5. 1, 3, 4, 1 — простой цикл.



Рис.8. Маршруты, цепи, циклы

Расстояние между вершинами

Длиной маршрута называется количество ребер в нем (с повторениями). Если маршрут М= v0, e1,1,e2,v2,..., ek, k то длина М равна k (обозначается |М| = k).

Расстоянием между вершинами и и v (обозначается d(u,v)) называется длина кратчайшей цепи (u,v), а сама кратчайшая цепь называется геодезической.

ЗАМЕЧАНИЕ -

Если  и, v, то по определению d(u, v).

Диаметром графа G (обозначается D(G)) называется длина длиннейшей геоде­зической.

Множество вершин, находящихся на одинаковом расстоянии n от вершины v (обозначение D(v,n)), называется ярусом:

D(v,u).

Связность

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

Отношение связанности вершин является эквивалентностью. Классы эквива­лентности по отношению связанности называются компонентами связности гра­фа. Число компонент связности графа G обозначается k(G). Граф G является связным тогда и только тогда, когда k(G) = 1. Если k(G) > 1, то G — несвязный граф. Граф, состоящий только из изолированных вершин (в котором k(G) = p(G) и r(G) = 0), называется вполне несвязным.

Виды графов и операции над графами

В данном разделе рассматриваются различные частные случаи графов и вводят­ся операции над графами и их элементами. Заметим, что не все из используемых обозначений операций над графами являются традиционными и общепринятыми.

Тривиальные и полные графы

Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с k вершинами, обозначается Сk.

Пример

С3 — треугольник.

Граф, в котором каждая пара вершин смежна, называется полным. Полный граф с р вершинами обозначается Кр, он имеет максимально возможное число ребер: 

Полный подграф (некоторого графа) называется кликой (этого графа).

Двудольные графы

Двудольный граф (или биграф, пли четный граф) — это граф G(V,E), такой что множество V разбито на два непересекающихся множества V1 и V2 (V1  V2 = V & V1  V2 = ), причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из |V2). Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если |V1| = m и |V2| = п, то полный двудольный граф обозначается Km,n.

Пример

На рис. 7.9 приведена диаграмма графа К3,3.

Рис..9. Диаграмма графа Кз,з

ТЕОРЕМА Граф является двудольным тогда и только тогда, когда все его про­стые циклы, имеют четную длину.

доказательство

[Необходимость.] От противного.

Пусть G(V1,V2;E) — двудольный граф, и 1, 2,..., 2k+1, 1 — простой цикл не­четной длины. Пусть 1 ∊ V1, тогда 2 ∊ V2, 3 ∊ V1, 4 ∊ V2,... , 2k+1 ∊ V1. Имеем: 1, 2k+1 ∊ V1 и (1, 2k+1)∊ E, что противоречит двудольности.

[Достаточность.] Не ограничивая общности, можно считать, что G — связный граф, поскольку каждую компоненту связности можно рассматривать отдельно. Разо­бьем множество V на V1 и V2 с помощью следующей процедуры:

Вход: граф G(V,E).

Выход: Множества V1 и V2 — доли графа.

select  ∊ V { произвольная вершина }

V1: =  { в начале первая доля содержит , ... }

V2 : =  { ... а вторая пуста }

for и ∊ V \ {} do

if d(, u] — четно then

V1: = V1 + u { помещаем вервину u в первую долю }

else

V2 : = V2 +u {помещаем вершину u во вторую долю }

end if

end for

Далее от противного. Пусть есть две вершины в одной доле, соединенные ребром. Пусть для определенности u, ? ∊ V2 и (u, ?) ∊ Е.

Рассмотрим геодезические , u и , ? (здесь  — та произвольная вершина, ко­торая использовалась в алгоритме построения долей графа). Тогда длины | , u| и | , ? | нечетны. Эти геодезические имеют общие вершины (по крайней мере, вершину ). Рассмотрим наиболее удаленную от  общую вершину геодезиче­ских , u и , ? и обозначим ее ' (может оказаться так, что  = '). Имеем: | ’, u| + | ’, ? | = | , u| + | , ? -2| , ’| -четно, и ',...,u,?,...,' -простой цикл нечетной длины, что противоречит условию. Если же , ? ∊ V1, то длины | , u| и | , ? | четны и аналогично имеем: ',...,u,?,...,' — простой цикл нечетной длины.

Направленные орграфы и сети

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

ОТСТУПЛЕНИЕ---------------------------------------------------------------------------------------------------------------

Название «турнир» имеет следующее происхождение. Рассмотрим спортивное соревно­вание для пар участников (или пар команд), где не предусматриваются ничьи. Пометим вершины орграфа участниками и проведем дуги от победителей к побежденным. В таком случае турнир в смысле теории графов — это как раз результат однокругового турнира в спортивном смысле.

--------------------------------------------------------------------------------------------------------------------------------------

Если в орграфе полустепень захода некоторой вершины равна нулю (то есть d+() = 0), то такая вершина называется источником, если же нулю равна полу­степень исхода (то есть d-() = 0), то вершина называется стоком. Направлен­ный орграф с одним источником и одним стоком называется сетью.

Операции над графами

Введем следующие операции над графами:

1. Дополнением графа G(V1,E1) (обозначение — (V1,E1)) называется граф G(V2,E2), где V2= V1& E2= 

2. Объединением графов G1(V1,E1) и G2(V2,E2) (обозначение - G1(V1,E1)G2(V2,E2), при условии V1  V2 = , E1 E2 = ) называется граф G(V,E), где C.

Пример

 = С3  С3.

3. Соединением графов G1(V1,E1) и G2(V2,E2)

(обозначение – G1(V1,E1) + G2(V2, Е2), при условии V1V2= , E1 E2 =  называется граф G(V,E), где

V = V1V2&E= E1 E2{e= (1, 2)| 1∊Vl&2∊V2}.

Пример

=  + .

4. Если V1V2, то пересечением G1G2 графов G1 и G2 называется граф (V1V2, E1E2).

5. Кольцевой суммой G1  G2 называется граф (V1V2,E1E2), где E1E2= (E1\E2)(E2\E2)

Пример

Для графов G1({a1, a2, a3},{[ a1, a2],( a2, a3)}) и G2({a1, a2, a4},{( a1, a2),( a4, a1)}) (рис. 4.12) найдём G1G2, G1G2, G1G2. По определению имеем G1G2=({a1, a2, a3},{[ a1, a2],( a2, a3), ( a4, a1)}), G1G2=({a1, a2},{( a1, a2)}), G1G2==({a1, a2, a3, a4},{( a2, a1),( a2, a3) ,( a4, a1)}).



Рис. 4.12

6. Произведением G1G2 графов G1 и G2 называется граф, (V1V2,E), в котором ((a1, b1),( a2, b2))∊R тогда и только тогда, когда a1= a2 и (b1, b2)∊R2 , или b1= b2 и (a1, a2)∊R1.

Пример

На рис. 4.14 изображено произведение G1G2 графов G1=({1,2},{(1,1),(2,1)}) и G2=({a,b,c},{[a,b],(b,c)}).



Рис. 4.14

7. Удаление вершины v из графа G1(V1,E1) (обозначение — G1(V1,E1) - v, при
условии v ∊ V1) дает граф G2(V2,E2), где V2 = V1\{v}&E2= E1\{e = (v1,v2) | v1 = v  v1 = v} .

Пример

C3-v = K2.

8. Удаление ребра е из графа G1(V1,E1) (обозначение — G1(V1,E1) - e, при усло­вии е ∊ E1) дает граф G2(V2, E2), где V2=V1&E2=E1\{e}.

Пример

К2-e = .

9.Добавление вершины v в граф G1(V1,E1) (обозначение — G1(V1,E1) + v, при условии v ∊ V1) дает граф G2(V2,E2), где V2=V1{v}&E2=E1.

Пример

K2 + v = K2  K1.

10. Добавление ребра е в граф G1(V1,E1) (обозначение — G1(V1,E1) + е, при усло­вии е ∊ E1) дает граф G2(V2, E2), где V2=V1&E2=E1{e}.

11. Стягивание подграфа А графа G1(V1,E1) (обозначение — G1(V1,E1) /A, при условии А  V1, v∊V1) дает граф G2(V2,E2), где V2=(V1\A){v}&

E2=E1\{e=(u,w)|u∊Aw∊A}{e=(u,v)|u∊Г(A)\A}.

Пример

K4/C3=K2.

12. Размножение вершины v графа G1(V1,E1) (обозначение — G1(V1,E1)?v при условии v∊V1, v’V1) дает граф G2(V2, E2), гдеV2 : = V1  {v’} & E2 : = E1{(v, v')}{е = (u,v')|u∊ Г+(v) } .

Пример K2?v=C3.

13. Операция отождествления вершин v и u графа G(V,E) состоит в удалении из графа G вершин v и u и присоединении новой вершины v’, дуг (v’,c), если (v, c)∊E или (u,c)∊E, и дуг (c,v’), если (c,v)∊E или (c, u)∊E: (V\{v,u}){v’},(E\{(c,d)|c=v или d=v, или c=u, или d=u}){(v’,c)|(v,c)∊E, или (u,c)∊E}{(c,v’)|(c,a)∊E, или (c,u)∊E}.

Говорят, что построенный граф получается из графа G отождествлением вершин v и u. В случае, когда v и u соединены дугой, операцию отождествления вершин v и u называют стягиванием дуги (v,u).

Пример

Из графа G, показанного на рис. 4.10, добавлением вершины 5 образуется граф G1, добавлением дуги (3,1) – граф G2, удалением дуги (3,2) – граф G3, удалением вершины 2 – граф G4, отождествлением вершин 1 и 4 – граф G5, стягиванием дуги (2,3) – граф G6.



Рис. 4.10.

Представление графов в ЭВМ

Следует еще раз подчеркнуть, что конструирование структур данных для пред­ставления в программе объектов математической модели — это основа искус­ства практического программирования. Мы приводим четыре различных базовых представления графов. Выбор наилучшего представления определяется требова­ниями конкретной задачи. Более того, при решении конкретных задач исполь­зуются, как правило, некоторые комбинации или модификации указанных пред­ставлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.

Требования к представлению графов

Известны различные способы представления графов в памяти компьютера, кото­рые различаются объемом занимаемой памяти и скоростью выполнения опера­ций над графами. Представление выбирается, исходя из потребностей конкрет­ной задачи. Далее приведены четыре наиболее часто используемых представле­ния с указанием характеристики n(р, q) — объема памяти для каждого предста­вления. Здесь р — число вершин, a q — число ребер.

ЗАМЕЧАНИЕ

Указанные представления пригодны для графов и орграфов, а после некоторой модифи­кации также и для псевдографов, мультиграфов и гиперграфов.



Рис.10 Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров

Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10.

Матрица смежности

Представление графа с помощью квадратной булевской матрицы

М : array [l..p,l..p] of 0..1,

отражающей смежность вершин, называется матрицей смежности, где



Для матрицы смежности n(p,q) = О(р2).

Пример

 

Матрица инциденций

Представление графа с помощью матрицы H : array [l..p, l..q] of 0..1 (для оргра­фов H : array [l..p, l..g] of —1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа



а для ориентированного графа



Для матрицы инциденций n(p,q) = O(pq).

Пример

 

. Списки смежности

Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей Г : array [l..p] of ? N на списки смеж­ных вершин (элемент списка представлен структурой N : record v : l..p; n :? N end record), называется списком смежности. В случае представления неориенти­рованных графов списками смежности n(p,q) = O(p+2q), а в случае ориентиро­ванных графов n(р, q) = О(р + q).

Пример

Списки смежности для графа G и орграфа D представлены на рис.7.11.



Рис. 7.11. Списки смежности для графа G (слева) и орграфа D (справа)

7.4.5. Массив дуг

Представление графа с помощью массива структур Е : array [l..p] of record b,e: l..p end record, отражающего список пар смежных вершин, называется мас­сивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).

Пример

Представление с помощью массива ребер (дуг) показано в следующей таблице (для графа G слева, а для орграфа D справа).

b

е

b

е

1

2

1

2

1

4

2

3

2

3

2

4

2

4

4

1

3

4

4

3

. Обходы графов

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

Алгоритм 7.1. Поиск в ширину и в глубину

Вход: граф G(V, Е), представленный списками смежности Г.

Выход: последовательность вершин обхода.

for v ∊ V do

x[v]: =0{ вначале все вершины не отмечены}

end for

select v ∊ V{ начало обхода — произвольная вершина }

v ? Т{ помещаем v в структуру данных Т ... }

x[v] : = 1{... и отмечаем вершину v }

repeat u? Т{ извлекаем вершину из структуры данных Т ... }

yield u{ ... и возвращаем ее в качестве очередной пройденной вершины }

for w ∊ Г(u) do

if x[w] =0 then

w ? Т{ помещаем w в структуру данных Т ... }

x[w]: = 1{ ... и отмечаем вершину w }

end if

end for

until Т = 

Если Т — это стек (LIFO — Last In First Out), то обход называется поиском в глубину. Если Т — это очередь (FIFO — First In First Out), то обход называется поиском в ширину.

Пример

В следующей таблице показаны протоколы поиска в глубину и в ширину для графа, диаграмма которого приведена на рис. 7.12. Слева в таблице протокол поиска в глубину, а справа — в ширину. Предполагается, что начальной является вершина 1.

u

Т

u

Т

1

2,4

1

2,4

4

2,3

2

4,3

3

2

4

3

2



3





Рис..12. Диаграмма графа к примеру обхода в ширину и в глубину

ТЕОРЕМА Если граф G связен (и конечен), то поиск в ширину и поиск в глубину обойдут все вершины по одному разу

доказательство

[Единственность обхода вершины.] Обходятся только вершины, попавшие в Т. В Т попадают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вершина будет обойдена не более одного раза.

[Завершаемость алгоритма.] Всего в Т может попасть не более р вершин. На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов.

[Обход всех вершин.] От противного. Пусть алгоритм закончил работу, и вер­шина w не обойдена. Значит, w не попала в Т. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с w, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после завершения алгоритма). Но G связен, значит, существует путь (v,w). Следовательно, вершина v не отмечена. Но она была отмечена на первом шаге!

СЛЕДСТВИЕ • Пусть (u 1 , . . . , ui , . . . , uj , . . . , uр) – обход (то есть последовательность вершин) при поиске в ширину. Тогда i 1, ui) d(ui, uj).

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

СЛЕДСТВИЕ Пусть (u1 , . . . , ui, . . . , uр) – обход при поиске в глубину. Тогда

i1 d(u 1, ui)ip.

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

СЛЕДСТВИЕ Пусть (u1 , . . . , ui, . . . , uр) – обход при поиске в ширину, а D(u1, 1),D(u1, 2), ... — ярусы графа относительно вершины u1. Тогда

i1.

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

СЛЕДСТВИЕ Пусть (u1 , . . . , ui, . . . , uр) — обход при поиске в ширину, a (v1 , . . . , vj, . . . , vр) — обход при поиске в глубину, где ui=vj. Тогда в среднем i =2j.

Другими словами, поиск в глубину в среднем вдвое быстрее, чем поиск в ширину

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

Целью этого, заключительного раздела данной главы является установление свя­зи теории графов с другими разделами дискретной математики.

Графы и отношения

Любой орграф G(V, E) с петлями, но без кратных дуг, задает бинарное отношение Е на множестве V, и обратно. А именно, пара элементов принадлежит отношению (а, b) ∊ Е  V  V тогда и только тогда, когда в графе G есть дуга (а, b).

Полный граф соответствует универсальному отношению. Граф (неориентирован­ный) соответствует симметричному отношению. Дополнение графов есть допол­нение отношений. Изменение направления всех дуг соответствует обратному от­ношению. Гиперграф соответствует многоместному отношению и т. д.

ОТСТУПЛЕНИЕ -

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

Достижимость и частичное упорядочение

В качестве примера связи между орграфами и бинарными отношениями рассмо­трим отношения частичного порядка с точки зрения теории графов.

Вершина u в орграфе G(V, E) достижима из вершины v, если существует путь из v в u. Путь из v в u обозначим .

Отношение достижимости можно представить матрицей Т : array [l..p,l..p] of 0..1, где T[i,j] = 1, если вершина vj достижима из вершины vi, и T[i,j] = 0, если вершина vj недостижима из вершины vi.

Рассмотрим отношение строгого частичного порядка w, которое характеризуется следующими аксиомами:

1. антирефлексивность: v ∊ V ¬(v w v);

2. транзитивность: u,v,w (v w w & w w u  v w u);

3. антисмметричность: u,v ¬(u w v&v w u).

Отношению строгого частичного порядка w V  V можно сопоставить граф G(V, Е), в котором а w b  (а, Ь) ∊ Е.

ТЕОРЕМА Если отношение Е есть строгое частичное упорядочение, то орграф G(V, E) не имеет контуров.

доказательство

От противного. Пусть в G есть контур. Рассмотрим любую дугу (a,b) в этом контуре. Тогда имеем а w b, но b w а по транзитивности, что противоречит строгости упорядочения.

ТЕОРЕМА Если орграф G(V,E) не имеет контуров, то достижимость есть строгое частичное упорядочение.

доказательство

[Антирефлексивность.] Нет циклов, следовательно, нет петель, следовательно, достижимость антире­флексивна.

[Транзитивность..] Если существуют пути из v в w и из w в u, то существует и путь из v в u.
Следовательно, достижимость транзитивна.

[Антисиметричность.] Пусть достижимость — это не строгое упорядочение. Тогда u,v uwv&vwu,
то есть существует путь из v в u и из u в v. Следовательно, существует контур , что противоречит условию. 

ТЕОРЕМА Если орграф не имеет контуров, то в нем есть вершина, полустепенъ захода которой равна 0.

доказательство

От противного. Пусть такой вершины нет, тогда для любой вершины найдется вершина, из которой есть дуга в данную вершину. Следовательно, имеем контур против направления стрелок. 

ЗАМЕЧАНИЕ

Эта теорема позволяет найти минимальный элемент в конечном частично упорядоченном множестве, который требуется в алгоритме топологической сортировки (алгоритм 1.7). А именно, минимальный элемент — это источник, то есть вершина, которой в матрице смежности соответствует нулевой столбец.

. Транзитивное замыкание

Если Е — бинарное отношение на V, то транзитивным замыканием Е+ на V будет отношение достижимости на орграфе G(V, E).

ТЕОРЕМА Пусть М — матрица смежности орграфа G(V, Е). Тогда Mk[i,j] = 1 в том и только в том случае, если существует путь длиной k из вершины vi, в вершину vj.

доказательство

Индукция по k. База: k = 1, М1 = М — пути длины 1. Пусть Mk-1 содержит пути длины k - 1. Тогда 

то есть путь длины k из вершины i в вершину j существует тогда и только тогда, когда существуют вершина l, такая что существует путь длины k - 1 из i в l и дуга (l,j), то есть 

Если Т — матрица достижимости, то очевидно, что .

Трудоемкость прямого вычисления по этой формуле составит О(р4). Матрица достижимости Т может быть вычислена по матрице смежности М алгоритмом Уоршалла (алгоритм 1.11) за О(р3).

Комментарии

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

Классическими учебниками по теории графов являются книги [2] и [23]. Первая является библографической редкостью, а последняя монография переиздавалась в нашей стране и является образцовой по глубине и широте охвата материала и одновременно по ясности и лаконичности изложения. Терминология и обозна­чения книги [23] взяты за основу в данном учебнике. Книга [23], хотя и имеет сравнительно небольшой объем, содержит большое число прекрасных упраж­нений'и различные сведения справочного характера. В меньшей степени в ней представлены программистские аспекты теории графов.

Существуют и другие доступные учебники по теории графов: [6, 21]. Послед­няя книга вполне доступна даже неподготовленному читателю, имеет небольшой объем, но в то же время вполне достаточна для первоначального знакомства. Раз­делы, посвященные теории графов, как правило, присутствуют во всех учебниках по дискретной математике, хотя такие разделы, по естественным причинам, не отличаются полнотой охвата материала.

Особого упоминания заслуживают книги [11] и [5]. Содержание этих книг аб­солютно точно соответствует их названиям и является необходимым для про­граммиста дополнением к классическим монографиям типа [23]. Эти источники, особенно [11], в значительной мере повлияли па отбор материала для данного учебника.

Единственный в этой главе алгоритм 7.1 носит настолько общеизвестный ха­рактер, что трудно указать его источник. Идея этого алгоритма лежит в осно­ве огромного числа конкретных алгоритмов на графах. Как правило, эта идея предполагается заранее известной читателю, и изложение сразу погружается в технические детали применения общей концепции поиска в ширину и в глуби­ну для решения конкретной задачи. В то же время свойства алгоритма поиска, приведенные в виде следствий к теореме, обосновывающей алгоритм 7.1, хотя и являются вполне тривиальными, не всегда осознаются практическими програм­мистами при решении задач. Именно поэтому представляется важным предпо­слать обсуждению конкретных алгоритмов на графах изложение общей идеи в предельно простой и рафинированной форме.

Упражнения

7.1. Построить пример графов G1 и G2, для которых p1 = р2, q1 = q2, 1 = 2, 1 = 2, но G1 G-2 (кроме примера подраздела 7.1.6).

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

7.3. Задача Рамсея. Доказать, что среди любых 6 человек есть либо 3 попарно знакомых, либо 3 попарно незнакомых.

7.4. Рассмотрим матрицу смежности ребер Q : array [1..q, l..q] of 0..1, где



Является ли матрица смежности ребер Q представлением в ЭВМ графа G(V,E)?

7.5. Описать в терминах теории графов отношение эквивалентности на конечном множестве.


Связность

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

Компоненты связности

В русском языке есть как слово «компонент» мужского рода, так и слово «компо­нента» женского рода, оба варианта допустимы. Современная языковая практика склоняется к использованию мужского рода, и мы ей следуем в остальной части книги. Однако исторически сложилось так, что «компонента связности» имеет женский род, и в этом случае мы подчиняемся традиции.

. Объединение графов и компоненты связности

Напомним, что если граф G состоит из одной компоненты связности (то есть fe(G) = 1), то он называется связным. В связном графе любые две вершины со­единены (простой) цепью.

ТЕОРЕМА Граф связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

доказательство

Необходимость. От противного. Пусть k(G) = 1 и граф G состоит из двух ком­понент, то есть

где Vi П V2 = 0, ei П Е2 = 0, Vi ^ 0, V2 ^ 0. Возьмем vl е Vi, v2 & V2. Тогда 3{t>i,v2) vi Ђ Vikv2 Ђ V2. В этой цепи Эе = (a,b) а Ј Уг &Ь Ђ V2. Но тогда е g ei, e g Е2, следовательно, е g E. Достаточность. От противного. Пусть fc(G) > 1. Тогда 3 w, v -d (и, v). Следователь­но, вершины и, v принадлежат разным компонентам связности. Положим gi -
компонента связности для и, a G2 — все остальное. Имеем G = gi U G2.

ЗАМЕЧАНИЕ

Таким образом, несвязный граф можно всегда представить как объединение связных ком­понент. Эти компоненты можно рассматривать независимо. Поэтому во многих случаях можно без ограничения общности предполагать, что рассматриваемый граф связен.

Точки сочленения

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

ЛЕММА В любом нетривиальном графе есть (по крайней мере) две вершины, которые не являются точками сочленения

доказательство

Например, это концы диаметра.

Оценка числа ребер через число вершин и число компонент связности

Инварианты p(G), q(G) и k(G) не являются независимыми.

ТЕОРЕМА Пусть р — число вершин, q — число ребер, k — число компонент связ­ности графа. Тогда

доказательство

1. р — k ^ q. Индукция по р. База: р = 1, g = 0, k = 1. Пусть оценка верна для всех графов с числом вершин меньше р. Рассмотрим граф G, p(G] = р. Удалим в G вершину v, которая не является точкой сочленения: G' : = G — v. Тогда если v — изолированная вершина, то р' — р - 1, k' = k - 1, q' = q. Имеем р — k = р' — k' ^ q' = q. Если v — не изолированная вершина, то р' = р — 1, k' = k, q' < q. Имеем: р-k^l+p'-k'^l + q'^q.

2 - q ^ (p— k)(p— fc+l)/2. Метод выделения «критических» графов. Число ребер q графа с р вершинами и k компонентами связности не превосходит числа ребер в графе с р вершинами и k компонентами связности, в котором все компонен­ты связности суть полные графы. Следовательно, достаточно рассматривать только графы, в которых все компоненты связности полные. Среди всех гра­фов с р вершинами и k полными компонентами связности наибольшее число ребер имеет граф

fc-i

Kp.k+1 U

Действительно, пусть есть две компоненты связности gi и G2, такие что 1 < pi = p(Gi) ^ Р2 = р(съ). Если перенести одну вершину из компонен­ты связности gi в компоненту связности G2, то число ребер изменится на Д(pi — 1) = Р-2 ~ Pi + 1 > 0. Следовательно, число ребер возросло. Таким образом, достаточно рассмотреть случай

k-l

Но при этом

k-l

q(Kp_k+1 U U Ki) = (р - k + 1)(р - k + 1 - 1)/2 + 0 = (р - k)(p -k + l)/2. П

СЛЕДСТВИЕ Если q > (р - 1)(р - 2)/2, то граф связен.

доказательство

Рассмотрим неравенство (р-1)(р-2)/2 < g < (p-fc)(p-fc + l)/2 при различных значениях fc.

/с = 1 (р - 1)(р - 2)/2 < (р - 1)р/2 выполняется,

fc = 2 (р- 1)(р-2)/2 < (р-2)(р- 1)/2 не выполняется,

/с = 3 (р- 1)(р-2)/2 < (р-3)(р-2)/2 не выполняется

и т. д. П

Вершинная и реберная связность

При взгляде на диаграммы связных графов (сравните, например, рис. 7.9 и 8.1) возникает естественное впечатление, что связный граф может быть «более» или «менее» связен. В этом разделе рассматриваются некоторые количественные ме­ры связности.

Мосты и блоки

Мостом называется ребро, удаление которого увеличивает число компонент связ­ности. Блоком называется связный граф, не имеющий точек сочленения.

Пример

В графе, диаграмма которого представлена на рис. 8.1:

вершины и, v — точки сочленения, и других точек сочленения нет;

ребро х — мост, и других мостов нет;

правильные подграфы {а, Ь, и}, {a,u,w}, {a,b,u,w}, {c,d,v}, {e,f,v} — блоки,
и других блоков нет.

А е /



Рис. 8.1. Точки сочленения, мосты и блоки

Если в графе, отличном от К2, есть мост, то есть и точка сочленения. Концы всякого моста (кроме висячих вершин) являются точками сочленения, но не всякая точка сочленения является концом моста.

ТЕОРЕМА Пусть G(V, Е) — связный граф и v е V. Тогда следующие утверждения эквивалентны:

v — точка сочленения;

3u, wGVu^w&V (u,w)G v 6 (u,w);

3U,W UC\W = 0&UUW = У\{г>}&Уие UVweW V(u,w)G we (u,w)G.

доказательство

1=>3: Рассмотрим G — v. Этот граф не связен, k(G — v) > 1, следовательно, G — v имеет (по крайней мере) две компоненты связности, то есть

V \ {v} = U U W,

где U — множество вершин одной из компонент связности, a W •- все остальные вершины.

Пусть и Ј U, w Ђ W. Тогда -d (и, u>)G_v. Но k(G) — 1, следовательно, 3 (u,w)G , и значит, V(u,w)G v 6 (u,w)G. 3=>2: Тривиально.

•2=4-1: Рассмотрим G - v. Имеем: -^3(u,w)G_v. Следовательно, k(G - v) > 1,
откуда v — точка сочленения.

ТЕОРЕМА Пусть G(V,E) — связный граф и х е Е. Тогда следующие утвержде­ния эквивалентны:

l.a;— мост;

2. х не принадлежит ни одному простому циклу

3 и, w 6 V V (и, w)G x e (u,

доказательство

Упражнение 8.2

Меры связности

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

Пример

x(G) = 0, если G несвязен;

x(G) = 1, если G имеет точку сочленения;

х(Кр] = р — 1, если Кр — полный граф.

Граф G называется k-связным, если x(G) = /с.

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

A(G) — 0, если G несвязен;

полный граф. 5(G).

A(G) = 1, если G имеет мост;

= р - 1, если Кр

ТЕОРЕМА x(G) ^ A(G)

доказательство

х ^ А: Если А = 0, то х = 0. Если А = 1, то есть мост, а значит либо есть точка сочленения, либо G = К2. В любом случае х = 1. Пусть теперь А > 2. Тогда удалив А - 1 ребро, получим граф G', имеющий мост (и, v). Для каждого из удаляемых А — 1 ребер удалим инцидентную вершину, отличную от и и v. Если после такого удаления вершин граф несвязен, то х ^ А — 1 < А. Если связен, то удалим один из концов моста — и или v. Имеем х ^ А.

А ^ 6 : Если 6 = 0, то А = 0. Пусть вершина v имеет наименьшую степень: d(v) = 6. Удалим все ребра, инцидентные v. Тогда А ^ 6.

Теорема Менгера

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

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

Непересекающиеся цепи и разделяющие множества

Пусть G(V, Е) — связный граф, и и v — две его несмежные вершины. Две цепи (и, v} называются вершинно -непересекающимися, если у них нет общих вершин, отличных от и и v. Две цепи (и, v} называются реберно-непересекающимися, если у них нет общих ребер. Если две цепи вершинно не пересекаются, то они и реберно не пересекаются. Множество вершинно-непересекающихся цепей (и, v) обозначим через P(u,v)..

Р(ц, v) : = {(и, v) \ (и, v)l 6 Р & (и, v)2 е Р =» (и, у)г П (и, v)2 = {и, v}} .

Множество S вершин (и/или ребер) графа G разделяет две вершины unv, если и и v принадлежат разным компонентам связности графа G - S. Разделяющее множество ребер называется разрезом. Разделяющее множество вершин для вер­шин и и v обозначим S(u,v).

ЗАМЕЧАНИЕ -

Если и т v принадлежат разным компонентам связности графа G, то \Р(и, v)\ = 0 и \S(u,v)\ = 0. Поэтому без ограничения общности можно считать, что G — связный граф.

Теорема Менгера в «вершинной форме»

ТЕОРЕМА (Менгера) Пусть и и v — несмежные вершины в графе G. Наимень­шее число вершин в множестве, разделяющем и и v, равно наибольшему числу вершинно-непересекающихся простых (и, v}-цепей:

max \P(u, v)\ = min \S(u, v)\.

замечание

Пусть G — связный граф, и вершины и и v несмежны. Легко видеть, что |Р| < |5|. Действи­тельно, любая (и, г>)-цепь проходит через 5. Если бы |Р| > \S\, то в S была бы вершина, принадлежащая более чем одной цепи из Р, что противоречит выбору Р. Таким образом, VP V5 |Р| ^ |5|. Следовательно, max|P| ^ min|5|. Утверждение теоремы состоит в том, что в любом графе существуют такие Р и S, что достигается равенство |Р| = |5|.

доказательство

Пусть G — связный граф, и и v — несмежные вершины. Совместная индукция по р и д. База: наименьший граф, удовлетворяющий условиям теоремы, состоит из трех вершин u,w,v и двух ребер (u,w) и (w,v). В нем P(u,v) = (u,w,v) •и S(u,v) = {w}. Таким образом, \P(u,v)\ = \S(u,v)\ = 1. Пусть утверждение теоремы верно для всех графов с числом вершин меньше р и/или числом ребер меньше q. Рассмотрим граф G с р вершинами и q ребрами. Пусть u,v&V,u,v-не смежны и S — некоторое наименьшее множество вершин, разделяющее и и v, га: = |S|. Рассмотрим три случая.

1. Пусть в 5 есть вершины, несмежные с и и несмежные с v. Тогда граф G — S со­стоит из двух нетривиальных графов gi и G%. Образуем два новых графа Gu и Gv, стягивая нетривиальные графы gi и G2 к вершинам и и'г>, соответственно: Gu : = G/d, Gv : = G/G2 (рис. 8.2).

S S S



Рис. 8.2. Доказательство теоремы Менгера, случай 1

S по-прежнему является наименьшим разделяющим множеством для и и v как в Gu, так и в Gv. Так как gi и G2 нетривиальны, то Gu и С„ имеют мень­ше вершин и/или ребер, чем G. Следовательно, по индукционному предполо­жению в Gu и в Gv имеется п вершинно-непересекающихся простых цепей. Комбинируя отрезки этих цепей от 5 до г) и от и до 5, получаем п вершинно-непересекающихся простых цепей в G.

2. Пусть все вершины S смежны с и или с v (для определенности пусть с и), и среди вершин S есть вершина w, смежная одновременно с и и с v (рис. 8.3).



Рис. 8.3. Доказательство теоремы Менгера, случай 2

Рассмотрим граф G': = G-w. В нем S \ {w} - разделяющее множество для и и v, причем наименьшее. По индукционному предположению в G' имеется |5\{и>}| = п— 1 вершинно-непересекающихся простых цепей. Добавим к ним цепь (u,w,v). Она простая и вершинно не пересекается с остальными. Таким образом, имеем п вершинно-непересекающихся простых цепей в G

3. Пусть теперь все вершины 5 смежны с и или с v (для определенности пусть с ы), и среди вершин 5 нет вершин, смежных одновременно с вершиной и и с вершиной v. Рассмотрим кратчайшую (и, г>}-цепь (u,wi,w2,... ,v}, wi e S, w2 ф v (рис. 8.4).



Рассмотрим граф G': = G/{wi,w2}, полученный из G склейкой вершин w\
и w2 в вершину w\. Имеем w2 $ S, в противном случае цепь (u,W2,...,v}
была бы еще более короткой. Следовательно, в графе G' множество S по-
прежнему является наименьшим, разделяющим и и v, и граф G' имеет (по
крайней мере) на одно ребро меньше. По индукционному предположению в G'
существуют п вершинно-непересекающихся простых цепей. Но цепи, которые
не пересекаются в G', не пересекаются и в G. Таким образом, имеем п вершино-
непересекающихся простых цепей в G.
Варианты теоремы Менгера

Теорема Менгера представляет собой весьма общий факт, который в разных фор­мулировках встречается в различных областях математики. Комбинируя вер­шинно- и реберно-непересекающиеся цепи, разделяя не отдельные вершины, а множества вершин, используя инварианты х и А, можно получить множество результатов «типа теоремы Менгера». Например:

ТЕОРЕМА Для любых двух несмежных вершин и и v графа G наибольшее число реберно-непересекающихся (и, v)-цепей равно наименьшему числу ребер в (u,v)-разрезе.

ТЕОРЕМА Чтобы граф G был k-связным, необходимо и достаточно, чтобы лю­бые две несмежные вершины были соединены не менее чем k вершинно-непересе­кающимися простыми цепями.

Другими словами, в любом графе G любые две несмежные вершины соединены не менее чем x(G) вершинно-непересекающимися простыми цепями.

Теорема Холла

Теорема Холла, устанавливаемая в этом разделе, имеет множество различных применений и интерпретаций, с рассмотрения которых мы и начинаем ее изло­жение.

. Задача о свадьбах

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

8.4.2. Трансверсаль

Пусть 5 = {Si,...,Sm} — семейство подмножеств конечного множества Е. Sf. не обязательно различны и могут пересекаться. Системой различных предста­вителей S (или трансверсалъю 5) называется подмножество С = {ci,...,cto} из m элементов множества Е, таких что Ck Ђ 5*,. В каком случае существует трансверсаль?

ЗАМЕЧАНИЕ

С является множеством, а потому все элементы С различны, откуда и происходит назва­ние «система различных представителей».

Совершенное паросочетание

Паросочетанием (или независимым множеством ребер) называется множество ребер, в котором никакие два не смежны. Независимое множество называется максимальным, если никакое его надмножество не является независимым.

Пусть G(Vi,Vz,E) — двудольный граф. Совершенным паросочетанием из V\ в V2 называется паросочетание, покрывающее вершины У\. В каком случае существу­ет совершенное паросочетание из V\ в V2?

ЗАМЕЧАНИЕ -

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

Теорема Холла — формулировка и доказательство

Вообще говоря, задачи 8.4.1, 8.4.2 и 8.4.3 — это одна и та же задача. Действитель­но, задача 8.4.1 сводится к задаче 8.4.3 следующим образом. Vi — множество юно­шей, V2 — множество девушек, ребра — знакомства юношей с девушками. В таком случае совершенное паросочетание — искомый набор свадеб. Задача 8.4.2 сводит­ся к задаче 8.4.3 следующим образом. Положим Vi: = S, V2: = E, ребро (Sb6») существует, если e.i Ђ Sk. В таком случае совершенное паросочетание — искомая трансверсаль. Таким образом, задачи 8.4.1, 8.4.2 и 8.4.3 имеют общий ответ: в том и только том случае, когда

(юношей \ / знакомы с

подмножеств в совокупности содержат
вершин из Vi у у смежны с

(

девушками элементов вершинами из V2

что устанавливается следующей теоремой.

ТЕОРЕМА (Холла) Пусть G(Vi,V2,E) — двудольный граф. Совершенное паросо­четание из Vi в V2 существует тогда и только тогда, когда V А с V\ \А\

доказательство

Необходимость. Пусть существует совершенное паросочетание из Vi в V2. Тогда в Г (Л) входит \А\ вершин из V2 парных к вершинам из А и, возможно, еще что-то. Таким образом, \А\ ^ Г(А)|.

Достаточность. Добавим в G две новые вершины и и v, так что и смежна со всеми вершинами из Vi, a v смежна со всеми вершинами из V2. Совершенное паросочетание из Vi в V2 существует тогда и только тогда, когда существуют |Vi| вершинно-непересекающихся простых (u, v) цепей (рис. 8.5). Ясно, что \P(u,v}\ < ^ |Vi| (так как Vi разделяет и и v).



Рис. 8.5. Иллюстрация к доказательству теоремы Холла

По теореме Менгера max \P(u, v)\ = min \S(u, v)\ = \S\, где 5 — наименьшее мно­жество, разделяющее вершины и и v. Имеем |5| < |Vi|. Покажем, что |5| > |Vi|. Пусть 5 = A U В, А с Vi, В с V2. Тогда r(Vj \ А) с В. Действительно, если бы F(Vi \A)(ЈB, то существовал бы «обходной» путь (u,vi,v2,v), и S не было \\В\.бы разделяющим множеством для и и v. Имеем: |Vi \ А\ Следовательно, |5| = \А\ + \В\ ^ \А\ + \Уг \А\ = |V"i|.

Потоки в сетях

Рассмотрим некоторые примеры практических задач.

Пример

Пусть имеется сеть автомобильных дорог, по которым можно проехать из
пункта А в пункт В. Дороги могут пересекаться в промежуточных пунктах.
Количество автомобилей, которые могут проехать по каждому отрезку дороги
в единицу времени, не безгранично, оно определяется такими факторами, как
ширина проезжей части, качество дорожного покрытия, действующие ограни­
чения скорости движения и т. д. (обычно это называют «пропускной способно­
стью» дороги). Каково максимальное количество автомобилей, которые могут
проехать из пункта А в пункт В без образования пробок на дорогах (обычно
это называют «автомобильным потоком»)? Или же можно поставить другой
вопрос: какие дороги и насколько нужно расширить или улучшить, чтобы уве­
личить максимальный автомобильный поток на заданную величину?

Пусть имеется сеть трубопроводов, соединяющих пункт А (скажем, нефтепро­
мысел) с пунктом В (скажем, нефтеперерабатывающим заводом). Трубопрово­
ды могут соединяться и разветвляться в промежуточных пунктах. Количество
нефти, которое может быть перекачено по каждому отрезку трубопровода в
единицу времени, также не безгранично и определяется такими факторами,
как диаметр трубы, мощность нагнетающего насоса и т. д. (обычно это назы­
вают «пропускной способностью» или «максимальным расходом» трубопро­
вода). Сколько нефти можно прокачать через такую сеть в единицу времени?

Пусть имеется система машин для производства готовых изделий из сырья, и
последовательность технологических операций может быть различной (то есть
операции могут выполняться на разном оборудовании или в разной последо­
вательности), но все допустимые варианты заранее строго определены. Мак­
симальная производительность каждой единицы оборудования, естественно,
также заранее известна и постоянна. Какова максимально возможная произ­
водительность всей системы в целом и как нужно организовать производство
для достижения максимальной производительности?

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

Определение потока

Пусть G(V, E) — сеть, s и t — соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами, с: Е —» Ј+. Если и и v — вершины, то число с(и, v) — называется пропускной способностью дуги (и, v).

ЗАМЕЧАНИЕ

Матрица пропускных способностей С : array [l..p, l..p] of real является представлением сети, аналогичным матрице смежности. Элемент C[u, v] = 0 соответствует дуге с нулевой пропускной способностью, то есть отсутствию дуги, а элемент C[u, v] > 0 соответствует дуге с ненулевой пропускной способностью, то есть дуга присутствует.

Пусть задана функция f:E-*R. Дивергенцией функции / в вершине v называ­ется число div(/, v), которое определяется следующим образом:
{v\(v,u)ЈE}

{v\(u,v)eE}

ЗАМЕЧАНИЕ

В физике дивергенция обычно определяется наоборот: то, что пришло, минус то, что ушло. Но в данном случае удобнее, чтобы дивергенция источника была положительна.

Функция /: Е —»• R называется потоком в сети G, если:

V(-u, v) б Е 0 < f(u,v) < c(u,v), то есть поток через дугу неотрицателен и не
превосходит пропускной способности дуги;

Vu е V \ {s,t} div(/, и) = О, то есть дивергенция потока равна нулю во всех
вершинах, кроме источника и стока.

Число w(f): = div(/, s) называется величиной потока /.

Разрезы

Пусть Р - (в,г)-разрез, Р с Е. Всякий разрез определяется разбиением множе­ства вершин V на два подмножества S и Т, так что 5 с V, Т с V, S U Т = V, = 0, s е 5, t е Т, а в Р попадают все дуги, соединяющие S и Т. Тогда = Р+ UP-, где Р+ - дуги от 5 к Т, Р~ - дуги от Т к S. Сумма потоков через Дуги разреза Р обозначается F(P). Сумма пропускных способностей дуг разреза Р называется пропускной способностью разреза и обозначается С(Р):

Теорема Форда и Фалкерсона

ЛЕММА w(f) = F(P+) - F(P-).

доказательство

Рассмотрим сумму W:= ^ div(/,v). Пусть дуга (и,v) e E. Если u,v е S, то ves

в сумму W попадают два слагаемых для этой дуги: +/(и,и) при вычислении
div(/,и) и —f(u,v) при вычислении div(/,u), итого 0. Если и е 5, v e Т, то в
сумму W попадает одно слагаемое +/(ц,и), все такие слагаемые дают F(P+).
Если и е Г, v е S, то в сумму W попадает одно слагаемое -f(u,v), все такие
слагаемые дают F(P~]. Таким образом, W = F(P+) - F(P~). С другой стороны,
W = Ј div(/, и) = div(/, s) = «,(/).

ЛЕММА div(/, s) = - div(/, t).

доказательство

Рассмотрим разрез Р: =(S, Т), где S: = V \ {t}, а Т: ={*}. Имеем:

f,s) = w(f) = F(P+) - F(P-) = F(P+] = Ј/M) = -div(/,t).

ЛЕММА w(f) ^ F(P).

доказательство

F(P+) ^ F(P).

ЛЕММА тахго(/) < ттС(Р).

доказательство

По предыдущей лемме ги(/) ^ F(P), следовательно, maxw(/) :

По определению F(P) < С(Р), следовательно, minP(P) < minC'(P).

Имеем: тахго(/) < minC(P).

ТЕОРЕМА (Форда и Фалкерсона) Максимальный поток в сети равен минимальной пропускной способности разреза, то есть существует поток f*, такой что

w(f*) = maxw(/) = minC(P).
доказательство

Пусть / — некоторый максимальный поток. Покажем, что существует разрез Р, такой что w(f) = С(Р]. Рассмотрим граф G', полученный из сети G отменой ориентации ребер. Построим множество вершин 5 следующим образом:

5: ={и Е V 3 (s, u)eG'V(щ, ui+l) 6 (s,и) е G' (гц, щ+i) ЈЕ=^ f(ui, ui+i) < C(ui, ui+i) & (ui+i.iti) G E => f(ui+i,Ui) > 0}, то есть вдоль пути (s, и) дуги в направлении пути не насыщены, а дуги против направления пути имеют положительный поток. Такая цепь (s, и) называется аугментальной. Имеем s e 5 по построению. Следовательно, 5^0. Положим Т: = V \ S. Покажем, что t Ђ Т. Действительно, пусть t e S. Тогда существует аугментальная цепь {s,t}, обозначим ее R. Но тогда можно найти число 8:

(5: = ттД(е), А(е):=-

[ с(е) - f(e] > 0, если е ориентировано вдоль R,
\/(е) > 0, если е ориентировано против R.

В этом случае можно увеличить величину потока на 6, изменив поток для всех дуг аргументальной цепи:

s i

f(e) + 8, если е ориентировано вдоль R, 1(е) - 8, если е ориентировано против R.

ч

При этом условия потока выполняются: 0 ^ f(e) ^ C(e), div(v) = 0.

Таким образом, поток / увеличен на величину 8, что противоречит максималь­
ности потока /. Имеем t е Т и Т ^ 0. Следовательно, 5 и Т определяют разрез
Р = Р+ U Р~. В этом разрезе все дуги е+ насыщены (f(e+) = C(e+)), а все
дуги е~ не нагружены (f(e~) = 0), иначе S можно было бы расширить. Имеем:
w(f) = F(P+) - F(P-) = С(Р+), таким образом, Р+ - искомый разрез. П

8.5.4. Алгоритм нахождения максимального потока

Следующий алгоритм определяет максимальный поток в сети, заданной матри­цей пропускных способностей дуг. Этот алгоритм использует ту же идею доказа­тельства теоремы Форда и Фалкерсона, а именно, задавшись начальным прибли­жением потока, определяется множество вершин S, которые соединены аугмен-тальными цепями с источником s. Если оказывается, что t e S, то это означает, что поток не максимальный и его можно увеличить на величину 8. Для опреде­ления аугментальных цепей и одновременного подсчета величины 8 в алгоритме использована вспомогательная структура данных:

Р • array [l..p] of record

s : enum (—,+) { «знак», то есть направление дуги }

п : 1..р { предшествующая вершина в аугментальной цепи }

S : real { величина возможного увеличения потока } end record

Алгоритм 8.1. Нахождение максимального потока

Вход: сеть G(V, Е) с источником s и стоком t, заданная матрица пропускных способно­стей С : array [l..p, l..p] of real.

Выход: матрица максимального потока F : array [l..p, l..p] of real, for u, v Ђ V do

p[Uj v]: = 0{ вначале поток нулевой } end for

M : { итерация увеличения потока } for v е V do

S{v] : = Q;N[v}: = 0;P[v] :=(,,) { инициализация } end for

S[s]: = 1; P[s]: =(+, s, oo){ так как s Ђ S } repeat

a: = 0{ признак расширения 5 } for и е У do

if SM = l&N[v] =0then for u e I» do

if S[u] = 0&F[v,u} < C[v,u] then

S[u]: = 1; P[u]: =(+, v, mm(P[v}.5, C[v, u] - F[v, u])); a : = 1 end if end for forueT-1^) do

if 5[и] =OkF[u,v] >0then

S[u]: = 1; P[u]: =(-,v, mm(P[v].S, F[u, v})); a: = 1 end if end for N[v]: = 1 end if end for if S[t] then

x:'=i;5:*=P[ti.S while x ^ s do if P[x].s=* + then

F[P[x}'.n,x]: = F[P[x].n, x}+6 else

F[x,P[x].n}: = F[x,P(x].n}-5 end if x: = P[x].n end while goto M end if until a = 0

обоснование

В качестве первого приближения берется нулевой поток, который по опре, нию является допустимым. В основном цикле, помеченном меткой М, дел ся попытка увеличить поток. Для этого в цикле repeat расширяется, пока э возможно, множество S вершин, достижимых из вершины s по аугментальнь цепям. При этом, если в множество 5 попадает вершина t, то поток вдоль най­
денной аугментальной цепи (s,t) немедленно увеличивается на величину 6, и
начинается новая итерация с целью увеличить поток. Процесс расширения мно­
жества S в цикле repeat заканчивается, потому что множество вершин конечно,
а отмеченные в массиве N вершины повторно не рассматриваются. Если про­
цесс расширения множества S заканчивается и при этом вершина t не попадает
в множество S, то по теореме Форда и Фалкерсона найденный поток F является
максимальным и работа алгоритма завершается. П

ЗАМЕЧАНИЕ

Приведенный алгоритм не является самым эффективным. Более подробное изложение известных методов можно найти, например, в [14J или в [11].

Связь между теоремой Менгера и теоремой Форда и Фалкерсона

Теорема Менгера является фундаментальным результатом, который проявляется в различных формах (см., например, задачи 8.4.1, 8.4.2, 8.4.3). Теорема Форда и Фалкерсона также может быть получена из теоремы Менгера. Далее приведена схема неконструктивного доказательства теоремы Форда и Фалкерсона на основе теоремы Менгера. Сначала нужно получить вариант теоремы Менгера в ориен­тированной реберной форме: наибольшее число (s,t)-путей, непересекающихся по дугам, равно наименьшему числу дуг в (s, Ј)-разрезе. Это теорема Форда и Фалкерсона в том случае, когда Ve е Е С(е) = 1. Действительно, пусть Q -множество дуг из максимального набора непересекающихся (s,t)-путей. Назна­чим f(e): = 1, если е е Q, и f(e): = 0, если е Ј Q. Это поток, так как дивергенция в любой вершине равна 0 и поток через дугу не превосходит пропускной способ­ности. Величина этого потока равна k ^ d+(s), где k — число дуг, выходящих из s, которые начинают пути из Q. Этот поток максимальный. Действительно, если положить f(e]: = о > 0 для е & Q, то

1. если дуга е входит в вершину, входящую в пути из Q, или выходит из такой
вершины, то нарушается условие потока (дивергенция -а или +а, соответ­
ственно);

2. если вновь назначенные дуги с ненулевыми потоками образуют новый (s,t)-
путь, то это противоречит выбору Q.

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

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

ОТСТУПЛЕНИЕ -

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

Связность в орграфах

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

Сильная, односторонняя и слабая связность

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

Пусть G(V, Е} — орграф, vi и v2 — его вершины. Говорят, что две вершины v\ и V2 сильно связаны в орграфе G, если существует путь (ориентированная цепь) из v\ в г>2 и из V2 в vi. Говорят, что две вершины v\ и v2 односторонне связаны в орграфе G, если существует путь либо из v: в v2, либо из v2 в v\. Говорят, что две вершины v\ и v2 слабо связаны в орграфе G, если они связаны в графе G', полученном из G отменой ориентации ребер. Если все вершины в орграфе силь­но (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабо) связным. Сильная связность влечет одностороннюю связность, которая влечет слабую связность. Обратное неверно.

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



рис. 8.6.Сильная (слева), односторонняя (в центре) и слабая (справа) связность

. Компоненты сильной связности

Компоненты сильной связности (КСС) орграфа G — это его максимальные сильно связные подграфы.

Каждая вершина орграфа принадлежит только одной КСС. Если вершина не связана с другими, то считаем, что она сама образует КСС. Конденсацией G* орграфа G (или графом Герца, или фактор-графом) называется орграф, который получается стягиванием в одну вершину каждой КСС орграфа G.

Пример

На рис. 8.7 показаны диаграммы орграфа и его конденсации.



Рис. 8.7. Оргаф (слева) и его фактор-граф (справа)

8.6.3. Выделение компонент сильной связности

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

Алгоритм 8.2. Выделение компонент сильной связности Вход: орграф G(V, Е), заданный списками смежности Г(г;).

Выход: список С компонент сильной связности, каждый элемент которого есть список вершин, входящих в компоненту сильной связности. С: = 0 for v e V do

M[v]: ={v} { M[v] список вершин, входящих в ту же КСС, что и v }

e[v]: = 0 { все вершины не рассмотрены } end for while V ф 0 do

select v g V { взять v из V }

Т <— v { положить v в стек }

е[г>]: = 1 { отметить v }

КСС { вызов процедуры КСС } end while

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

if Т = 0 then

return{ негде выделять }

end if

v <— Т; v —» Т { стоим в вершине г>} if T[v] П V = 0 then

C: = C\JM[v] {этоКСС } V : = V \ {v} { удалить вершину } v «— Т { снять г) со стека } КСС { возврат из тупика } else

for и 6 Г[г>] do if e[u] = 0 then u —> Г { положить и в стек } е[и]: = 1 { отметить и } else repeat

w <— Т { ш — склеиваемая вершина } \/ : = V \ {w} { удалить ее } Г [и]: = Г [и] U Г [ад] { запомнить смежность } М[и] : = М[и} U М[го]{ склеивание вершин } until и = w

w —>• Т{ чтобы не убрать ту вершину, } V : = V U {w}{ к которой слили } end if

КСС { поиск в глубину }

end for

end if

Кратчайшие пути

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

8.7.1. Длина дуг

Алгоритм Уоршалла позволяет ответить на вопрос, существует ли цепь (и, и). Часто нужно не только определить, существует ли цепь, но и найти эту цепь. Если задан орграф G(V, E), в котором дуги помечены числами (эти числа обычно называют весами, или длинами, дуг), то этот орграф можно представить в виде матрицы весов (длин) С:{ О, для г = j Cij, конечная величина, если есть дуга из г в j, оо, если нет дуги из г в j.

Длиной пути называется сумма длин дуг, входящих в этот путь. Наиболее часто на практике встречается задача отыскания кратчайшего пути.

8.7.2. Алгоритм Флойда

Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в (ор)графе. В этом алгоритме для хранения информации о путях используется матрица Н[1..р, 1..р], где

., _ J k, если k— первая вершина, достигаемая на кратчайшем пути из г в j; (О, если из i в j нет пути.

ОТСТУПЛЕНИЕ

Матрица Н размера О(р2) хранит информацию обо всех (кратчайших) путях в графе. Заметим, что всего в графе О(р2) путей, состоящих из О(р) вершин. Таким образом, не­посредственное представление всех путей потребовало бы памяти объема О(р3). Эконо­мия памяти достигается за счет интерпретации представления, то есть динамического вычисления некоторой части информации вместо ее хранения в памяти. В данном слу­чае любой конкретный путь (и, v) легко извлекается из матрицы с помощью следующего алгоритма.

w: =u; yield w{ первая вершина }

while w ^ v do

w : = H[w, v}; yield w{ следующая вершина }

end while

Алгоритм 8.З. алгоритм Флойда Вход: матрица С[1..р, 1..р] длин дуг.

Выход: матрица Т[1..р,1..р] длин путей и матрица Н[1..р,1..р] самих путей. for г from I to p do for j from 1 to p do T[i,j] : = C[i,j] { инициализация } if C[iJ] = 00 then

H[i,j\: = 0 { нет дуги из г в j } else

H[i,j] -=j{ есть дуга из г в j } end if end for end for

for г from 1 to p do for j from 1 to p do for fc from 1 to p do

if г + jkT{j,i] / <х>&г ф k&T{i,k] / oo&(T[j,fc] = ooVT[j,k] > T\ then

H[j, k]: = H[j, i] { запомнить новый путь } T[j, k]: = T[j, i] + T[i, k} { и его длину } end if end for end for

for j from 1 to p do if T,j <0then

stop { нет решения: вершина j входит в цикл отрицательной длины } end if end for end for

ЗАМЕЧАНИЕ -

Если в G есть цикл с отрицательным весом, то решения поставленной задачи не суще­ствует, так как можно «накручивать» на этом цикле сколь угодно короткий путь.

обоснование

Алгоритм Флойда имеет много общего с алгоритмом Уоршалла (алгоритм 1.8). Покажем по индукции, что после выполнения г-го шага основного цикла по г элементы матриц T\j,k\ и H[j,k] содержат, соответственно, длину кратчайшего пути и первую вершину на кратчайшем пути из вершины j в вершину k, про­ходящем через промежуточные вершины из диапазона 1..г. База: г = 0, то есть до начала цикла элементы матриц Т и Н содержат информацию о кратчайших путях (если таковые есть), не проходящих ни через какие промежуточные вер­шины. Пусть теперь перед началом выполнения тела цикла на г-м шаге T[j, k] содержит длину кратчайшего пути от j к k , a H[j,k] содержит первую вершину на кратчайшем пути из вершины j в вершину k (если таковой есть). В таком случае, если в результате добавления вершины г к диапазону промежуточных вершин находится более короткий путь (в частности, если это вообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда г = р, матрицы содержат кратчайшие пути, проходящие через промежуточ­ные вершины 1..р, то есть искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует. Дополнительный цикл по j служит для прекращения работы в случае обнаружения в графе цикла с отрицательным весом.

8.7.3. Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в (ор)графе, если длины дуг неотрицательны.

Алгоритм 8.4. алгоритм Дейкстры

Вход: орграф G(V,E), заданный матрицей длин дуг С : array [l..p,l..p] of real; s и t -

вершины графа. Выход: векторы Т : array [l..p] of real; и Я : array [l..p] of O..p. Если вершина v лежит на

кратчайшем пути от s к t, то T[v] — длина кратчайшего пути от s к v; H(v] — вершина, непосредственно предшествующая v на кратчайшем пути. for v from I to p do

T[v]: = oo { кратчайший путь неизвестен }

X[v] : = 0 { все вершины не отмечены } end for

H[s]: = 0 { s ничего не предшествует } T[s]: = 0 { кратчайший путь имеет длину 0 ... }

X[s] : = !{... и он известен } v : = s { текущая вершина } М: { обновление пометок } for и Ђ P(v) do

if X[u\ = 0 & Т{и] > T[v] + C[v, и] then

Т[и] : = T[v] + C[v,u] { найден более короткий путь из s в и через v } Н[и] :=v{ запоминаем его }

end if end for t: = oo;u: = 0

{ поиск конца кратчайшего пути } for и from I to p do

if X[u] = 0&2>] < Ј then

v : = и; t: = Т [и] { вершина v заканчивает кратчайший путь из S}

end if end for if v = 0 then

stop { нет пути из s в t} end if if v = t then

stop { найден кратчайший путь из s в t} end if

X[v]: = 1 { найден кратчайший путь из s в v} goto M

ЗАМЕЧАНИЕ -

Для применимости алгоритма Дейкстры достаточно выполнения более слабого условия, [ положительность длин дуг. А именно, достаточно выполнения неравенства треуголъ-

. Vu, v, w е V d(u, v) ^ d(u, w) + d(w, v), которое, очевидно, выполняется, если длины дуг неотрицательны.

обоснование

Для доказательства корректности алгоритма Дейкстры достаточно заметить, что каждом выполнении тела цикла, начинающегося меткой М в качестве v мьзуетея вершина, для которой известен кратчайший путь из вершины s •ими словами, если X[v] = 1, то 7>] = d(s,v), и все вершины на пути (,,») ределяемом вектором Я, обладают тем же свойством, то есть

\/u T[u] = 1 =*. T[u] = d(s,u)bT[H[u]] = 1.

Действительно (по индукции), первый раз в качестве v используется вершина s я которой кратчайший путь пустой и имеет длину 0 (непустые пути не мо-ггь короче, потому что длины дуг неотрицательны) Пусть ТЫ = d(s u] * всех ранее помеченных вершин и. Рассмотрим вновь помеченную верши­ну v, которая выбрана из условия T[v] = min 2>]. Заметим, что если известен

Л ['ttj ^^0 путь, проходящий через помеченные вершины, то тем самым известен кратчай­ ший путь. Допустим (от противного), что T[v] > d(s,v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть
непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую
что T[w] = 0. Имеем: T[w] = d(s,w) ^ d(s,v) < T[v], что противоречит выбору вершиныv.

коментарии

Изложение центрального результата этой главы — теоремы Менгера 8.3.2 и со­путствующего материала — в основном следует в [23].

Алгоритм нахождения максимального потока в сети заимствован из [11] с небольшими модификациям Алгоритм выделения компонент сильной связности приведен в [5], где имеется весьма полный обзор различных алгоритмов обхода и анализа графов, применя­емых в программировании. Алгоритмы Флойда и Дейкстры нахождения крат­чайших путей принадлежит к числу классических общеизвестных алгоритмов, описание которых можно найти в большинстве учебников по дискретной мате­матике, в частности, в [14, 11].

Упражнения

Доказать, что если 5(G) > (р - 1)/2, то граф G связен.

Доказать вторую теорему подраздела 8.2.1.
Как может измениться количество компонент сильной связности орграфа
при добавлении к нему одной дуги?

Пусть в графе G(V,E) заданы вероятности успешного прохождения дуг,
О ^ P[v] ^ 1. Вероятность успешного прохождения пути определяется как
произведение вероятностей составляющих его дуг. Построить алгоритм на­
хождения наиболее надежного (то есть имеющего наибольшую вероятность)
пути от вершины s к вершине t.

  1   2   3   4


Иркутский государственный технический университет
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации