Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети

§1. Понятие орграфа

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

§3. Бесконтурные графы

§4. Пути в сетях

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


Определение. Сетью называется пара (G,a), где G – ориентированный граф, а a - функция из множества вершин графа в множество неотрицательных действительных чисел.


Если е – дуга графа G, то число a(е) в зависимости от контекста называется либо длиной, либо весом, либо пропускной способностью дуги. При изображении сети a(е) проставляется рядом с дугой е. В этом параграфе число a(е) будет называться длиной дуги е.

Для сетей можно обобщить понятие полустепени исхода и полустепени захода вершины. Пусть N=(G, a) – сеть, v – вершина этой сети (т.е. вершина графа G). Полустепенью исхода r(v) вершины v назовем сумму a(е) по всем дугам, исходящим из v, полустепенью захода r+(v) вершины v – сумму a(е) по всем дугам, заходящим в v. Например, для сети на рис. 6.12 выполняется равенство r(v0)=5, r+(v0)=0, r(v2)=8, r+(v2)=4. Для сетей, так же как и для орграфов справедливо утверждение о том, что сумма полустепеней исхода и сумма полустепеней захода всех вершин совпадают.

Как и в случае орграфов, вершину сети v, для которой r(v)>0 и r+(v)=0 будем называть источником, а вершину w, для которой r+(w)>0 и r(w)=0 – стоком.

Введем длину пути как сумму длин дуг, составляющих путь.


Определение. Расстоянием d(u,v) от вершины u до вершины v называется длина кратчайшего (u,v)–пути. Если (u,v)–пути не существует, то полагаем d(u,v)=¥. Расстояние от u до u равно нулю.

Так для сети, изображенной на рис. 6.12, имеем равенства d(v0,v5)=3, d(v1,v0)=¥, d(v1,v2)=4, d(v2,v1)=2.


Для сети N возникает задача нахождения расстояния d(u,v) для данных вершин u и v и соответствующего кратчайшего пути. Известно несколько способов решения этой задачи. Мы рассмотрим один из них, основой которого является алгоритм Дейкстры, названный в честь известного скандинавского специалиста по компьютерным наукам Дейкстры.

Алгоритм Дейкстры вычисляет расстояние от фиксированной вершины v0 до всех остальных вершин сети. Прежде, чем привести описание алгоритма, введем необходимые обозначения. Пусть N=(G,a) – сеть, v0 – фиксированная вершина этой сети, v1,…,vk – остальные вершины. Для i=1,…,k расстояние d(v0,vi) обозначим через d(vi). На множестве вершин введем двухместную функцию a(v,v’) следующим образом:

Описание алгоритма, кроме того, еще использует подмножество S множества вершин V.


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

Шаг 1. Полагаем S=V\{v0}, d(vi)=a(v0,vi) для всех i=1,…,k.


Шаг 2. Если ½S½=1, то выполнить шаг 4. Выбрать в S элемент v’, для которого величина d(v’) является наименьшей (среди всех элементов из S).


Шаг 3. Положить S=S\{v’}, d(v)=min{d(v), d(v’)+a(v’,v)} для всех vÎS и перейти к шагу 2.


Шаг 4. Выдать d(v1),…,d(vk). Конец работы алгоритма.


Алгоритм осуществляет «итеративный» процесс нахождения расстояния d(vi) для i=1,…,k. Проследим, как это делается для сети N, изображенной на рис. 6.12. Работа алгоритма будет иллюстрироваться заполнением таблицы 6.1.

При выполнении первого шага алгоритма величины d(vi) примут значения, которые указаны в нулевой строке таблицы. Из них точным является только d(v2), значения остальных величин завышены. На шаге 2 в качестве v’ выбирается вершина v2 (в таблице соответствующее значение набрано жирным шрифтом) и удаляется из S на шаге 3. На том же шаге уточняются предыдущие значения d(v) для vÎS (см. первую строку таблицы 6.1). На этом первый проход алгоритма заканчивается. На втором проходе в качестве v’ берется v5, удаляется из S и значения d(v) для vÎS снова уточняются. Результат уточнения отражен во второй строке таблицы. Когда множество S будет содержать только вершину


Рис. 6.12

Таблица 6.1

Номер

строки

d(v1) d(v2) d(v3) d(v4) d(v5)
0 4 1 ¥ ¥ ¥
1 3   ¥ 5 3
2 3   ¥ 4  
3     4 4  
4     4    

V3 алгоритм заканчивает работу. Результат: d(v1)=3, d(v2)=1, d(v3)=4, d(v4)=4, d(v5)=3.

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


Теорема 6.6. Пусть для сети N и фиксированной вершины v0 этой сети алгоритм Дейкстры выдал величины d(v1),…,d(vk). Тогда d(vi) есть расстояние от v0 до vi для i=1,…,k.


Доказательство. Отметим вначале, что если d(vi)¹ ¥ , то величина d(vi) равна длине некоторого пути из v0 в vi. Пусть в очередном проходе алгоритма на втором шаге выбирается вершина v’, d(v’)¹ ¥ и


v0=x0, x1,…,xi-1,xi,…,xp-1, xp=v’ –

кратчайший (v0,v’)–путь. Убедимся в том, что для любой вершины х этого пути выполняется равенство d(x)=d0(v0,x). Действительно, для х=х0 это справедливо. Предположим, что d(xi-1)=d(v0,x), но d(xi)>d(v0,xi). Тогда поскольку d(xi-1)<d(v’), то вершина хi-1 выбиралась на втором шаге в более раннем проходе алгоритма. На третьем шаге этого прохода d(xi) получило бы значение d(xi-1)+a(xi-1,xi), которое равно d(v0,xi). Следовательно, для любой вершины х фиксированного пути выполняется равенство d(x)=d(v0,x), в частности, d(v’)=d(v0,v’). Отсюда следует, что если существует (v0,v)–путь в сети N, то на момент завершения работы алгоритма выполняется равенство d(v)=d(v0,v).

Теорема доказана.


Итак, мы рассмотрели вопрос о нахождении самого короткого пути между двумя вершинами. Однако иногда возникают ситуации, когда надо найти самый длинный путь между данными вершинами. Рассмотрим одну из таких ситуаций.


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

В качестве примера рассмотрим проект, состоящий из семи работ v1,…,v7, время выполнения и предшественники которых указаны в таблице 6.2.

Таблица 6.2

Наимен.

работы

Время

выполн.

Предшествующие

pаботы

v1 3 --
v2 3 --
v3 2 v1
v4 4 v1,v2
v5 2 v2
v6 5 v3,v4
v7 3 v5

Проект удобно представить в виде ориентированного графа, вершинами которого являются работы, а дуги вводятся следующим образом: если работа х предшествует работе y, то изображается (x,y)–дуга. Над такой дугой проставляется время выполнения работы y. Будем считать, что полученная сеть не содержит контуров. В таком случае, сеть имеет хотя бы один источник и хотя бы один сток. Нам будет удобно, чтобы сеть имела в точности один источник и в точности один сток. Для этого расширим проект, добавив две «фиктивные» работы: «начало проекта» и «завершение проекта». Первая работа предшествует всем источникам, а все стоки предшествуют второй из добавленных работ. Время выполнения этих работ равно нулю. Полученная расширенная сеть называется сетевым графиком проекта. Сетевой график проекта, представленного таблицей 6.2, изображен на рис. 6.13. Фиктивные работы – v0 и v8.


Рис. 6.13

Поскольку сетевой график не содержит контуров, то в силу теоремы 6.4 можно считать, что вершины сетевого графика занумерованы так, что если vi предшествует vj, то i<j.

Рассмотрим две задачи, связанные с сетевыми графиками.

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

Введем ряд обозначений. Время выполнения работы v будем обозначать через t(v), а наименьшее время выполнения всего проекта через Tmin. Пусть, далее, PBH(v) и PBO(v) – наиболее раннее время начала и, соответственно, наиболее раннее время окончания работы v. Источник сетевого графика будем обозначать через v0, сток – через vk. Таким образом, Tmin=PBH(vk)=PBO(vk). Следующее утверждение очевидно.


Предложение 1. Для любой вершины v¹v0 сетевого графика справедливы равенства

PBH(v)=max{PBO(v′)½v′ предшествует v},

PBO(v)=PBH(v)+t(v).

Используя это предложение, несложно вычислить величины PBH(v) и PBO(v) для всех вершин v сетевого графика. Напомним, что вершины сетевого графика занумерованы так, что если vi предшествует vj, то i<j. Полагаем, что PBH(v0)=PBO(v0)=0. Пусть, далее, указанные величины найдены для всех вершин v0,v1,…,vl-1. Тогда поскольку все вершины, предшествующие vl, находятся среди v0,v1,…,vl-1, то полагаем PBH(vl)=max{PBO(v’)½v’ предшествует vl} и PBO(vl)=PBH(vl)+t(vl). Результат вычисления для сетевого графика, изображенного на рис. 6.13 , приведен в таблице 6.3. Мы видим, что в этом случае Tmin=12.

Таблица 6.3

Работы PBH(v) PBO(v) ПВН(v) ПВО(v)
v0 0 0 0 0
v1 0 3 0 3
v2 0 3 0 3
v3 3 5 5 7
v4 3 7 3 7
v5 3 5 7 9
v6 7 12 7 12
v7 5 8 9 12
v8 12 12 12 12

Как показывает следующее утверждение, наиболее раннее время выполнения проекта равно длине самого длинного пути из v0 в vk.


Теорема 6.7. Наиболее раннее время окончания работы v равно длине самого длинного пути из v0 в v.


Доказательство. Для v=v0 теорема очевидна. Предположим, что теорема доказана для вершин v0,v1,…,vl-1 и v=vl. Пусть, далее, среди вершин v’, предшествующих вершине v, максимум величины PBO(v’) достигается на вершине vi. Тогда PBH(v)=PBO(vi) и PBO(v)=PBO(vi)+t(v). Это означает, что существует путь из v0 в v, имеющий длину PBO(v). Рассмотрим произвольный путь из v0 в v, обозначим его длину через d.Этот путь должен проходить через одну из вершин, предшествующих v. Пусть он проходит через вершину vj (см. рис. 6.14).


Рис. 6.14

Поскольку для vj утверждение теоремы справедливо, то d(PBO(vj)+t(v). Но в силу введенных выше обозначений, справедливо неравенство PBO(vi)(PBO(vi). Это означает, что d(PBO(vi)+t(v)=PBO(v).

Теорема доказана.


Заметим, что самый длинный путь из v0 в vk может быть не один (см. рис. 6.13).


Вторая задача, связанная с сетевыми графиками состоит в нахождении так называемых критических работ. Предположим, что уже вычислено наиболее раннее время окончания каждой работы и всего проекта в целом. Тогда возникает вопрос о нахождении самого позднего времени окончания работ, которое не влияет на время выполнения всего проекта в целом. Введем соответствующие обозначения. Пусть задано время Т выполнения проекта в целом. Ясно, что T³Tmin. Через ПВН(v) и ПВO(v) обозначим соответственно наиболее позднее время начала и наиболее позднее время окончания работы v, не ведущие к увеличению времени Т выполнения проекта. Работа v, для которой PBO(v)=ПВО(v), называется критической. Временному графику выполнения критических работ руководитель проекта должен уделять особое внимание, поскольку сдвиг во времени при выполнении этих работ повлечет увеличение времени выполнения всего проекта в целом.


Следующее утверждение очевидно.


Предложение 2. Для любой вершины v¹vk сетевого графика справедливы равенства

ПВО(v)=min{ПВН(v’)½v предшествует v’},

ПВН(v)=ПВО(v)-t(v).


Предложение 2 «позволяет» легко вычислить величины ПВO(v) и ПВН(v) для всех вершин v сетевого графика. Считаем, как уже неоднократно отмечалось, что вершины сетевого графика занумерованы так, что если vi предшествует vj, то i<j. Положим, что ПВО(vk)=ПВН(vk)=Т. Предположим, что указанные величины вычислены для вершин vl+1,…,vk и что v=vl. Если вершина v предшествует vj, то j>l, и поэтому значение ПВН(vj) уже вычислено. Полагаем, что ПВО(v)=min{vj½v предшествует vj} и ПВН(v)=ПВО(v)-t(v). Результат вычисления величин ПВН(v) и ПВО(v) для сетевого графика, изображенного на рис. 6.13, в случае, когда Т=Тmin=12 приведен в таблице 6.3. Как мы видим, критическими работами в этом примере являются работы v0,v1,v2,v4,v6,v8.


Следующее утверждение доказывается аналогично доказательству теоремы 6.7.


Теорема 6.8. Пусть T=Tmin. Тогда длина самого длинного пути из v в vk равна Т минус наиболее позднее время окончания работы v.


Из теорем 6.7 и 6.8 следует


Теорема 6.9. Пусть T=Tmin. Тогда критическими работами являются те и только те работы, через которые проходит (хотя бы один) самый длинный путь из v0 в vk.


Доказательство. Длину самого длинного пути из v в v’ обозначим через D(v,v’). Напомним, что из теоремы 6.7 следует равенство D(v0,vk)=Tmin.

Пусть v – критическая работа, v0=x1,…,xi-1, xi=v – самый длинный путь из v0 в v, а v=y1,y2,…, yj=vk – самый длинный путь из v в vk. Тогда длина первого пути равна D(v0,v), второго – D(v,vk), D(v0,v)=PBO(v) (теорема 6.7) и ПВО(v)+D(v,vk)=Tmin (теорема 6.8). Поскольку РВО(v)=ПВО(v), то длина объединенного пути x1,…,xi, y2,…,yj равна D(v0,v)+D(v,vk)=Tmin. Это означает, что объединенный путь имеет максимальную длину. Tак как он проходит через вершину v, то через v проходит самый длинный путь из v0 в vk.

Предположим теперь, что через v проходит самый длинный путь v0=z1,…,zi,…,zl=vk и zi=v. Тогда z1,…,zi – самый длинный путь из v0 в vi, а zi,…,zl – самый длинный путь из vi в vk. Согласно теоремам 6.7 и 6.8 длина первого пути равна РВО(v), а второго Tmin-ПВО(v). Это означает, что D(v0,vk)=D(v0,v)+D(v,vk)=PBO(v)+Tmin-ПВО(v)=Tmin. Следовательно, РВО(v)=ПВО(v), т.е. v – критическая работа.

Теорема доказана.

§5. Потоки в сетях

Задачи

Ответы указания и решения


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru