close

Вход

Забыли?

вход по аккаунту

?

149.Каверина В.К.Задачи оптимизации и планирования на сетях

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Воронежский государственный архитектурно–строительный университет»
В.К. Каверина
ЗАДАЧИ ОПТИМИЗАЦИИ И ПЛАНИРОВАНИЯ
Учебное пособие
Воронеж 2015
УДК 517.15
ББК 22.176я73
К125
Каверина, В.К.
К125
Задачи оптимизации и планирования на сетях: учеб. пособие / В.К. Каверина; Воронежский ГАСУ. – Воронеж, 2015. – 62 с.
В учебном пособии излагаются основы теории графов и представлены алгоритмы, предназначенные для решения прикладных задач с помощью теории графов. Разобранные задачи имеют экономическую интерпретацию, а методы их решения находят широкое практическое применение.
Каждый раздел сопровождается упражнениями.
Учебное пособие предназначено для магистрантов всех направлений,
изучающих курсы дискретной математики и дискретного программирования, включенные в современные образовательные стандарты. Пособие будет полезно магистрантам и аспирантам в качестве дополнительного материала при изучении основ теории графов и задач планирования и оптимизации на сетях.
Ил. 33. Табл. 6. Библиогр.: 11 назв.
УДК 517.15
ББК 22.176я73
Печатается по решению
учебно-методического совета Воронежского ГАСУ
Рецензенты:
кафедра высшей математики и теоретической
механики Воронежского государственного аграрного
университета им. Петра I;
М.Е. Семенов, д-р физ.-мат. наук, проф.
ISBN 978-5-89040-569-2
© Каверина В.К., 2015
© Воронежский ГАСУ, 2015
Введение
Основу теории графов составляет совокупность методов и представлений, которые сформировались при решении конкретных прикладных задач. Во множестве математических объектов графы занимают одно из ведущих мест в качестве основы формирования моделей реальных систем. В
рамках теории графов выделяют два основных класса задач. В первом требуется ответить на вопрос, существуют ли графы, обладающие определенным свойством, и если да, то какова оценка их количества. Во втором
нужно определить, как построить граф или подграф, обладающий некоторым заданным свойством.
Начало теории графов относят к 1736 году, когда Л. Эйлер решил популярную в то время задачу о кенигсбергских мостах: можно ли совершить прогулку по берегам реки, соединенным семью мостами так, чтобы, выйдя из дома,
вернуться обратно, пройдя в точности один раз
по каждому мосту?
Однако этот результат более ста лет оставался единственным результатом теории графов. Толчок к развитию теория графов получила в середине XIX века, когда Г. Киркгоф разработал теорию деревьев для исследования электрических цепей, а А. Кэли решил перечислительные задачи для
трех типов деревьев.
В настоящее время теория графов стала популярным средством решения задач, связанных с дискретными объектами. К ним, в частности относятся: проектирование и исследование сетей связи, электрических и
монтажных схем, программных систем; исследование автоматов, анализ и
синтез логических цепей; задачи календарного планирования; поиск информации; разработка стратегий инвестиций; анализ качества, исследование движения транспорта, размещение предприятий коммунального обслуживания, исследование поведения индивидуумов.
Глава 1. Основные понятия
1.1. Формы представления графов. Подграфы. Степени вершин
Определение 1.1. Граф G = ( X , U ) задан, если даны два конечных
множества: а) множество вершин X = {x1 , x 2 ,..., x n } ;
б) множество ребер U = {u1 , u 2 ,..., u m } , состоящее из некоторых пар
элементов u k = ( xi , x j ) множества вершин X .
Для наглядности геометрически вершинам графа сопоставляют точки, а ребрам – линии, соединяющие некоторые из этих точек.
3
Данное определение графа должно быть дополнено в одном важном
отношении. В определении ребра можно принимать или не принимать во
внимание порядок расположения двух его концов. Если этот порядок является несущественным, то есть u = ( xi , x j ) = ( x j , xi ) , то говорят, что ребро
u - неориентированное; если же этот порядок является существенным, то
есть, например, xi - начало, а x j - конец ребра, то u называется ориентированным ребром или дугой.
Определение 1.2. Граф называется неориентированным (неорграфом), если каждое его ребро не ориентировано.
Определение 1.3. Граф называется ориентированным (орграфом),
если каждое его ребро ориентировано, причем xi называется начальной
вершиной ребра, а x j - конечной вершиной ребра ( xi , x j ) .
Замечания. 1) ориентация ребра указывается стрелкой; 2) говорят,
что дуга ( xi , x j ) выходит из вершины xi и заходит в вершину x j ; 3) любой
неориентированный граф можно трактовать как ориентированный, заменив каждое неориентированное ребро на две дуги, противоположно направленные; 4) граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.
Петлей называется ребро ( xi , xi ) , у которого начальная и конечная
вершины совпадают. Граф, полученный из орграфа заменой каждой дуги
на ребро, называется основанием графа.
Если пара вершин графа соединяется несколькими различными ребрами или дугами, то ребра называются кратными, а их количество – кратностью ребра. Граф с кратными ребрами без петель называется мультиграфом. Граф с петлями и кратными ребрами называется псевдографом.
Граф без петель и кратных ребер называется простым графом.
Пример 1.1.
x1
x2
а)
x1
x2
б)
x1
x2
в)
x1
г)
Рис. 1.1
На рис. 1.1 а), в) изображены неорграф и смешанный граф соответственно, у которых кратность ребра ( x1 , x 2 ) равна трем. На рис. 1.1 б) изображен орграф, у которого кратность ребра ( x1 , x 2 ) равна двум. На рис. 1.1
г) приведен пример петли (петля обычно считается неориетированной).
Пример 1.2. На рис. 1.2: а) – псевдограф, б) – мультиграф, в) - простой граф.
Определение 1.4. Две вершины графа x i , x j называются смежными,
если существует соединяющее их ребро ( xi , x j ) , при этом x i , x j называются концами ребра.
4
x2
x2
x2
x3
x1
а)
x3
x1
x3
x1
б)
Рис 1.2
в)
Определение 1.5. Два ребра смежны, если они имеют общую вершину.
Определение 1.6. Если ребро соединяет вершины x i , x j , то говорят,
что ребро инцидентно вершинам x i , x j , а, в свою очередь, вершины x i , x j
инцидентны этому ребру ( xi , x j ) .
Вершина, для которой не существует инцидентных ей ребер, называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро, называется висячей.
x1
x1
x2
x3
x4
x3
x4
x2
Рис. 1.3
Рис. 1.4
Пример 1.3. На рис. 1.3 изображен неориентированный граф, имеющий 4 вершины, 5 ребер. Смежными вершинами являются, например, x1 и
x 2 , x1 и x 4 ; смежными ребрами являются ( x1 , x 4 ) и ( x 4 , x 2 ) ; ребро ( x1 , x 2 )
инцидентно вершинам x 2 , x1 ; а вершина x3 инцидентна ребрам ( x3 , x2 ) и
( x 4 , x3 ) .
На рис. 1.4 изображен ориентированный граф, имеющий 4 вершины,
6 дуг. Смежными вершинами являются x1 и x 2 , x 2 и x3 ; смежными дугами являются ( x 4 , x3 ) и ( x3 , x 2 ) ; ( x3 , x 4 ) и ( x3 , x 2 ) ; дуга ( x 4 , x3 ) инцидентна вершинам x3 , x 4 ; а вершина x 4 инцидентна ребрам ( x3 , x 4 ) , ( x 4 , x3 ) и
( x 4 , x1 ) .
Пусть Γ( xi ) - множество вершин x j , для которых в графе G существует ориентированная дуга ( xi , x j ) , тогда это множество называется окрестностью вершины xi . Используя понятие окрестности, граф определяют
как совокупность множества вершин и множества окрестностей в виде
G = ( X , Γ) , где Γ - неоднозначное отображение, ставящее в соответствие
каждой вершине подмножество Γ( xi ) в X . Γ −1 ( xi ) - множество вершин
x j , для которых в графе G существует дуга ( x j , xi ) . Например, для графа,
5
изображенного на рис. 1.4, множество Γ( x 4 ) = {x1 , x3 } , а множество
Γ −1 ( x 2 ) = {x1 , x3 } .
Если граф ориентированный, то говорят, что дуга ( xi , x j ) исходит из
вершины xi и заходит в вершину x j . Число дуг, которые имеют вершину
xi своей начальной вершиной, называют полустепенью исхода вершины xi
и обозначают d − ( xi ) . Число дуг, которые имеют вершину xi своей конеч-
ной вершиной, называют полустепенью захода xi и обозначают d + ( xi ) .
Заметим, что d + ( xi ) = Γ −1 ( xi ) , d − ( xi ) = Γ( xi ) .
Для неориентированного графа G степенью или валентностью
вершины xi , называется число ребер, инцидентных вершине xi , то есть
число ребер концом которых является вершина xi (при этом петли считаются дважды). Степень вершины xi будем обозначать d ( xi ) . Для ориентированного графа степень вершины xi определяется следующим образом
d ( xi ) = d − ( x i ) + d + ( xi ) .
Иначе говоря, степени вершин ориентированного графа есть степени вершин в соответствующем неориентированном графе.
Поскольку каждое ребро инцидентно двум вершинам, в сумму степеней вершин графа каждое ребро вносит двойку. Таким образом, мы приходим к утверждению, которое установлено Эйлером и является исторически первой теоремой теории графов.
Теорема 1.1. Сумма степеней вершин графа G равно удвоенному
числу его ребер:
∑ d ( x i ) = 2m ,
i
где m - число ребер графа. Изолированная вершина имеет степень 0, висячая вершина – степень 1.
Последовательность d1 ≥ ... ≥ d n называется графической, если существует граф G на n вершинах x1 ,..., x n такой, что степень d ( xi ) вершины
xi равна d i для любого i . В этом случае d = {d1 ,..., d n } называется последовательностью степеней графа или степенной последовательностью.
Рассмотрим графы, обладающие определенными свойствами.
Граф, в котором две любые вершины смежны, называется полным.
Полный орграф называется турниром. Этот термин получил свое название
от соревнований по круговой системе, графическое представление которых
имеет структуру полного ориентированного графа. В турнирах по круговой системе играют несколько команд, каждая со всеми остальными по
одному разу. Игра по правилам не может закончиться в ничью. В представлении графом командам соответствуют вершины, а дуга ( x, y ) присутствует тогда и только тогда, когда команда x победила команду y . Количество очков команды соответствует числу побежденных ею противников
или числу элементов в ее окрестности Γ .
6
Граф G , который можно изобразить на плоскости так, чтобы никакие два ребра не пересекались в точках, отличных от вершин, называется
планарным графом.
Пример 1.4. На рис. 1.5: а) - полный неорграф, б) - полный орграф,
в) – планарный граф.
а)
б)
в)
Рис. 1.5
В графе можно выделить части – подграфы, обладающие некоторыми свойствами. Рассмотрим граф G = ( X , U ) .
Определение 1.7. Граф G ′ = ( X ′, U ′) называется подграфом графа
G , если X ′ ⊆ X и U ′ ⊆ U .
Иначе говоря, от исходного графа остается некоторое подмножество
вершин и некоторое подмножество ребер или дуг, соединявших эти вершины.
Определение 1.8. Если X = X ′ , то такой подграф называется остовным.
Примером остовного подграфа может быть подграф Gu = ( X , U \ u ) ,
полученный из неорграфа G = ( X , U ) путем удаления ребра u , в дальнейшем такой подграф будем обозначать сокращенно Gu = G − u .
Определение 1.9. Порожденным подграфом графа G на множестве
вершин X ′ называется подграф G ′ = ( X ′, U ′) , такой, что U ′ содержит все
те ребра из U , которые соединяют вершины из X ′ .
Определение 1.10. Подграф G ′ графа G называется максимальным
подграфом по отношению к некоторому свойству P , если G ′ обладает
свойством P и G ′ не является подграфом никакого другого подграфа графа G , обладающего свойством P .
x2
x2
x3
x1
x4
x6
x5
а)
x3
x1
x2
x2
x1
x3
x4
x6
x3
x1
x4
x4
x5
б)
в)
Рис. 1.6
7
г)
Пример 1.5. На рис 1.6 : а) – данный граф, б) – остовный подграф, в)
– порожденный подграф, г) – подграф.
Пример 1.6. Пусть G = ( X , U ) представляет собой карту автомобильных дорог России: множество вершин X - это города, а множество
ребер U - это дороги между городами. Тогда карта всех дорог Воронежской области – это порожденный подграф, а карта всех федеральных трасс
России – это остовный подграф.
Задачи и упражнения
1.1. Изобразите графически следующие графы:
а) G1 = ({x1 , x 2 , x3 }, {( x1 , x 2 ), ( x1 , x3 ), ( x1 , x1 ), ( x 2 , x3 )}) ;
б) G 2 = ({x1 , x 2 , x3 , x 4 }, {( x1 , x 2 ), ( x1 , x 4 ), ( x 2 , x 4 ), ( x3 , x3 ), ( x3 , x 4 ), ( x 4 , x1 )}) .
1.2. Для графа, изображенного на рис. 1.7, найти:
а) Γ( x 2 ) , Γ −1 ( x 2 ) ;
б) d − ( x 2 ) , d + ( x 2 ) ;
x1
x5
x2
x3
x4
Рис. 1.7
1.3. Для графа G = ( X , U ) , изображенного на рис. 1.7, описать:
а) описать порожденный подграф G ′ , у которого X ′ = {x1 , x 2 , x3 , x 4 } ;
б) остовный подграф ( X , U ′) , где ( xi , x j ) ∈U ′ тогда и только тогда, когда
i + j нечетно.
1.4. Для неориентированного графа доказать, что число вершин с нечетной степенью четно (нуль – четное число).
1.2. Путь, цепь, контур, цикл. Связность графа
Определение 1.11. Путем в орграфе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Для неорграфа такая последовательность ребер называется цепью. Под длиной пути (цепи) подразумевается количество дуг (ребер) которые составляют этот путь (цепь).
Определение 1.12. Если каждой дуге (ребру) приписано некоторое
число, называемое весом, то граф называется взвешенным.
8
В случае взвешенного графа, длина пути (цепи) – это сумма весов
дуг (ребер), входящих в этот путь.
Определение 1.13. Путь (цепь) называется простым(-ой), если в нем
никакая дуга (ребро) не встречается дважды, и составным(-ой) - в противном случае.
Определение 1.14. Путь (цепь) называется элементарным(-ой), если
в нем ни одна вершина не встречается дважды.
Определение 1.15. Путь (цепь), у которого(-ой) начальная и конечная вершина совпадают, называется контуром (циклом).
Пример 1.7.
u2
u8
x2
u3
u6
x2
u7
x5
x1
а)
x4
u6
u1
u4
u5
u3
x4
u7
u1
x1
x3
x3
u2
u5
u4
x5
б)
Рис. 1.8
Для неорграфа, изображенного на рис. 1.8 а):
1) элементарная цепь ( x1 , x 2 ) , ( x 2 , x3 ) , ( x3 , x 4 ) ;
2) элементарный цикл ( x1 , x 2 ) , ( x 2 , x3 ) , ( x3 , x1 ) ;
3) простая цепь ( x1 , x 2 ) , ( x 2 , x3 ) , ( x3 , x 4 ) , ( x 4 , x 2 ) ;
4) простой цикл ( x1 , x 2 ) , ( x 2 , x3 ) , ( x3 , x 4 ) , ( x 4 , x 2 ) , ( x 2 , x5 ) , ( x5 , x1 ) .
Для орграфа, изображенного на рис. 1.8 б):
1) простой путь ( x1 , x 2 ) , ( x 2 , x3 ) , ( x3 , x 4 ) , ( x 4 , x5 ) , ( x5 , x 2 ) ;
2) элементарный контур ( x5 , x 2 ) , ( x 2 , x3 ) , ( x3 , x 4 ) , ( x 4 , x5 ) .
Ниже приведем без доказательства утверждения, которые будут нам
полезны в дальнейшем.
Утверждение 1.1. [3, гл.1, § 4] Объединение двух несовпадающих
элементарных цепей, соединяющих вершины xi и x j , содержит цикл.
Утверждение 1.2. [3, гл.1, § 4] Если C и D - два несовпадающих
цикла, имеющих общее ребро u , то граф (C ∪ D) − u также содержит
цикл. (Доказать самостоятельно).
Определение 1.16. Неориентированный граф называется связным,
если любые его вершины связаны цепью, иначе граф называется несвязным.
Для орграфов понятие связности является более содержательным.
Можно выделить три типа связности орграфа.
9
Определение 1.17. Орграф называется слабо связным, если его основание есть связный граф; односторонне связным, если для любых двух
различных вершин xi и x j существует, по крайней мере, один путь из xi в
x j , или из x j в xi ; сильно связным, если для любых двух различных вершин xi и x j существует путь из xi в x j и обратно.
Определение 1.18. Всякий максимальный связный подграф графа G
называется компонентой связности графа G или связной компонентой.
Еще раз напомним, что слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с бόльшим числом элементов.
Аналогично, для орграфа формулируется понятие односторонней
компоненты связности, сильной компоненты связности.
Пример 1.8. На рис 1.9: а) – связный неорграф, б) – несвязный неорграф, содержащий две компоненты связности, в) – сильно связный орграф.
x2
x4
x2
x2
x4
x3
x4
x1
x5
x1
x3
а)
x5
x1
x3
x5
б)
в)
Рис. 1.9
Теорема 1.2. [3, гл.1, § 4] Каждый граф представляется в виде объединения своих связных компонент. Разложение графа на связные компоненты определено однозначно.
Отметим, что указанная теорема позволяет сводить большинство задач, касающихся графов, к случаю связных графов. Полезна также и следующая
Лемма 1.1. [3, гл.1, § 4] Пусть G = ( X , U ) - связный граф. Тогда:
1) если ребро u ∈ U принадлежит какому-либо циклу графа G , то граф
G − u связен;
2) если ребро u ∈ U не входит ни в какой цикл, то граф G − u имеет ровно
две компоненты связности.
На вопрос, сколько ребер может быть в графе с n вершинами и фиксированным числом компонент связности k отвечает следующая
Теорема 1.3. [3, гл.1, § 4] Пусть число компонент связности простого
графа G = ( X , U ) равно k , число ребер m , число вершин n . Тогда справедлива следующая оценка
(n − k )(n − k + 1)
n−k ≤m≤
,
2
причем обе эти оценки для m достижимы.
10
Задачи и упражнения
1.5. Приведите пример сильно связного, односторонне связного, слабо связного, несвязного графов.
1.6. Среди графов, изображенных на рис. 1.10, указать сильно связный, односторонне связный, несвязный графы.
G1
G2
G3
G4
Рис. 1.10
1.3. Матричные представления графов
Понятия, которые вводятся в этом разделе, полезны при алгебраическом исследовании графов, а также при компьютерной обработке в том
случае, когда число вершин и ребер графа настолько велико, что геометрическое представление теряет свою наглядность.
Пусть G = ( X , U ) произвольный простой граф, число вершин которого равно n .
Определение 1.19. Матрицей смежности графа G = ( X , U ) называется квадратная матрица A размерности n × n , элементы которой определяются следующим образом:
1, если вершины xi и x j соединены ребром (дугой),
aij = 
0,
в противном случае.

Замечание. 1) Матрица смежности неорграфа всегда симметрическая; 2) Количество дуг, выходящих из i -ой вершины, – это сумма элементов i -ой строки. Количество дуг, входящих в i -ую вершины, – это сумма
элементов i -го столбца.
Пример 1.9. Для неорграфа, изображенного на рис. 1.8 а) и орграфа,
изображенного на рис. 1.4, матрицы смежности соответственно равны:
0

1
A1 =  1

0
1

1 1 0 1

0 1 0 0
1 0 1 1,

0 1 0 1
0 1 1 0 
1

0
A2 = 
0

1
11
1 0 0

0 0 0
.
1 0 1

0 1 0 
Определение 1.20. Матрицей инцидентности графа G = ( X , U ) с n
вершинами и m ребрами называется матрица B размерности n × m , элементы которой определяются следующим образом:
 1, если вершина xi является началом дуги u j ,

bij = − 1, если вершина xi является концом дуги u j ,
 0, если вершина xi не инцидентна дуге u j

Пример 1.10. Матрица инцидентности для неориентированного
графа, изображенного на рис. 1.8 а):
 u1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 


x1  1 0 0 0 1 0 0 1 
x2  1 1 0 0 0 1 1 0 

B= 
x3  0 1 1 0 0 0 0 1 
x4  0 0 1 1 0 0 1 0 



x5  0 0 0 1 1 1 0 0 
Матрица инцидентности для ориентированного графа, изображенного на рис. 1.8 б):
 u1 u 2 u 3 u 4 u 5 u 6 u 7 


x1  1
0
0
0 −1 0
0
x2  − 1 1
0
0
0 −1 1 

B= 
x3  0 − 1 1
0
0
0
0
x4  0
0 −1 1
0
0 − 1


x 5  0
0
0 −1 1
1
0 
Задачи и упражнения
1.7. Для графа, приведенного на рисунке 1.11, найти:
а) матрицу смежности; б) матрицу инцидентности.
x1
x2
x3
x6
x4
x5
Рис. 1.11
12
1.8. Построить граф по матрице смежности:
1

1
A=
0

1
0 1 1

0 1 0
.
1 1 0

1 0 0 
1.4. Деревья
Понятие дерева как математического объекта было впервые предложено Киркгофом в связи с определением фундаментальных циклов, применяемых при анализе электрических цепей. Деревья занимают особое положение в теории графов из-за предельной простоты строения, и часто при
решении какой-либо задачи на графах ее сначала исследуют на деревьях.
Понятие дерева применяется при конструировании различных алгоритмов.
Кратчайшее остовное дерево находит применение при решении задач, в
которых необходимо связать n точек некоторой сетью так, чтобы общая
длина «линий связи» была минимальна.
Определение 1.21. Деревом называется связный неорграф без циклов, имеющий не менее двух вершин.
Определение 1.22. Если G - граф с n вершинами, то остовным деревом (остовом) графа G называется всякий остовный подграф графа G ,
являющийся деревом.
Определение 1.23. Ориентированным деревом с корнем r ∈ X называется ориентированный граф G = ( X , U ) без циклов, в котором полустепень захода каждой вершины, за исключением одной r , равна 1, а полустепень захода вершины r равна 0.
Примером ориентированного дерева может служить "генеалогическое" дерево, в котором вершины соответствуют лицам мужского пола, а
дуги ориентированы от родителей к детям. Корень в этом дереве соответствует "основателю" рода.
Рассмотрим следующую практическую задачу. Пусть имеется ряд
городов, которые предполагается соединить авиалиниями. Как выбрать
маршруты, чтобы из любого города можно было попасть в любой другой
(с пересадками) и общая длина маршрутов было наименьшей? Пусть вершинами графа служат города, а дугами – возможные маршруты самолетов,
пусть длина дуги равна длине соответствующего маршрута. Таким образом, практической задаче сопоставляется математическая задача о кратчайшем остовном дереве.
Другим примером служит построение кратчайшей коммуникационной сети. Пусть на некоторой территории размещены пункты, которые надо связать коммуникационной сетью минимальной стоимости. Предположим, что в результате изысканий определены возможные трассы для про13
кладки коммуникаций и оценена стоимость создания каждой трассы. Сопоставим каждому пункту сети вершину графа, две вершины будут соединены дугой, если только соответствующие пункты соединены возможной
трассой коммуникации. Каждой дуге сопоставим число, равное стоимости
строительства соответствующей коммуникации, и назовем его длиной дуги. Оптимальной структуре коммуникационной сети будет соответствовать
кратчайшее дерево.
Пример 1.11. На рис. 1.12 а) – данный граф, б) – остов графа, в) –
другой остов графа.
x2
x3
x1
x4
x3
x1
x7
а)
x3
x4
x4
x5
x5
x6
x2
x2
x6
x7
б)
x5
x1
x6
x7
в)
Рис. 1.12
Рассмотрим некоторые свойства дерева. Хотя данное выше определение дерева просто для понимания, существует еще несколько других определений дерева, которые рассматриваются в следующей теореме.
Теорема 1.4. Пусть G - граф, у которого n вершин и m ребер
( n > 1 ). Тогда следующие свойства равносильны:
1) G связен и не содержит циклов, то есть G - дерево;
2) G связен и имеет (n − 1) ребро;
3) G не содержит циклов и имеет (n − 1) ребро;
4) всякая пара вершин соединена цепью и притом только одной;
5) G не содержит циклов, добавление ребра между любыми двумя
несмежными вершинами приводит к появлению циклов.
Доказательство. Покажем, что из 1)⇒2) ⇒3) ⇒4) ⇒5) ⇒1), тогда
все свойства равносильны. Воспользуемся индукцией по n .
При n = 2 утверждение тривиально.
Пусть n > 2 .
Покажем, что из 1)⇒2). В дереве нет циклов, следовательно, согласно лемме 1.1, граф G − u имеет ровно две компоненты связности T1 и T2 ,
каждая из которых есть дерево. Пусть у графа Ti - ni вершин, mi ребер,
i = 1,2 . По индуктивному предположению верны равенства
mi = n i − 1 .
14
Далее имеем
m = m1 + m 2 + 1 = n1 − 1 + n 2 − 1 + 1 = (n1 + n 2 ) − 1 = n − 1 .
2)⇒3) Граф связен и m = n − 1 . Требуется доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть u - ребро этого цикла.
Тогда G − u связен (лемма 1.1) и имеет (n − 2) ребра, что противоречит
теореме 1.3.
3)⇒4) Пусть k - число компонент связности G . Пусть, далее, компонента Ti граф, у которого ni - число вершин, mi - число ребер. Так как Ti
- дерево, то mi = ni − 1 . Теперь имеем
n − 1 = m = m1 + m2 + ... + mk = (n1 − 1) + (n2 − 1) + ... + (nk − 1) =
= (n1 + n2 + ... + nk ) − k = n − k
n − 1 = n − k , k = 1.
Итак, G - связный граф и потому любые несовпадающие вершины xi
и x j соединены в нем цепью. Предположим, что существует две несовпадающие цепи, соединяющие xi и x j , тогда согласно утверждению 1.1 их
объединение содержит цикл, что противоречит нашему условию. Следовательно, каждые две вершины соединены единственной цепью.
4)⇒5) Предположим, что граф G содержит циклы. Пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей
мере двумя цепями, что противоречит условию. Следовательно, G ациклический. Пусть x i и x j - две его несмежные вершины. Присоединим к
графу G ребро u = ( xi , x j ) . В G есть цепь ( xi , x j ) , которая в G + u дополняется до цикла. В силу утверждения 1.2 это цикл единственен.
5)⇒1) Требуется доказать, что граф G связен. Предположим противное, то есть, что вершины x i и x j принадлежат разным компонентам
связности графа G . Тогда G + ( x i , x j ) не имеет циклов, что противоречит
5). Следовательно, G связен и потому является деревом.
Далее, рассмотрим задачу о кратчайшем остовном дереве.
Постановка задачи. Пусть дан связный неорграф G = ( X , U ) , каждому ребру u которого в соответствие поставлено число l (u ) > 0 , называемое длиной этого ребра. Требуется найти остов графа G , общая длина ребер которого минимальна.
Алгоритм Краскала построения кратчайшего остова
взвешенного графа
Шаг 1. Начать с построения графа T , содержащего все n вершин исходного графа и не содержащего ни одного ребра.
Шаг 2. Составить список ребер графа G в порядке неубывания их
весов.
Шаг 3. Начав с первого ребра в этом списке, добавлять по порядку
ребра в графе T , соблюдая условие: такое добавление не должно приводить к появлению цикла в T , в противном случае это ребро пропускается.
15
Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в T не станет
равным n − 1 . Получившееся дерево является кратчайшим остовом графа.
Обоснование алгоритма Краскала весьма тривиально [2, гл. 7, § 3].
Пример 1.12. Найти кратчайший остов графа G , изображенного на
рис. 1.13 а). Над ребрами графа указаны длина каждого ребра.
Шаг 1. Построим граф, содержащий все девять вершин графа, рис.
1.13 б).
Шаг 2. Расположим все ребра графа в порядке неубывания их длин:
1
1
1
( x1 , x 2 ) , ( x1 , x 4 ) , ( x 2 , x5 ) ,
2
2
2
( x 2 , x 4 ) , ( x 4 , x 5 ) , ( x 6 , x8 ) ,
3
3
3
3
( x 2 , x 6 ) , ( x 5 , x 6 ) , ( x8 , x 9 ) , ( x 7 , x 8 ) ,
4
4
( x3 , x6 ) , ( x 6 , x9 ) ,
5
5
6
7
( x 2 , x 3 ) , ( x 5 , x8 ) , ( x 4 , x 7 ) , ( x 4 , x8 ) .
x1
1
x2
1
2
3
2
x4
x5
6
7
x7
3
3
1
5
x8
x1
x3
5
4
x2
1
1
x6
1
x3
3
4
x6
x4
x5
2
3
4
2
x9
x7
а)
3
x8
3
x9
б)
Рис. 1.13
Всего девять вершин, поэтому алгоритм закончится, когда будет
внесено восемь ребер в граф. На рис. 1.13 б) представлено кратчайший остов графа, его длина равна восемнадцати.
Отметим, что полученное дерево не единственно, но его длина одинакова для всех кратчайших остовных деревьев.
Задачи и упражнения
1.9. С помощью алгоритма Краскала найти кратчайший остов графов, изображенных на рис. 1.14.
1.10. Все площадки для отдыха, расположенные в горной лесопарковой зоне, необходимо соединить телефонной сетью, причем телефонные
линии должны проходить вдоль троп лесопарковой зоны (рис. 1.15). Тре-
16
буется, спроектировать телефонную сеть с минимальной суммарной длиной линий.
4
5
5
10
12
18
5
11
6
17
9
15
11
6
9
14
13
8
10
3
3
G1
G2
Рис. 1.14
7
p2
1
6
4
p5
3
p1
1
1
p6
5
2
4
p8
p3
1
p9
9
4
5
6
7
p4
p7
Рис. 1.15
1.5. Эйлеровы и гамильтоновы графы
Как уже было отмечено, одна из самых первых задач теории графов –
это задача о кенигсбергских мостах. Можно ли, начав с некоторой точки
совершить прогулку и вернуться в исходную точку, пройдя по каждому
мосту ровно один раз. Многие были убеждены, что у этой задачи нет решения. Однако лишь в 1736 году швейцарский математик Л. Эйлер доказал
возможность решения задачи и дал отрицательный ответ на поставленный
вопрос, так как соответствующий граф не содержал эйлерова цикла. С эйлеровыми графами также связана задача китайского почтальона: ребрам
графа приписаны положительные веса, требуется найти цикл, проходящий
через каждое ребро, по крайней мере, один раз и такой, что его суммарный
вес минимален. Очевидно, что если такой граф содержит эйлеров цикл, то
он и будет оптимальным. Эта задача имеет много потенциальных приложений, связанных с проблемой инспектирования распределенных систем,
когда требуется проверить все «компоненты». Например, проверка электрических, телефонных или железнодорожных линий. Другие приложения
могут быть связаны с отысканием наилучшего метода работы автоматических вентиляционных устройств, составлением оптимального маршрута
при уборке помещений и коридоров в больших учреждениях.
17
В 1859 году другой известный математик Гамильтон придумал игру,
где использовался додекаэдр, всем вершинам которого были даны названия известных городов. Задача играющего состояла в том, чтобы определить замкнутый путь через все города, посетив каждый из них только один
раз. Так возникло понятие гамильтонова пути во взвешенном графе. Практические приложения этой задачи весьма разнообразны. Так в ряде отраслей промышленности, особенно химической и фармацевтической возникает следующая основная задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат должен или не
должен быть перенастроен после того, как произведен продукт pi в зависимости от комбинации ( p i , p j ) . Стоимость перенастройки аппаратуры
постоянна и не зависит от продукта, который только что произведен, или
от продукта, следующего за ним, при этом не требуется никаких затрат,
если перенастройка аппаратуры не нужна. Предположим, что продукты
производятся в непрерывном цикле, так что после производства последнего из n продуктов снова возобновляется в том же фиксированном цикле
производство первого продукта. Возникает вопрос, может ли быть найдена
циклическая последовательность производства продуктов, не требующая
перенастройки аппаратуры. Пусть G - ориентированный граф, вершины
которого представляют продукты, а существование дуги ( p i , p j ) означает,
что продукт p j может следовать за продуктом pi без перенастройки аппаратуры. Ответ на поставленный вопрос зависит от того, имеет ли данный
граф гамильтонов контур или нет. Если нет, то какова должна быть последовательность производства с наименьшими затратами на перенастройку.
Другой задачей, связанной с понятием гамильтонова пути, является
задача коммивояжера: коммивояжер должен посетить каждый из заданных n городов, выехав из некоторого города и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояние между каждой парой
городов. С точки зрения теории графов, задача коммивояжера сводится к
поиску гамильтонова цикла минимального веса в полном взвешенном графе, если под весом цикла понимается сумма весов составляющих его ребер. Задача коммивояжера и ее варианты имеют большое число практических приложений в различных областях человеческой деятельности. Например, ее приложениями являются задачи сбора почтовых отправлений из
почтовых ящиков, составления расписания выполнения операций на машинах, проектирования электрических сетей, управления автоматическими
линиями и т.д.
Таким образом, эйлеровы и гамильтоновы графы часто встречаются
в практических задачах и поэтому представляют особый интерес. Рассмотрим более подробно эти понятия.
Определение 1.24. Цикл (цепь), который(-ая) проходит ровно один
раз по каждому ребру неориенированного графа G , называется эйлеровым
циклом (эйлеровой цепью). Граф, в котором существует эйлеров цикл, называется эйлеровым графом.
18
Пример 1.13. На рис. 1.16 а) изображен эйлеров граф, поскольку он
содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 4, 2, 6, 1). На рис. 1.16 б) изображен
неэйлеров граф.
2
C
3
1
A
D
4
B
6
5
а)
б)
Рис. 1.16
Очевидно, что не все графы имеют эйлеров цикл. Более того, справедливо следующее утверждение: почти нет эйлеровых графов (Р.Рейд,
1962 г.).
Теорема 1.5. (Л.Эйлер, 1736 г.) [3, гл.7, § 43] Связный неорграф
является эйлеровым тогда и только тогда, когда степени всех его вершин
четны.
Понятие эйлеровости можно распространить и на орграфы. Имеет
место следующая
Теорема 1.6. Связный орграф G = ( X , U ) содержит эйлеров контур
(эйлеров путь) тогда и только тогда, когда полустепени захода d + ( xi ) и
полустепени исхода d − ( xi ) всех вершин удовлетворяют условиям:
для случая контура d + ( xi ) = d − ( xi ) для всех xi ∈ X ;
для
случая
пути
d + ( xi ) = d − ( xi )
для
всех
x i ≠ p или q ,
d + ( p ) = d − ( p ) − 1 , d − (q) = d + (q ) + 1, где p -начальная, а q - конечная
вершина эйлерова пути.
Естественно возникает вопрос: как найти хотя бы один эйлеров цикл
в эйлеровом графе? Для определения эйлерова цикла в неорграфе используется метод Флери, идея которого заключается в следующем: начав с некоторой вершины, каждый раз вычеркивать пройденное ребро; не проходить по ребру, если удаление этого ребра приводит к разбиению графа на
две связные компоненты (не считая изолированных вершин).
Определение 1.25. Путь, проходящий через все вершины графа в
точности по одному разу через каждую, называется гамильтоновым путем. Если начальная и конечная вершина этого пути совпадают, то такой
путь называется гамильтоновым контуром. Граф, в котором существует
гамильтонов контур, называется гамильтоновым графом.
В неорграфе рассматривают гамильтоновы циклы и цепи.
Пример 1.14. Граф, представленный на рис. 1.17 а), является гамильтоновым, так как последовательность его ребер u1 , u 2 , u 3 , u 4 , u 5 , u 6 , образу19
ет гамильтонов цикл. Граф на рис. 1.17 б) имеет гамильтонов путь, состоящий из ребер u1 , u 2 , u 2 , u 2 , но не имеет гамильтонова цикла.
u5
u6
u5
u1
u4
u6
u4
u7
u1
u2
u3
u3
u2
а)
б)
Рис. 1.17
Несмотря на внешнее сходство постановок, задачи распознавания
эйлеровости и гамильтоновости графа принципиально различны. Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе
гамильтонов цикл или контур. Интуитивно ясно, что если граф содержит
много ребер и эти ребра к тому же достаточно равномерно распределены,
то граф «предрасположен» быть гамильтоновым. В приводимых ниже теоремах можно усмотреть подтверждение этому.
Теорема 1.7. Если G - сильно связный граф на n вершинах без петель, для любой вершины x которого справедливо неравенство
d + ( x) + d − ( x) ≥ n , то G имеет гамильтонов контур.
Теорема 1.8. Простой орграф G , имеющий последовательность степеней d1 ≤ d 2 ≤ ... ≤ d n является гамильтоновым, если из того, что
d k ≤ k ≤ n / 2 следует d n − k ≥ n − k , где n - количество вершин графа.
Отметим, что указанные критерии представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных
графов, встречающихся на практике. С другой стороны, существующие алгебраические методы определения гамильтоновых циклов не могут быть
применены к задачам с более чем несколькими десятками вершин, так как
требуют слишком большого времени работы и большой памяти компьютера. Более приемлемыми являются методы перебора, например, метод Робертса и Флореса [2] и мультицепной метод, которые не предъявляют
чрезмерных требований к памяти компьютера.
Рассмотрим алгоритм алгебраического метода определения гамильтоновых путей и контуров. Сначала введем ряд определений.
Внутреннее произведение вершин пути [ x1 ,..., x k ] определяется как
выражение вида x 2 ⋅ x3 ... ⋅ x k −1 , не содержащее концевые вершины x1 и x k .
Модифицированная матрица смежности B - это матрица размерности n × n , элементы которой определяются следующим образом:
20
 xij , если существует дуга (xi , x j ) ,
bij = 
в противном случае.
 0,
Постановка задачи. Пусть дан орграф G = ( X , U ) . Требуется найти
все гамильтоновы контуры данного графа.
Алгебраический метод выделения гамильтоновых путей и контуров
Шаг 1. Положить k = 1 , Pk = A .
Шаг 2. Положить k = k + 1 и найти Pk = B × Pk −1 .
Шаг 3. Если k = n , то диагональные элементы матрицы Pk дают
внутренние произведения вершин, которые соответствуют гамильтоновым
контурам графа. Получить гамильтоновы контуры.
Иначе перейти к шагу 4.
Шаг 4. Сделать все цепи простыми, обнулив в матрице Pk все диагональные элементы, которые содержат сомножителями вершины, соответствующие данной строке. Перейти к шагу 5.
Шаг 5. Если k = n − 1 , то элементы матрицы Pk дают внутренние
произведения вершин, которые соответствуют данным гамильтоновым путям графа G . Получить гамильтоновы пути.
Иначе перейти к шагу 2.
Еще раз подчеркнем, что построенная матрица Pn−1 дает все гамильтоновы пути, имеющие длину n − 1 , между всеми парами вершин. Поэтому
гамильтоновы контуры можно получать сразу из путей в Pn−1 и тех дуг из
G , которые соединяют начальную и конечную вершины каждого контура.
С другой стороны, гамильтоновы контуры даются членами внутреннего
произведения вершин, стоящими в любой диагональной ячейке матрицы
B ⋅ Pn −1 (все диагональные элементы этой матрицы дают одинаковые контуры).
a
b
d
e
c
Рис. 1.18
Пример 1.15. Рассмотрим граф G изображенный на рис. 1.18, матрица смежности и модифицированная матрица смежности которого равны
21
a

a 0
b 0
A= 
c 0
d  0
e  1
b c d
1
0
1
0
0
0
0
1
1
1
0
0
0 1
0
e

0
1

1

0
0 
a

a 0
b 0
B= 
c 0
d  0
e  a
e

d 0
d e

0 e

0 0
0 0 
b c d
b
0
b
0
0
0
0
c
0 c
′
′
Положим P1 ≡ A . Матрица P2 = B ⋅ P1 получается равной
b
c
a

a0
0
d

0
d +e
′ b e
P2 = 
c e
0
e

d 0
c
0
e  0 a + c
0
d e

b b
0 0

b b
0 c 
a c 
′
Матрица P2 почти такая же, как P2 , - только подчеркнутые элемен′
′
ты в P2 надо заменить нулями. Матрица P3 = B ⋅ P2 равна
b
c
d
e 
a


a  be
dc
bd + be
0
dc 

0
ea
dc 
′ b 0 dc + ea + ec

P3 = 
c  be
ea + ec
bd + be
ea
0 
d  ce
0
0
cb
cb 
e  ce
0
ad
ad + cb ab + cb 
′
Матрица P3 получается из P3 после замены подчеркнутых элементов ну′
лями. Матрица P4 = B ⋅ P3 равна
b
c
d
e
 a



a  dce
0
0
bea
bdc + bdc 

0
ead
eab + ecb
dcb 
′ b  dce

P4 =
c 0
0
ead
bea + eab + ecb
bdc 

d  cbe
cea
0
cea
0

e  cbe adc + cea abd + abe
cea
adc 
Матрица P4 гамильтоновых путей имеет вид
b
c
d
e
 a



a 0
0
0
0
bdc + bdc 

b  dce 0
ead
0
0

P4 = 
c 0
0
0
bea + eab
0



d  cbe cea
0
0
0


e  0 adc abd + abe
0
0

22
Гамильтоновы пути abdce и adcbe , соответствующие элементу (1,5) матрицы P4 , дают гамильтоновы контуры abdcea и adcbea , если добавить дугу (e, a ) . Все другие гамильтоновы пути приводят к тем же самым гамильтоновым путям, и поэтому в графе G существуют только эти два контура.
(Самостоятельно найдите матрицу P5 и убедитесь, что ее диагональные
элементы дают те же контуры).
Задачи и упражнения
1.11. Существует ли эйлеров цикл в графах, изображенных на рис.
1.19?
Рис. 1.19
1.12. Определить (если существуют) гамильтоновы пути и контуры
алгебраическим методом в графах, изображенных на рис. 1.20?
Рис.1.20
1.13. Задача Эйлера о шахматном коне [9]. Найдите такую последовательность ходов шахматного коня, чтобы, начав с произвольной клетки, пройти
через каждую клетку шахматной доски один раз и вернуться в исходную.
1.6. Основные числа теории графов
Число внутренней устойчивости
Определение 1.26. Множество вершин графа называется внутренне
устойчивым (независимым), если никакие две вершины этого множества
не смежны.
23
Определение 1.27. Внутренне устойчивое множество называется
максимальным, если его нельзя пополнить ни одним элементом без нарушения свойства внутренней устойчивости. Наибольшее по мощности
внутренне устойчивое множество называется наибольшим.
Ясно, что наибольшее внутренне устойчивое множество является
максимальным. Обратное, вообще говоря, неверно.
Пример 1.16. Для графа, изображенного на рис. 1.21, множество
вершин {5,8} является внутренне устойчивым, {4,7} – максимальным
внутренне устойчивым множеством, не являющимся наибольшим, а множества {1,2,3,7}, {2,3,5,8} – наибольшими внутренне устойчивыми множествами.
1
2
3
7
5
4
6
8
Рис. 1.21
Определение 1.28. Число элементов в наибольшем внутренне устойчивом множестве графа G = ( X , U ) называется числом внутренней устойчивости и обозначается α (G ) .
Для графа из примера 1.15 число внутренней устойчивости α (G ) = 4 .
К отысканию числа внутренней устойчивости графа сводится, например, известная задача о восьми ферзях, которую связывают с именем
немецкого математика К. Гаусса.
Пример 1.16. (Задача о восьми ферзях.) Чему равно наибольшее количество ферзей, которых можно расставить на шахматной доске так, чтобы ни один ферзь не находился под ударом?
Таких ферзей, очевидно, не может быть более восьми, так как никакие два из них не должны находиться на одной вертикали или горизонтали.
Рассмотрим граф, вершины которого соответствуют клеткам доски, а ребра – парам клеток, лежащих на одной вертикали, горизонтали или диагонали. Ясно, что расстановке ферзей соответствует наибольшее внутренне устойчивое множество. Наибольшее количество ферзей, которых можно расставить на шахматной доске так, чтобы ни один ферзь не находился под
ударом, равно числу внутренней устойчивости α (G ) = 8 , один из вариантов
расстановки ферзей можно найти в [3, гл. IV, § 25].
Множества внутренней устойчивости вершин графа имеют различные применения. Одно из них связано с задачей кодирования в теории информации ([9, гл. 13, п. 13.3].).
24
Число внешней устойчивости
Определение 1.28. Пусть дан граф G = ( X , U ) . Подмножество вершин графа A ⊆ X называется внешне устойчивым (доминирующим), если
каждая вершина из A = X \ A смежна с некоторой вершиной из A .
Определение 1.29. Внешне устойчивое множество называется минимальным, если из него нельзя удалить ни один элемент без нарушения
свойства внешней устойчивости. Внешне устойчивое множество, имеющее
наименьшую мощность, называется наименьшим.
Определение 1.30. Число элементов в минимальном по мощности
внешне устойчивом множестве графа G = ( X , U ) называется числом внешней устойчивости и обозначается β (G ) .
Пример 1.17. Схема тюрьмы представлена в виде графа (рис. 1.22):
вершины – посты караула, ребра – коридоры, куда выходят двери камер.
Какое наименьшее количество охранников требуется, чтобы они видели
все посты?
2
1
6
7
3
4
5
Рис. 1.22
Очевидно, что число внешней устойчивости является минимальным
числом охранников, необходимых для решения этой задачи. Для этого
графа β (G ) = 2. В качестве постов, с которых просматриваются все остальные посты, можно взять, например, множество вершин {2,5}, которое является наименьшим внешне устойчивым множеством.
Пример 1.18. (Задача о пяти ферзях.) Чему равно наименьшее количество ферзей, которых можно расставить на шахматной доске так, чтобы каждая клетка доски находилась под ударом?
Рассмотрим граф, вершины которого соответствуют клеткам доски, а
ребра – парам клеток, лежащих на одной вертикали, горизонтали или диагонали. Ясно, что расстановке ферзей соответствует наименьшее внешне
устойчивое множество. Наименьшее количество ферзей, которых можно
расставить на шахматной доске так, чтобы каждая клетка доски находи25
лась под ударом, равно числу внешней устойчивости β (G ) = 5 , один из вариантов расстановки ферзей можно найти в [3, гл. IV, § 25].
Отыскание в графе минимального внешне устойчивого множества с
наименьшим количеством элементов является сутью многих прикладных
задач. Например, пусть имеется множество населенных пунктов, связанных сетью дорог. В некоторых из них надо разместить предприятия обслуживания так, чтобы расстояние от каждого из населенных пунктов до
какого-либо из предприятий не превосходило заданной величины. Размещение следует выполнить так, чтобы обойтись минимальным количество
предприятий. Если поставить в соответствие населенным пунктам вершины графа, в котором две вершины смежны тогда и только тогда, когда расстояние между соответствующими пунктами не превышает заданной величины, то задача, очевидно, сводится к построению в графе наименьшего
внешне устойчивого множества.
Ядро графа
Определение 1.30. Пусть дан граф G = ( X , U ) . Подмножество вершин графа S ⊆ X называется ядром, если оно одновременно внутренне и
внешне устойчиво.
Существуют графы, у которых нет ядра, а также графы с несколькими ядрами. Например, для графа, изображенного на рис. 1.21, множества
вершин {1,2,3,7}, {1,2,3,8}, {2,3,5,7}, {2,3,5,8}, {4,7} являются ядрами графа.
Теорема 1.9. (Необходимое условие существования ядра в графе.)
Для того, чтобы в графе существовало ядро необходимо, чтобы
α (G ) = β (G ) .
Понятия внутренне, внешне устойчивого множества, ядра естественным образом переносятся на случай ориентированных графов в [3, гл. X, §
67].
Хроматическое число графа
Определение 1.31. Граф G = ( X , U ) , ориентированный или неориентированный, называется r-раскрашиваемым, если его вершины могут быть
окрашены в r цветов так, что никакие две смежные вершины не будут окрашены в один цвет. Такая раскраска графа называется правильной.
Определение 1.32. Минимальное число r, при котором граф является r-раскрашиваемым, называется хроматическим числом графа
G = ( X , U ) и обозначается γ (G ) . Если r = γ (G ) , то граф G = ( X , U ) называется r-хроматическим. Такая раскраска графа называется минимальной.
Для некоторых графов найти хроматические числа несложно. Например, граф является 1-хроматическим тогда и только тогда, когда он
пустой (не содержит ребер). Полный граф на n вершинах имеет хроматиче26
ское число n. Обычно 2-хроматический граф называют бихроматическим.
Справедлива
Теорема 1.10. (Теорема Кенига.) Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной
длины.
Пример 1.19. На рис. 1.23: а) – бихроматический граф,
б) - 4-хроматический граф.
а)
б)
Рис 1.23
Задачи отыскания хроматического числа и построения минимальной
раскраски произвольного графа являются очень сложными, эффективные
алгоритмы их решения неизвестны. Рассмотрим простой алгоритм построения правильной раскраски графа, в ряде случаев приводящий к раскраскам, близким к минимальным.
Алгоритм раскраски
Шаг 1. Найдем степени вершин графа.
Шаг 2. Расположим все вершины графа в порядке невозрастания их
степеней.
Шаг 3. В первый цвет окрашиваем первую вершины из списка, и
двигаясь вдоль списка, в этот же цвет окрашиваем каждую вершину не
смежную с уже окрашенными до нее в этот цвет.
Шаг 4. Берем первую из неокрашенных вершин, двигаясь вдоль списка, и окрашиваем в другой цвет саму вершину и все не смежные с уже окрашенными в этот цвет и т.д.
Пример 1.20. Построить правильную раскраску графа, изображенного на рис. 1.24.
Шаг 1. Найдем степени вершин графа: d ( x1 ) = 4 , d ( x 2 ) = 3 , d ( x3 ) = 4 ,
d ( x 4 ) = 4 , d ( x5 ) = 3 , d ( x 6 ) = 3 , d ( x 7 ) = 3 .
27
Шаг 2. Расположим вершины в порядке невозрастания степеней их
вершин:
x1 , x3 , x 4 , x 2 , x5 , x6 , x7 .
x2
C
B
x3
А
x1
C
x7
C
А
x4
x6
B
x5
Рис 1.24
Шаг 3. Окрасим вершину x1 в цвет А, затем в этот же цвет окрашиваем каждую вершину не смежную с уже окрашенными до нее в этот цвет.
Такая вершина одна - x 4 .
Шаг 4. Берем первую из неокрашенных вершин – это вершина x3 ,
окрашиваем ее в цвет B, двигаясь вдоль списка, окрашиваем и не смежные
с уже окрашенными в этот цвет вершины – это вершина x5 .
Берем первую из неокрашенных вершин – это вершина x 2 , окрашиваем ее в цвет C, двигаясь вдоль списка, окрашиваем все не смежные с уже
окрашенными в этот цвет вершины – это вершины x6 , x7 .
Граф является 3-раскрашиваемым. Раскраска является правильной.
Для наглядности расставим полученные при раскраске цвета рядом с вершинами графа. Так как граф содержит циклы нечетной длины, то согласно
теореме Кенига, он не является бихроматическим. Следовательно, раскраска является минимальной, γ (G ) = 3 ,
а сам граф будет 3хроматическим.
Рассмотрим некоторые практические задачи, сводящиеся к правильной раскраске графа.
1. Задача составления расписаний. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их ведет один и тот же лектор). Построим граф,
28
вершины которого соответствуют лекциям, две вершины смежны тогда и
только тогда, когда соответствующие лекции нельзя читать одновременно.
Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, окрашенные в один цвет, могут читаться одновременно. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения лекций, равно γ (G ) .
2. Задача распределения оборудования. Пусть необходимо выполнить n работ. Известно, что для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При
этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время
выполнения всех работ было минимальным.
Построим граф, вершины которого соответствуют выполняемым работам. Соединим ребром любую пару вершин, если для выполнения соответствующих работ требуется хотя бы один общий механизм. При правильной раскраске графа работы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех
работ достигается при минимальной раскраске и равно γ (G ) .
Проблема четырех красок
Проблема раскраски планарных графов является одной из самых
знаменитых проблем теории графов. Возникшая в середине 19 века, она до
сих пор привлекает внимание специалистов.
Первоначально вопрос формулировался так: достаточно ли четырех
красок для такой раскраски произвольной географической карты, при которой любые две соседние страны окрашены в различные цвета? При этом
рассматриваются те карты, в которых граница любой страны состоит из
одной замкнутой линии, а соседними считаются страны, имеющие общую
границу ненулевой длины.
В 1879 году британский математик А. Кэли опубликовал статью, в
которой сформулировал гипотезу четырех красок: всякая карта 4раскрашиваема. Часто пользуются другой формулировкой гипотезы: всякий планарный граф 4-раскрашиваем.
Первоначально гипотеза четырех красок не показалась сложной и
появилось несколько ее доказательств, в которых позднее были обнаружены пробелы. В дальнейшем эту проблему пытались решить многие известные математики. Большой интерес к гипотезе способствовал открытию
многих важных результатов в теории графов. До сих пор эта проблема остается мощным стимулом исследования различных свойств графов.
Цикломатическое число графа
29
Пусть G = ( X , U ) - связный граф. Обозначим число ребер этого графа через m , число вершин - n . Тогда число
ν (G ) = m − n + 1
называют цикломатическим числом графа G.
Теорема 1.10. Для любого связного графа G цикломатическое число
удовлетворяет неравенству
ν (G ) ≥ 0 .
Причем ν (G ) = 0 тогда и только тогда, когда G является деревом, и ν (G ) = 1
тогда и только тогда, когда G содержит единственный цикл.
В общем случае, когда число компонент связности графа G равно p ,
цикломатическое число находится по формуле
ν (G ) = m − n + p .
Очевидно, что граф G не содержит циклов тогда и только тогда, когда ν (G ) = 0 .
Задачи и упражнения
1.14. Для графа, изображенного на рис. 1.25 укажите внутренне устойчивое, максимальное внутренне устойчивое, наибольшее внутренне устойчивое множества; внешне устойчивое, минимальное внешне устойчивое, наименьшее внешне устойчивое множества. Найдите число внутренней устойчивости, число внешней устойчивости, хроматическое и цикломатическое число. Постройте правильную раскраску.
Рис. 1.25
30
Глава 2. Некоторые оптимизационные задачи на графах
В последнее время интенсивно проводятся исследования в области
синтеза и анализа объектов самой различной природы, обладающих сетевой структурой. К таким объектам, в частности, относятся территориальнораспределенные системы: информационные, транспортные, энергетические и т.п. Хорошим описанием различных коммуникационных сетей служит взвешенный граф, ребрам и вершинам которого приписывают веса,
означающие соответственно пропускные способности линий связи и потребности (производственные мощности) объектов.
В математической постановке многие из подобных задач удается
сформулировать в терминах линейного программирования. Однако оказывается, что удобнее формулировать задачи линейного программирования в
терминах распределения потоков на графах. Это объясняется тем, что для
потоковых задач большой размерности в настоящее время разработаны алгоритмы с высокой вычислительной эффективностью.
2.1. Задача о кратчайшем пути
Задача о кратчайшем пути заключается в нахождении пути минимальной длины от заданной вершины s к заданной вершине t в ориентированном графе. Если граф является взвешенным, то под длиной пути подразумевается сумма длин дуг, которые этот путь составляют; иначе - длина
пути - это количество дуг, образующих путь. Обобщениями задачи о кратчайшем пути являются:
а) задача о нахождении кратчайших путей между вершиной s и всеми
другими вершинами графа;
б) задача нахождения кратчайших путей между всеми парами вершин.
Если определить кратчайшие пути от заданной вершины s ко всем
вершинам графа, то можно построить дерево кратчайших путей. При решении задачи о кратчайшем пути во взвешенном графе следует рассматривать три случая: а) все дуги имеют неотрицательный вес; б) некоторые дуги имеют отрицательный вес, но в графе не существует контуров с суммарным отрицательным весом; в) в сети присутствует один или несколько
контуров с суммарным отрицательным весом. В последнем случае задачу о
кратчайшем пути решить нельзя, но можно обнаружить контуры с отрицательным суммарным весом. В случае а) для поиска кратчайшего пути между заданными вершинами используется алгоритм Дейкстры; для поиска
кратчайших путей между заданной вершиной и всеми остальными может
быть использован также алгоритм Дейкстры. В случаях б) и в) используется алгоритм Форда-Мура [2]. Для определения кратчайшего пути между
всеми парами вершин применим алгоритм Флойда [2].
Конкретная ситуация, приводящая к задаче о кратчайшем пути, может
быть описана следующим образом. Из города s в город t требуется перебросить некоторый груз за кратчайшее время. Обозначим через X множе31
ство, состоящее из s , t и возможных перевалочных пунктов. Две вершины
xi и x j графа соединяются дугой тогда и только тогда, когда из пункта xi
в x j можно попасть. Длиной дуги ( xi , x j ) назовем время, необходимое для
того, чтобы попасть из пункта xi в пункт x j по дуге ( xi , x j ) . Самый короткий путь, ведущий их вершины s в t , в получившемся графе, будет
решением исходной задачи.
Вполне естественным образом к задаче о кратчайшем пути сводятся
задачи поиска маршрутов минимальной длины в коммуникационных сетях. Здесь узлам коммуникационной сети ставят в соответствие вершины
графа, а коммуникациям - дуги графа. Длина ребра характеризует длину
соответствующей коммуникации.
Отметим, что длиной дуги могут служить не только расстояние между
двумя пунктами, но и время движения между ними, стоимость проезда,
расход топлива или энергии и т.д.
Постановка задачи. Пусть дан связный ориентированный граф
G = ( X , U ) , каждой дуге u которого в соответствие поставлено неотрицательное число c(u ) ≥ 0 , называемое длиной этого ребра. Пусть, кроме того,
в графе выделены две вершины: s - начальная вершина, t - конечная вершина. Требуется найти: а) кратчайший путь из вершины s в t ; б) кратчайший путь из вершины s во все остальные вершины графа.
Алгоритм нахождения кратчайшего пути состоит из двух частей. В
первой части определяется длина кратчайшего пути, во второй – сам этот
путь; то и другое осуществляется за конечное число шагов. На первом шаге каждой вершине xi графа G приписывается некоторое число l ( xi ) , которое называется пометкой. Различают пометки двух сортов: временную
и постоянную. Временные пометки меняются на последующих шагах, однако, пометка любой вершины не может меняться бесконечное число раз,
и поэтому, в конце концов, становится постоянной. Процесс изменения
пометок устроен так, что постоянная пометка данной вершины равна наименьшему расстоянию до этой вершины от вершины s .
Алгоритм Дейкстры
Первая часть.
Шаг 1. (присвоение начальных значений). Положить l ( x) = 0 для
x = s и считать эту пометку постоянной. Положить l ( xi ) = ∞ для xi ≠ s и
считать эти пометки временными. Положить p = s .
Шаг 2. (обновление пометок). Для всех xi ∈ Γ( p ) , пометки которых
временные, изменить пометки в соответствии с правилом:
l ( xi ) = min{l ( xi ), l ( p) + c( p, x i )}.
Шаг 3. (превращение пометок в постоянные). Среди всех вершин с
временными пометками найти такую xi* , для которой l ( xi* ) = min{l ( xi )}.
Считать эту пометку вершины xi* постоянной и положить p = xi* .
32
Шаг 4. (i) (Если надо найти лишь путь от s к t .) Если p = t , то l ( p )
является длиной кратчайшего пути. Останов.
Если p ≠ t , то перейти к шагу 2.
(ii) (Если требуется найти пути от s ко всем остальным вершинам.)
Если все вершины отмечены как постоянные, то эти пометки дают длины
кратчайших путей. Останов.
Если некоторые пометки являются временными, перейти к шагу 2.
Вторая часть.
Чтобы найти сам путь, надо поступить следующим образом: положить y = t (или y = x k , в случае (ii)); из всех вершин xi ∈ Γ −1 ( y ) выделить
такую вершину
x , для которой выполняется соотношение
l ( y ) = l ( x) + c( x, y ) ; затем в качестве y рассматривается найденная вершина x - процесс продолжается до тех пор, пока не будет достигнута вершина s , тогда путь из дуг, соединяющих выделенные вершины – искомый
кратчайший путь из s в t (или из s в x k ).
Обоснование алгоритма. Покажем, что постоянные пометки действительно дают длины кратчайших путей.
Заметим вначале, что пометка вершины xi ( l ( xi ) ≠ ∞ ) равна длине
пути от s к xi , который построен алгоритмом к этому моменту, причем
путь проходит полностью по вершинам, имеющим постоянные пометки на
данный момент. Поэтому для доказательства оптимальности пути из s в
xi , соответствующего постоянной пометке l ( xi ) , достаточно доказать, что
постоянная пометка l ( xi ) каждой вершины xi равна длине кратчайшего
пути из s в xi . Доказательство проведем по методу математической индукции [11, гл. 1, § 6].
Пусть вершина xi получила свою постоянную пометку на k -ой итерации, то есть после k -го выполнения шага 3. При k = 1 справедливость
утверждения очевидна. Предположим, что оно верно для вершин, получивших свои постоянные пометки на итерациях 2,3,..., k − 1 . Обозначим через P 0 путь из s в xi , построенный алгоритмом в результате k итераций,
а через P * - кратчайший путь из s в xi . По условию длина пути P 0 равна
l ( xi ) : ∆( P 0 ) = l ( xi ) . Пусть X 1 и X 2 - множество вершин, имеющих соответственно постоянные и временные пометки перед началом k -ой итерации. Рассмотрим две возможные ситуации:
1) Пусть P * содержит вершины из X 2 . Пусть x - первая (считая от
s ) такая вершина, принадлежащая P * , а вершина x′ предшествует x на
пути P * . Согласно выбору x имеем x ′ ∈ X 1 . Обозначим через P1 * часть
пути P * от s до x . По предположению индукции l (x ′) - длина кратчайшего пути из s в x′ . Поэтому
∆( P1 *) = l ( x ′) + c( x ′, x ) ≥ l ( x ) .
33
Поскольку l (x ) - временная пометка, а постоянная пометка l ( xi ) вершины
xi выбирается на k -ой итерации как наименьшая из временных, то
l ( x ) ≥ l ( xi ) . Объединив полученные неравенства имеем
∆ ( P*) ≥ ∆ ( P1 *) ≥ l ( x i ) = ∆ ( P 0 ) ,
то есть P 0 - кратчайший путь из s в xi .
2) Все вершины пути P * входят в X 1 . Пусть x′ и x ′′ - такие вершины, что дуга ( x ′, xi ) принадлежит пути P * , а дуга ( x ′′, xi ) - пути P 0 . Обозначив через P ′ часть пути P * от s в x′ , по предположению индукции
имеем ∆ ( P ′) ≥ l ( x ′) . Поэтому, если x ′ = x ′′ , то сразу получаем неравенство
∆ ( P*) = ∆ ( P ′) + c( x ′, xi ) ≥ l ( x ′) + c( x ′, xi ) = ∆ ( P 0 ) .
Допустим теперь, что x ′ ≠ x ′′ . Поскольку xi получает постоянную
пометку l ( xi ) из вершину x ′′ , а не из x′ , то
∆ ( P*) = l ( x ′) + c( x ′, x i ) ≥ l ( x ′′) + c( x ′′, x i ) = ∆ ( P 0 ) .
Таким образом, и в случае 2) верно неравенство ∆ ( P*) ≥ ∆ ( P 0 ) , то есть P 0
- кратчайший путь из s в xi .
Замечание. 1) Как легко видеть, алгоритм Дейкстры применим и к
смешанным и, в частности, к неориентированным графам. Для этого достаточно каждое неориентированное ребро графа, имеющее вес, рассматривать как пару дуг того же веса; 2) Если кратчайший путь от s в любую
вершину xk является единственным, то дуги этого кратчайшего пути образуют дерево кратчайших путей.
Пример 2.1. Требуется найти кратчайший путь из s во все остальные вершины орграфа, изображенного на рис. 2.1, над дугами графа указаны длина каждой дуги.
Шаг 1. l ( s ) = 0 , l ( xi ) = ∞ для xi ≠ s , p = s .
Первая итерация
Шаг 2. Γ( s ) = {x1 , x 2 , x3 } . Согласно правилу
l ( x1 ) = min{∞,0 + 7} = 7 ,
l ( x 2 ) = min{∞,0 + 1} = 1 ,
l ( x3 ) = min{∞,0 + 3} = 3 .
Шаг 3. min(7,1,3, ∞) = 1 соответствует x 2 .
Шаг 4. x 2 получает постоянную пометку l ( x 2* ) = 1, p = x 2 .
Вторая итерация
Шаг 2. Γ( x 2 ) = {x1 , x 4 , x5 }. Согласно правилу
l ( x1 ) = min{7,1 + 2} = 3 ,
l ( x 4 ) = min{∞,1 + 5} = 6 ,
l ( x5 ) = min{∞,1 + 4} = 5 .
Шаг 3. min(3,6,5, ∞) = 3 соответствует x1 .
Шаг 4. x1 получает постоянную пометку l ( x1* ) = 3 , p = x1 .
34
Третья итерация
Шаг 2. Γ( x1 ) = {x 4 } . Согласно правилу
l ( x 4 ) = min{6,3 + 1} = 4 .
Шаг 3. min(3,4,5, ∞) = 3 соответствует x3 .
Шаг 4. x3 получает постоянную пометку l ( x3* ) = 3 , p = x3 .
Четвертая итерация
Шаг 2. Γ( x3 ) = {x5 }. Согласно правилу
l ( x5 ) = min{5,3 + 5} = 5 .
Шаг 3. min(4,5, ∞) = 4 соответствует x 4 .
Шаг 4. x 4 получает постоянную пометку l ( x 4* ) = 4 , p = x 4 .
Пятая итерация
Шаг 2. Γ( x 4 ) = {t} . Согласно правилу
l (t ) = min{∞,4 + 2} = 6 .
Шаг 3. min(5,6) = 5 соответствует x5 .
Шаг 4. x5 получает постоянную пометку l ( x5* ) = 5 , p = x5 .
Шестая итерация
Шаг 2. Γ( x5 ) = {t}. Согласно правилу
l (t ) = min{6,5 + 6} = 6 .
Шаг 3. min(6) = 6 соответствует t .
Шаг 4. t получает постоянную пометку l (t ) = 6 , p = t .
Все вершины графа получили постоянные пометки. Останов.
Для нахождения кратчайшего пути между вершиной s и t (например) перейдем ко второй части алгоритма. Положим y = t , найдем вершину, для которой l ( y ) = l ( x) + c( x, y ) . Единственной такой вершиной является x 4 . Затем, полагая y = x 4 , аналогично, находим вершину x1 и т.д. Таким
образом, кратчайший путь из вершины s в t имеет длину шесть и проходит по дугам: ( s, x 2 ), ( x 2 , x1 ), ( x1 , x 4 ), ( x 4 , t ) .
x1
x4
1
2
7
2
6
4
1
s
t
5
x5
x2
5
3
x3
Рис. 2.1
s
x1
x2
x3
0
∞
∞
∞
x4
x5
7 3
1
3
6 4
∞
5
5
∞
t
∞
Таблица 2.1
35
6
Результаты вычислений сведены в таблицу 2.1, в первом столбце которой перечислены вершины графа, а в i -том – пометки вершин на (i − 1) ом шаге первой части алгоритма. В кружочек в таблице 2.1 обведены постоянные пометки.
Задачи и упражнения
2.1. Используя алгоритм Дейкстры, найти кратчайший путь из s в t
в графах, изображенных на рис. 2.2.
2
1
1
2
2
4
s
1
3
5
6
s
1
1
2
7
10
t
3
8
9
3
8
9
9
7
G1
G2
3
5
8
3
1
8
2
4
4
5
s
t
4
3
1
6
t
3
6
2
4
5
4
s
7
t
1
2
8
G3
G4
Рис. 2.2
2.2. Используя алгоритм Дейкстры, найти кратчайший путь из 1 в
каждую другую вершину графа, изображенного на рис.2.3.
2
2
1
6
3
4
1
3
6
7
5
4
8
5
5
Рис. 2.3
36
2.2. Задача о максимальном потоке
Определение 2.1. Сетью называется связный ориентированный граф
G = ( X , U ) без петель, каждой дуге ( xi , x j ) которого поставлено в соответствие неотрицательное число rij ≥ 0 , называемое пропускной способностью этой дуги, и такой, что:
1) существует ровно одна вершина s , в которую не заходит ни одна
дуга; эта вершина называется источником;
2) существует ровно одна вершина t , из которой не выходит ни одна дуга; эта вершина называется стоком.
Определение 2.2. Множество чисел {xij } , определенных на дугах
( xi , x j ) ∈U называют потоком в сети, если выполняются следующие условия баланса:
 v, если xi = s,

а) ∑ xij −
∑−1 xki = − v, если xi = t ,
j:x j ∈Γ ( xi )
k :xk ∈Γ ( xi )
 0, иначе.

б) 0 ≤ xij ≤ rij для всех ( xi , x j ) ∈U .
Величиной потока {xij } называется число v ≥ 0 . Поток с максимальной величиной v = v * называется максимальным потоком.
Замечание. Величина потока v = ∑ x sj − ∑ x ks = ∑ x sj , с друj:x j ∈Γ ( s )
гой стороны − v =
∑
x tj
j: x j ∈Γ ( t )
−
v=
∑−1x kt
k : xk ∈Γ
∑
x sj
j:x j ∈Γ ( s )
k :xk ∈Γ
(t )
∑−1x kt .
=
j:x j ∈Γ ( s )
∑−1x kt . Получаем, что
=−
(t )
k : xk ∈Γ − ( s )
k :xk ∈Γ
(2.1)
(t )
Это равенство только подтверждение интуитивно очевидного факта,
что ввиду условия сохранения общее количество материала, выходящего
из источника, равно общему количеству материала, входящего в сток.
Разрез в сети. Пусть R ⊂ X и R = X \ R - множество вершин графа,
не принадлежащих множеству R , тогда множество дуг
( R, R ) = {( xi , x j ) ∈U : xi ∈ R, x j ∈ R }
называется разрезом в сети.
Если при этом источник s ∈ R , а сток t ∈ R , то говорят, что разрез
( R, R ) отделяет s от t .
Любой разрез, отделяющий s от t , содержит по одной дуге каждого
пути в графе G , ведущего из s в t . Таким образом, если из множества дуг
сети изъять дуги произвольного разреза, отделяющего s от t , то не останется ни одного пути, ведущего из s в t .
Пропускной способностью разреза ( R, R ) называется число
r ( R, R ) =
∑ rij ,
( xi , x j )∈( R , R )
37
т.е. пропускная способность разреза равна сумме пропускных способностей дуг, входящих в этот разрез.
Из всех разрезов, отделяющих s от t , минимальным называется разрез ( R*, R *) с минимальной пропускной способностью r ( R*, R *) :
r ( R*, R *) = min r ( R, R ) ,
где минимум берется по всем разрезам, отделяющим s от t . Минимальных
разрезов может быть несколько.
Обозначим через Χ( R, R ) =
∑ xij - сумму потоков ориентиро( xi , x j )∈( R , R )
ванных из R в R . Аналогично, Χ( R , R) =
∑ x ki
- сумма потоков ориен-
( xk , xi )∈( R , R )
тированных из R в R.
В следующем подразделе будет доказана теорема Форда-Фалкерсона
о максимальном потоке и минимальном разрезе, после чего будет рассмотрен помечивающий алгоритм Форда-Фалкерсона определения максимального потока в сети.
Задача о максимальном потоке и ее варианты могут возникать во
многих практических приложениях, например, при определении максимальной интенсивности транспортного потока между двумя пунктами на
карте дорог, представленной графом. В этом примере решение задачи о
максимальном потоке автоматически укажет также ту часть сети дорог, которая «насыщена» и образует «узкое место» в отношении потока между
двумя указанными концевыми пунктами.
Другим примером является коммуникационная сеть, которая изображена ориентированным графом. Каждой дуге сопоставляется число,
равное пропускной способности соответствующей коммуникации (линии
связи, участка водопровода и т.п.). Задача состоит в определении пропускной способности коммуникационной сети между двумя выделенными
вершинами.
Модификации задачи о максимальном потоке:
а) если вместо одного источника и одного стока рассмотреть несколько заданных источников и стоков, причем между различными источниками и стоками протекают потоки различных продуктов, то задача максимизации суммы всех потоков между источниками и стоками называется
задачей о многопродуктовом потоке. В этой задаче пропускная способность дуги является ограничением для суммы всех потоков всех видов
продуктов через эту дугу;
б) если рассмотреть граф, в котором выходной поток дуги равен ее
входному потоку, умноженному на некоторое неотрицательное число, то
задачу о максимальном потоке от s к t называют задачей о потоках с выигрышами. В такой задаче потоки могут и «порождаться» и «поглощаться»
самим графом, так что поток, входящий в s , и поток, выходящий из t , могут независимо изменяться.
38
2.2.1 Теорема Форда-Фалкерсона
Теорема 2.1. Для любого потока величины v и любого разреза
( R, R ) , отделяющего s от t , справедлива следующая формула
v = Χ ( R, R ) − Χ ( R , R ) .
(2.2)
Доказательство. По определению потока и величины потока
 v, если xi = s,
∑ xij − ∑−1 xki = 0, если x ∈ R-{s}.
i
j:x j ∈Γ ( xi )

k :xk ∈Γ ( xi )
Просуммируем по всем вершинам в R , получаем
(2.3)
∑ ∑ xij − ∑
∑ xki = v .
xi ∈R
j:x j ∈Γ ( xi )
xi ∈R
k :xk ∈Γ −1 ( xi )
В левой части этого равенства xij и − xij для i ∈ R и j ∈ R появляются
точно по одному разу и поэтому взаимно уничтожаются. Следовательно,
выражение (2.3) упрощается до
∑ ∑ xij − ∑
∑ xki = v ,
xi ∈R
j:x j ∈Γ ( xi )
x j ∈R
xi ∈R
k :xk ∈Γ −1 ( xi )
xk ∈R
Χ ( R, R ) − Χ ( R , R ) = v .
Следствие 2.1. Формула (2.1) является частным случаем формулы
(2.2). (Доказать самостоятельно.)
Следствие 2.2. Для любого потока величины v и любого разреза
( R, R ) , отделяющего s от t , справедлива следующая формула
v ≤ r ( R, R ) .
(2.4)
Доказательство. Так как xij ≥ 0 и xij ≤ rij для всех ( xi , x j ) ∈U , то из
формулы (2.2) следует
v = Χ ( R, R ) − Χ ( R , R ) ≤ Χ ( R, R ) ≤ r ( R, R ) .
Теорема Форда-Фалкерсона. Величина максимального потока в сети из s в t совпадает с пропускной способностью минимального разреза,
отделяющего s от t в этой сети, т.е. v* = r ( R*, R *) .
Доказательство. Пусть {xij* } максимальный поток в величины v * .
Рассмотрим произвольный разрез ( R, R ) , отделяющий s от t , в силу следствия 2.2, справедлива следующая формула v* ≤ r ( R, R ) .
Покажем, что существует разрез, где v* = r ( R, R ) . Для этого по
имеющемуся максимальному потоку {xij* } построим специальный разрез,
следуя правилу:
1. Начать, полагая R* = {s} .
2. а) Если xi ∈ R * и, кроме того, xij* < rij , то x j включить в множество R * , т.е. x j ∈ R * (правило включения по прямой дуге);
б) Если xi ∈ R * и, кроме того, x *ji > 0 , то x j включить в множество
R * , т.е. x j ∈ R * (правило включения по обратной дуге).
39
Докажем, что при таком способе построения множества R * сток t
не попадет в R * .
Предположим, что существует путь P , соединяющий s и t , по дугам которого последовательно, используя правило 2а или 2б, удалось
включить t в R * .
Пусть
θ 1 = min [rij − xij* ] , если ( xi , x j ) ∈U - прямая дуга,
( xi , x j )
θ 2 = min x ij* , если ( xi , x j ) ∈U - обратная дуга
( xi , x j )
Определим положительное число
θ = min{θ1 , θ 2 } , θ > 0 .
Если теперь величину θ прибавить к потоку во всех прямых дугах и
вычесть во всех обратных дугах цепи, то в результате получится новый поток, на θ больший, чем предыдущий, удовлетворяющий всем ограничениям, накладываемым на поток в сети. Это, очевидно, в силу того, что прибавление величины θ не может привести к превышению ни одной из пропускных способностей, так как θ ≤ θ1 , а вычитание θ из потока в обратных дугах не может сделать поток в этих дугах отрицательным, так как
θ ≤ θ 2 . Условия баланса для всех вершин, кроме s и t , тоже выполнены.
Рассмотрим вершину s , из нее выходит поток величины v * , после
изменения величина потока стала v * +θ , но θ > 0 , следовательно,
v * +θ > v * , но по определению величина потока v * максимальна, получили противоречие, следовательно, такого пути P не существует, поэтому
t ∉ R * , следовательно t ∈ R * .
Таким образом, получили разрез ( R*, R *) который является, вопервых, отделяющим s от t , во-вторых, в силу теоремы 2.1,
v* = Χ( R*, R *) − Χ ( R *, R*) .
(2.5)
Покажем, что этот разрез есть искомый минимальный разрез.
Рассмотрим дуги, входящие в разрез. Пусть ( xi , x j ) ∈ ( R*, R *) , т.е.
xi ∈ R * , x j ∈ R * . Рассмотрим величину максимального потока xij* на дуге
( xi , x j ) ∈ ( R*, R *) . По определению потока: xij* < rij или xij* = rij . Если
xij* < rij , то согласно правилу 2а, x j следует включить в R * , что противо-
речит тому, что x j ∈ R * , следовательно, xij* = rij на всех дугах разреза.
Рассмотрим
величину
максимального
потока
x *ji
на
дуге
( x j , x j ) ∈ ( R *, R*) . По определению потока: x *ji > 0 или x *ji = 0 . Если
x *ji > 0 , то согласно правилу 2б, x j следует включить в R * , что противо-
речит тому, что x j ∈ R * , следовательно, x *ji = 0 на всех дугах разреза.
Итак, xij* = rij и x *ji = 0 .
Просуммируем
40
∑ x ij*
( xi , x j )∈( R *, R *)
=
∑ rij
( xi , x j )∈( R *, R *)
и
∑ x *ji
( x j , xi )∈( R *, R *)
=0.
Χ( R*, R *) = r ( R*, R *) и Χ( R *, R*) = 0 .
Вычтем из первого уравнения второе
Χ( R*, R *) − Χ( R *, R*) = r ( R*, R *) .
В силу равенства (2.5)
v* = r ( R*, R *) ,
то есть величина максимального потока равна пропускной способности
построенного разреза.
Так как v* ≤ r ( R, R ) , то
v* = r ( R*, R *) ≤ r ( R, R ) для любого разреза R .
Следовательно, разрез R * - минимальный разрез.
2.2.2. Алгоритм Форда-Фалкерсона
Постановка задачи. Задача о максимальном потоке заключается в
нахождении такого потока в сети, чтобы величина потока v была максимальной.
Метод решения задачи о нахождении максимального потока в сети.
Решение задачи основано на теореме Форда-Фалкерсона. Условия
задачи могут быть изображены в виде ориентированного графа с двумя
выделенными вершинами s и t , на каждой дуге которого записано некоторое положительное число – пропускная способность этой дуги.
Итог решения задачи: это тот же граф, но на каждой дуге теперь (через запятую после величины пропускной способности) полученное значение xij ≥ 0 - потока на этой дуге. В ответ так же входит величина максимального потока v * и выписанное отдельно множество дуг ( R*, R *) ,
представляющее минимальный разрез.
Метод решения – специальный алгоритм расстановки пометок при
вершинах графа. Чтобы избежать многократного перерисовывания сети,
применяют особый способ записи. Начальный поток на сети считают нулевым, то есть полагают все xij равными нулю.
Алгоритм решения задачи о максимальном потоке и
минимальном разрезе
Расстановка пометок. Вершина может находиться в одном из трех
состояний:
- вершине приписана пометка, и она просмотрена (т.е. она имеет пометку и все смежные вершины "обработаны");
- вершина имеет пометку, но не просмотрена (т.е. не все смежные с
ней вершины "обработаны");
- вершина не имеет пометки.
Пометка произвольной вершины xi состоит из двух частей и имеет
один из двух видов: (+ x j , δ ) или (− x j , δ ) . Часть + x j пометки первого ти41
па означает, что поток допускает увеличение вдоль дуги ( x j , xi ) . Часть
− x j пометки второго типа означает, что поток может быть уменьшен
вдоль дуги ( x j , xi ) . В обоих случаях δ задает максимальную величину дополнительного потока, который может протекать по некоторому пути от s
к xi
Шаг 1. Вершина s помечается специальной пометкой (+ s, ∞) . Вершине s присвоена пометка, все остальные вершины без пометок.
Шаг 2. Выбрать непросмотренную вершину с пометкой (± x k , θ i ) .
а) каждой непомеченной вершине x j ∈ Γ( xi ) , для которой xij < rij
присвоить пометку (+ xi , θ j ) , где θ j = min{θ i , rij − xij } ;
б) каждой непомеченной вершине x j ∈ Γ −1 ( xi ) , для которой x ji > 0
присвоить пометку (− xi , θ j ) , где θ j = min{θ i , x ji } .
Теперь вершина xi и помечена, и просмотрена, а вершины x j , пометки которым присвоены в а) и б), являются непросмотренными.
Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина t не будет
помечена, и тогда перейти к шагу 4, либо t будет не помечена и никаких
других пометок нельзя будет расставить. Если при этом R * - множество
помеченных вершин, а R * - множество непомеченных вершин, то
( R*, R *) - минимальный разрез, а сумме пропускных способностей на дугах этого разреза есть величина максимального потока v * .
Увеличение потока.
Шаг 4. Пусть вершина t имеет пометку (± y, θ t ) , тогда положить
x = t и перейти к шагу 5.
Шаг 5. а) если пометка в вершине x имеет вид (+ z , θ x ) , то увеличить
поток вдоль дуги ( z , x) на величину θ t .
б) если пометка в вершине x имеет вид (− z , θ x ) , то уменьшить поток
вдоль дуги ( x, z ) на величину θ t .
Перейти к шагу 6.
Шаг 6. Если z = s , то стереть все пометки и вернуться к шагу 1, иначе положить x = z и вернуться к шагу 5.
Замечание. После завершения работы алгоритма целесообразно
проверить: 1) Все ли дуги, входящие в минимальный разрез, насыщены потоком, т.е. выполняется ли условие xij * = rij для любой дуги
( xi , x j ) ∈ ( R*, R *) . Если хотя бы для одной дуги этого разреза условия насыщенности нарушено, то задача решена неверно; 2) Кроме того, необходимо убедиться, что сумма всех потоков, выходящих из s , равна v * и совпадает с суммой всех потоков, входящих в t .
Пример 2.2. Найти максимальный поток и минимальный разрез в сети, изображенной на рис. 2.4.
Возьмем в качестве начального потока - поток с нулевыми значениями на всех дугах. Запишем все вершины в первый столбец таблицы 2.2, на42
чиная с s по t . Каждый отчеркнутый столбик соответствует циклу расстановки пометок. Все столбики, кроме последнего, содержат пометку вершины t , в последнем эта пометка не появляется. Именно вершины, помеченные в последнем столбике, и образуют множество R * . Величины потоков на дугах последовательно нарастают, при этом предыдущие меньшие
значения зачеркиваются. Последние полученные цифры и есть максимальные потоки на дугах.
3, 0, 3
x1
x3
8, 0, 4, 7
10, 0, 3, 4
4, 0, 4
t
7, 0, 4
2, 0
s
10, 0, 4, 5
8, 0, 4, 8
5, 0, 4, 5
x2
x4
Рис. 2.4
s
x1
x2
x3
(+s, ∞)
(+ s,8)
(+ s,10)
(+s, ∞)
( + s , 4)
(+ s,10)
(+s, ∞)
( + s , 4)
( + s ,6 )
(+s, ∞)
(+ s,1)
( + s ,6 )
(+ x1 ,3)
(+ x1 ,3)
(+ x1 ,3)
(+ x 4 ,1)
x4
(+ x1 ,4)
(+ x 4 ,4)
(+ x 2 ,5)
(+ x 4 ,4)
(+ x 2 ,1)
(+ x3 ,3)
(+ x 2 ,1)
(+ x3 ,1)
t
(+s, ∞)
(+ s,1)
( + s ,7 )
Таблица 2.2
Алгоритм работает следующим образом.
Шаг 1. Припишем вершине s пометку (+ s, ∞) .
Шаг 2. а) Множество вершин
{x j : x j ∈ Γ( s), x sj < rsj , x j − не помечена} = {x1 , x 2 },
вершине x1 приписывается пометка (+ s, min[∞,8 − 0]) , то есть (+ s,8) ,
вершине x 2 приписывается пометка (+ s, min[∞,10 − 0]) , то есть (+ s,10) .
{
}
б) Множество вершин x j : x j ∈ Γ −1 ( s ), x js > 0, x j − не помечена является пустым. Итак, s помечена и просмотрена, x1 и x 2 помечены и не
просмотрены, а все остальные вершины не помечены. Повторяем шаг 2 и
первой просматриваем вершину x1 .
а) Множество вершин
{x j : x j ∈ Γ( x1 ), x1 j < r1 j , x j − не помечена} = {x3 , x 4 },
вершине x3 приписывается пометка (+x1 , min[8,3 − 0]) , то есть (+ x1 ,3) ,
вершине x 4 приписывается пометка (+x1 , min[8,4 − 0]) , то есть (+ x1 ,4) .
43
{
}
б) Множество вершин x j : x j ∈ Γ −1 ( x1 ), x js > 0, x j − не помечена является пустым. Итак, s и x1 помечены и просмотрены, а x 2 , x3 , x 4 помечены и не просмотрены, а все остальные вершины не помечены.
Беря для просмотра вершину x 2 , найдем, что никаких пометок расставить нельзя.
Беря для просмотра вершину x 4 и повторяя шаг 2, придем к следующим пометкам:
для t пометкой будет (+x 4 , min[4,8 − 0]) , то есть (+ x 4 ,4) .
Вершина t помечена, заносим все полученные пометки во второй
столбец таблицы 2.2, и переходим к шагам 4 и 5 алгоритма. В результате
получим:
x = t ; x 4t = 0 + 4 = 4 ;
x = x 4 ; x14 = 0 + 4 = 4 ;
x = x1 ; x s1 = 0 + 4 = 4 .
Там где значение потока на дугах сети изменилось - зачеркиваем
старые значения потока, и указываем новые. Возвращаясь к шагу 1 для
второго прохода, получим новые пометки вершин, которые мы занесем в
третий столбец таблицы 2.2,
Пометкой для s будет (+ s, ∞) ,
пометкой для x1 будет (+ s, min[∞,8 − 4]) = (+ s,4) ,
пометкой для x 2 будет (+ s, min[∞,10 − 0]) = (+ s,10) ,
теперь вершина s помечена и просмотрена.
Пометкой для x3 будет (+ x1 , min[ 4,3 − 0]) = (+ x1 ,3) ,
теперь вершина x1 помечена и просмотрена.
Пометкой для x 4 будет (+ x 2 , min[10,5 − 0]) = (+ x 2 ,5) ,
теперь вершина x 2 помечена и просмотрена.
Пометкой для t будет (+ x 4 , min[5,8 − 4]) = (+ x 4 ,4) ,
Вершина t помечена, переходим к шагам 4 и 5 алгоритма. В результате получим:
x = t ; x 4t = 4 + 4 = 8 ;
x = x 4 ; x 24 = 0 + 4 = 4 ;
x = x2 ; xs 2 = 0 + 4 = 4 .
Продолжая дальше, получаем после каждого прохода алгоритма поток и пометки, которые записываем на дугах сети и заносим в столбцы
таблицы 2.2. Алгоритм заканчивает работу, когда вершина t не может
быть помечена.
Обозначим множество всех помеченных вершин на последнем шаге
через R * и соответственно R * = X \ R * :
R* = {s, x1 , x 2 }, R * = {x3 , x 4 , t},
( R*, R *) = {( x1 , x3 ), ( x1 , x 4 ), ( x 2 , x 4 )}.
44
Все дуги, входящие в разрез ( R*, R *) , насыщены потоком. Пропускная
способность
найденного
минимального
разреза
равна:
v* = 3 + 4 + 5 = 12 .
Проверим: из s выходит 7 + 5 = 12 единиц потока, а в t входит
7 + 5 = 12 единиц потока.
Задачи и упражнения
2.3. Найти максимальный поток и минимальный разрез для графов,
изображенных на рис. 2.5.
7
4
2
3
s
2
2
3
4
s
t
4
4
3
8
4
2
3
1
1
3
t
8
G1
10
9
8
s
10
5
G2
12
10
1
4
2
8
t
10
14
6
8
s
9
7
2
6
15
6
8
t
1
10
4
G1
G2
Рис. 2.5
2.4. По тропам лесопарковой зоны можно провести ежедневно ограниченное число туристских групп. На рис.2.6 на каждой дуге (a i , a k ) около узла a i указано максимальное число (за один день) групп, которые
можно провести от a i к a k , а около узла a k - максимальное число групп,
которые можно провести от a k к a i . Найти максимальное число (за один
день) групп, которые можно провести от p1 до p9.
0 p2
3 1
5
p1 4
4
0
3
2
4
0
5
p5 1
p3 1
3
0 5
0 p4 3
2
5
1 p6
0
0
p8
3
4
1
0 p7 3
Рис. 2.6
45
0
0
p9
0
Глава 3. Задача сетевого планирования
3.1. Сетевая модель комплекса работ
В настоящее время в связи с осуществлением крупномасштабных
технических проектов, строительством современных предприятий, выполнением сложных научных разработок постоянно приходится решать задачи рационального планирования большого комплекса работ. Например,
строительство промышленного объекта включает в себя создание подъездных путей и энергетических коммуникаций, подготовку строительной техники, подвоз материалов, возведение фундаментов и корпусов, выполнение отделочных работ, установку и отладку оборудования, а также исполнения других необходимых работ и операций. При этом возникает вопрос
об очередности проведения работ, о распределении людей и материальных
ресурсов, о времени, необходимом для выполнения всего проекта в целом.
Все упомянутые и многие другие ситуации имеют некоторые общие
черты, которые мы выделим:
1) вся работа представляет собой комплекс более мелких звеньев,
элементарных работ (например, в случае строительства – это могут быть
подвоз материалов, рытье котлована и т.д.);
2) работы друг друга обусловливают, т.е. не могут выполняться в
произвольном порядке. Для начала одних работ требуется предварительное выполнение некоторых других работ.
Обычными параметрами, которыми интересуются в приведенных ситуациях, являются:
1. Время, необходимое на выполнение, как всего комплекса работ,
так и отдельных звеньев.
2. Стоимость работ всего комплекса и отдельных звеньев.
3. Ресурсы, необходимые для выполнения работ.
При этом возникает задача рационального планирования работ. Для
решения поставленных проблем используются методы сетевого планирования, которые предполагают построение сетевой модели всего комплекса
работ. Сетевая модель изображается в виде сетевого графика, отображающего технологическую взаимосвязь между работами.
Определение 3.1. Ориентированный граф, в котором существует
лишь одна точка A0 , не имеющая входящих вершин, и лишь одна точка An
не имеющая выходящих дуг, каждой дуге которого приписано некоторое
число, называется сетевым графиком.
Определение 3.2. Путь сетевого графика называется полным, если
его начало совпадает с вершиной A0 , а конец с вершиной An .
Как правило, сетевой график имеет большое число полных путей.
Пример 3.1. На рис. 3.1 изображен сетевой график, полными для него являются пути, проходящие через вершины A0 , A2 , A3 , A6 , длина пути
равна 10; A0 , A1 , A3 , A6 , длина пути равна 9 и т.д.
46
A1
5
1
3
3
A2
4
2
5
A0
1
2
A3
3
A5
4
4
A6
6
A4
Рис. 3.1
В сетевом планировании основные элементы сетевого графика (дуги
и вершины) принято называть соответственно работами и событиями:
Термин работа может иметь различные значения:
- действительная работа, требующая затрат времени и ресурсов;
- ожидание – процесс, не требующий затрат труда, но занимающий
время (например, твердение бетона);
- фиктивная работа – логическая связь между двумя или несколькими работами (событиями), не требующая затрат труда и времени. Она
указывает, что возможность начала одной работы непосредственно зависит
от результата другой. Продолжительность фиктивной работы равна нулю.
Событие – это момент завершения какого-либо процесса. Событие
может являться частным результатом отдельной работы или суммарным
результатом нескольких работ. Конечный результат любой работы важен
не только как факт окончания данной работы, но и как необходимое условие для начала следующих работ. Событие может свершиться только тогда, когда закончатся все работы, ему предшествующие. Последующие работы могут начаться только тогда, когда событие свершится. Событие не
имеет продолжительности во времени. Свершение события есть момент
времени, соответствующий моменту окончания последней из работ, непосредственно предшествующих ему.
Сетевой график ограничен исходным и завершающим событиями.
Исходное событие не имеет предшествующих работ и событий и представляет собой формулировку условия для начала работ по выполнению
комплекса работ. Завершающее событие не имеет последующих работ и
событий и представляет собой формулировку конечной цели комплекса
работ.
У всех событий сети, кроме исходного и завершающего, имеются, по
крайней мере, по одной непосредственно предшествующей и по одной непосредственно за ним следующей работе. Событие, непосредственно
предшествующее работе, по отношению к ней называется начальным, а
событие, непосредственно следующее за ней, - конечным.
Виды сетевых моделей зависят от различной интерпретации дуг и
вершин графа. Существует два способа отображения сетевых моделей в
зависимости от того, что будут изображать дуги и вершины – работы или
события:
47
1) сетевые модели в терминах событий – наиболее распространенный способ изображения сетей; события изображаются вершинами, а работы - дугами графа;
2) сетевые модели в терминах работ: в этом случае работы изображаются вершинами графа, а дуги показывают взаимосвязь отдельных работ.
В дальнейшем мы будем пользоваться только первым способом изображения сетевой модели.
Исходная информация о работах, которые требуется выполнить,
должна содержать перечень всех работ, последовательность их выполнения и оценку каждой работы (продолжительность, стоимость и т.п.). Так,
например, информация о некотором проекте может быть задана в виде
структурной таблицы комплекса работ (таблица 3.1).
Таблица 3.1
Структурная таблица комплекса работ
Работа
a2
Опирается
на работы
–
–
a3
a1
a4
a1
a5
a2
a6
a2
a7
a3
a1
Продолжительность работы
3
1
2
4
3
2
1
Работа Опирается
на работы
a8
a3
a9
a 4 , a5 , a 7
a10
a 4 , a5 , a 7
a11
a 6 , a9
a12
a 6 , a9
a13
a8 , a10 , a11
Продолжительность работы
1
1
3
1
5
2
Сетевой график в терминах событий строится следующим образом:
кружками обозначаются события; стрелками, соединяющими события,
обозначаются работы. Сплошными стрелками изображаются действительные работы, пунктирными – ожидания и фиктивные работы.
1
a1
a3
6
a4
a7
a8
a10
4
a13
3
0
a5
a9
2
a6
7
a11
a2
5
a12
Рис. 3.2
Построим сетевой график для последовательности работ, представленной в таблице 3.1. На предварительном этапе события, обозначающие
48
начала или концы работ, можно нумеровать в произвольном порядке.
Пусть 0 - исходное событие. Работы a1 и a 2 не имеют предшествующих
работ, поэтому они выходят из исходного события. В конце дуг, соответствующих работам a1 и a 2 изображаются события, характеризующие окончание этих работ. Обозначим их, например, 1 и 2. Работы a3 и a4 опираются на работу a1 , следовательно, из события 1 выходят две дуги, отвечающие работам a3 и a 4 . Концами этих работ служат события 6 и 3 соответственно. Работы a5 и a 6 опираются на работу a 2 , следовательно, из события 2 выходят две дуги, отвечающие работам a5 и a 6 . Событие, являющееся концом работы a5 , можно объединить с событием 3, так как последующие работы a9 и a10 , как видно из структурной таблицы, обе опираются на работы a 4 и a5 . Событие 5 означает завершение работы a 6 . Указанный процесс продолжается до тех пор, пока не будут построены все работы. На работы a12 и a13 не опирается ни одна работа, поэтому их окончанием служит завершающее событие 7. Сетевой график изображен на
рис. 3.2. Он выражает логическую связь в последовательности событий и
работ.
3.2. Правила построения сетевого графика
При построении сетевого графика следует соблюдать ряд правил, которые позволяют также проверить правильность его построения.
1. В сети не должно быть событий (кроме завершающего), из которых не выходит ни одна работа. Наличие таких «тупиковых» событий указывает на то, что забыта какая-нибудь работа, которая должна выполняться
после этого события, либо предшествующая ему работа не нужна для завершения всего комплекса работ. Если имеется несколько завершающих
событий, то их следует соединить в одно новое завершающее событие
фиктивными работами нулевой продолжительности.
2. В сети не должно быть событий (кроме исходного), в которые не
входит ни одна работа. Если имеется несколько исходных событий, то они
соединяются с одним, вновь введенным исходным событием, фиктивными
работами нулевой продолжительности.
3. В сети не должно быть контуров. Это следует из того, что каждая
работа, входящая в событие, предшествует работе, из него выходящей.
4. Нельзя допускать, чтобы у двух или более выполняемых параллельно во времени работ совпадали и начальное и конечное события. Такие
работы должны завершаться самостоятельными событиями, которые
далее соединяются с одним (для данной группы работ) событием фиктивными работами.
На рис. 3.3 а) и 3.3 б) приведены соответственно неправильный и
правильный способы представления фрагмента сетевого графика.
5. Если для начала какой-либо работы необходимо завершение всех
работ, входящих в предшествующее этой работе событие, а для другой,
49
начинающейся этим же событием, - только части из них, то данное событие разбивается на два, связанных фиктивной работой. В первое из них
входят работы, частный результат которых достаточен для начала одной
работ, а во второе – остальные.
2
1
2
3
1
а)
3
4
б)
Рис. 3.3
3.3. Упорядочение сетевого графика
Для удобства работы с сетью по определению временных параметров
целесообразно произвести упорядоченную нумерацию событий. Под сетью, с упорядоченной нумерацией событий, понимают такую сеть, в которой для каждой работы номер ее начального события меньше номера ее
конечного события. Упорядочение сети можно осуществить с помощью
матрицы смежности (см. определение 1.19). Номерами строк и столбцов
этой матрицы являются номера событий. Упорядочение сети с помощью
матрицы смежности рассмотрим на примере сетевого графика, представленного на рис. 3.2. Матрица смежности для этой сети приведена в таблице
3.2 (нулевые элементы матрицы смежности могут не проставляться).
r r r
r
Обозначим через v0 , v1 , v2 , …, v7 векторы, являющиеся строками
r
матрицы смежности. Найдем компоненты нового вектора V0 по формуле
r r
r r
r
V0 = v 0 + v1 + v 2 + ... + v 7
и припишем их снизу к матрице смежности, в качествеr первой дополнительной строки. Отметим, что i -ая компонента вектора V0 равна числу работ, заканчивающихся i -ым событием. Так как событию 0 соответствует
компонента, равная нулю, то это событие является исходным и образует
нулевой слой. Исключим из дальнейшего рассмотрения событие 0 и работы
r
с началом в этом событии, т.е. исключим вектор v0 . Вычислим компоненты вектора по формуле
r r r
V1 = V0 − v 0
и запишем их во второй дополнительной строке таблицы 3.1. Здесь появилось еще два нуля, соответствующих событиям 1 и 2. Эти нули свидетельствуют о том, что данные события не имеют предшествующих в сетевом
графике без события 0. Следовательно, события 1 и 2 образуют первый
слой. Затем находим вектор поrформуле
r r r
V2 = V1 − v1 − v 2 ,
с одной нулевой компонентой, соответствующей событию 6, которое образует второй слой. Аналогичными вычислениями, как видно из таблицы 3.2,
находятся остальные слои и события, их составляющие.
50
Таблица 3.2
Матрица смежности
0
0
1
2
3
4
5
6
7
r
V0
r
V1
r
V2
r
V3
r
V4
r
V5
r
V6
1
2
1
1
3
4
5
1
1
1
0
События,
вошедшие
в слой
Слой
0
1,2
6
3
5
4
7
0
1
2
3
4
5
6
1
1
1
1
1
1
1
1
0
7
1
1
0
6
3
3
1
0
3
3
3
2
1
0
2
2
1
1
0
1
1
0
2
2
2
2
2
1
0
Упорядоченная нумерация событий производится по слоям. Сначала
в произвольном порядке нумеруются события нулевого слоя, затем первого слоя и т.д. до последнего слоя. Сетевой график с упорядоченной нумерацией событий показан на рис. 3.4.
2
1
3
3
4
1
1
3
6
2
4
0
3
1
2
7
1
1
5
2
5
Рис. 3.4
Работу в сетевых графиках принято кодировать парой (i, j ) , где i номер начального, а j - номер конечного события (рис. 3.5). Так как
51
i
t ij
Работа (i, j )
Рис. 3.5
j
события одного слоя между собой не соединяются, а события, входящие в слой с меньшим номером, имеют меньшие индексы, то в пронумерованной сети для любой работы (i, j ) всегда i < j .
Продолжительность работы t ij принято проставлять в сетевом графике над соответствующей стрелкой.
3.4. Критический путь, критическое время,
ранние и поздние сроки свершения событий
Пусть весь комплекс работ изображен в виде пронумерованного сетевого графика и известна продолжительность t ij каждой работы. Естественно, возникает вопрос: какова минимальная продолжительность всего
комплекса работ. Рассмотрим любой полный путь сетевого графика. Продолжительностью пути называется время, необходимое для выполнения
всех работ, лежащих на этом пути. Обычно на сети существует несколько
полных путей различной продолжительности. Минимальная продолжительность всех работ равна сумме продолжительностей работ, взятых
вдоль самого длительного по времени полного пути. Такой путь называется критическим ( Lкр ), а его продолжительность называется критическим
временем t кр . Таким образом, путь сетевого графика, имеющий наибольшую длину, называется критическим. В сети может быть несколько критических путей, имеющих одинаковую длину. Критический путь имеет
особое значение в системе сетевого планирования, так как работы этого
пути определяют общий цикл завершения всего комплекса работ, планируемых при помощи сетевого графика. Критическое время - это минимальное количество времени, необходимое для выполнения всего комплекса работ.
Работы и события, лежащие на критическом пути, называются критическими, остальные работы и события сети будут некритическими. Если
выполнение какой-либо критической работы будет задержано на некоторый срок, то это вызовет запаздывание выполнения всего комплекса работ
на тот же срок. Некритические работы допускают некоторое запаздывание
с их выполнением, и это не вызывает задержки срока реализации всего
комплекса работ. Очевидно, что ускорить выполнение комплекса работ
можно, сократив сроки выполнения критических работ.
Для отыскания критического пути и критического времени, а также
определения времени, на которое можно задержать выполнение некритических работ, вводятся понятия раннего и позднего сроков свершения событий.
Под свершением события будем понимать момент, к которому заканчиваются все входящие в него работы и может быть начата любая выходящая работа. Событие может иметь некоторый интервал свободы
52
свершения. В связи с этим различают ранний и поздний сроки свершения
события.
Ранний срок t р ( j ) свершения события j равен минимальному сроку, необходимому для выполнения всех работ, предшествующих этому событию. Он определяется продолжительностью самого длительного из
предшествующих ему путей от исходного события до данного события j .
Ранний срок свершения события j может быть подсчитан по формуле:
t р ( j ) = max (t р (i ) + t ij ) ,
(3.1)
i∈Γ −1 ( j )
где максимум распространяется на все события i , непосредственно предшествующие событию j . Для вычисления по формуле (3.1) надо по входящим стрелкам определить все события, непосредственно предшествующие данному, подсчитать для каждого предшествующего события сумму
(t р (i ) + t ij ) и выбрать максимальную из полученных сумм. При расчете для
исходного события принимают, что ранний срок свершения равен 0.
Определение ранних сроков свершения событий следует вести по
формуле (3.1) последовательно от исходного события к завершающему.
При этом около каждого вычисленного значения t р ( j ) записываются номера тех из предшествующих событий, для которых в формуле (3.1) был
достигнут максимум. Эти помеченные события используются при отыскании критического пути, а именно, двигаясь по ним от завершающего события к исходному, будет построен критический путь. Для каждой работы
(i, j ) , лежащей на критическом пути, очевидно, выполняется условие:
t р ( j ) = t р (i ) + t ij . Ранний срок свершения завершающего события определяет продолжительность критического пути t кр .
Любое событие должно наступить не позднее такого предельного
момента, чтобы осталось достаточно времени на выполнение всех работ,
следующих за ним, иначе произойдет задержка реализации всего комплекса работ. Поэтому вводится понятие позднего срока свершения события.
Поздний срок t п (i ) свершения события i равен разности между продолжительностью критического пути t кр и продолжительностью самого
длительного из всех путей от данного события i до завершающего. Поздний срок свершения события i можно подсчитать по формуле:
t п (i ) = min (t п ( j ) − t ij ) ,
(3.2)
j∈Γ ( i )
где минимум распространяется на все события j , непосредственно следующие за событием i . Для вычисления по формуле (3.2) надо по стрелкам, выходящим из события i , определить все события, непосредственно
следующие за данными, подсчитать для каждого из них разность t п ( j ) − t ij
и выбрать минимальную из полученных разностей. При расчете принимают поздний срок свершения завершающего события равным раннему сроку, то есть критическому времени выполнения проекта.
53
Определение поздних сроков свершения событий следует вести последовательно от завершающего события к исходному. При правильном
расчете для исходного события получим t р (0) = t п (0) = 0 . Все события, для
которых t р (i ) = t п (i ) , являются критическими, а последовательность работ,
связывающих эти события, представляет собой критический путь.
При работе с сетевым графиком вручную, если количество событий
невелико, вычисления удобнее проводить прямо на графе. Для этого каждый кружок, обозначающий событие, делят на четыре сектора. Верхний
сектор отводится для записи номера события, левый – для вычисляемого
раннего срока свершения события t р ( j ) , нижний – для номеров тех событий, на которых достигается значение числа, записанного в левом секторе,
и правый для вычисляемого позднего срока свершения события t п (i ) .
В качестве примера вычислим временные параметры событий для
сетевого графика, представленного на рис. 3.4. Результаты вычислений,
представлены на рис. 3.6. Итак, критическое время выполнения комплекса
работ равно t кр = t р (7) = 13 . Искомый критический путь проходит через
события 1, 4, 5, 7. На рис. 3.6 критический путь выделен двойными стрелками.
3
0
3
0
2
1
1
4
0
0
3
5
3
1
7
0
7
13 13
5
1
1
2
0
2
7
3
1
3
6
10 11
4
4
1
1
1
6
8
4
2
5
5
4
8
Рис. 3.6
3.5. Моменты начала и окончания работ. Резервы времени
Основными временными параметрами работ сетевого графика являются моменты их начала и окончания. Для критической работы эти моменты равны срокам свершения начального и конечного событий данной работы. Для некритической работы (i, j ) различают моменты ее наиболее
раннего возможного начала t рн (i, j ) и окончания t ро (i, j ) , а также моменты наиболее позднего допустимого начала t пн (i, j ) и окончания t по (i, j ) .
Ранний срок начала работы равен раннему сроку свершения ее начального события:
t рн (i, j ) = t р (i) .
(3.3)
54
Ранний срок окончания работы равен раннему сроку начала работы,
сложенному с продолжительностью:
t ро (i, j ) = t р (i ) + t ij
(3.4)
Поздний срок окончания работы равен позднему сроку свершения ее
конечного события:
t по (i, j ) = t п ( j )
(3.5)
Поздний срок начала работы равен позднему сроку ее окончания за
вычетом продолжительности работы:
t пн (i, j ) = t п ( j ) − t ij
(3.6)
Работа может обладать резервами времени. Рассмотрим два основных вида резервов времени выполнения работ: полный резерв Rп (i, j ) и
свободный резерв Rс (i, j ) .
Полный резерв времени работы – максимальное количество времени,
на которое можно задержать начало работы или увеличить продолжительность ее выполнения, не изменяя срока завершения всего комплекса работ.
Полный резерв времени равен разности между поздним и ранним
сроками начала (или окончания) работы, а с учетом соотношений (3.3)(3.6) полный резерв равен разности между поздним сроком свершения конечного события работы и ранним сроком окончания этой работы:
Rп (i, j ) = t п ( j ) − t ро (i, j ) = t п ( j ) − t р (i ) − t ij .
(3.7)
Полный резерв времени у критических работ равен нулю. Некритические
работы обладают ненулевым полным резервом. Увеличение продолжительности некритической работы за счет использования всего ее полного
резерва обязательно влечет появление нового критического пути, в состав
которого войдет эта работа.
Свободный резерв времени работы – это максимальное количество
времени, на которое можно задержать начало работы или увеличить продолжительность ее выполнения при условии, что она начинается в свой
ранний срок, не изменяя при этом ранних сроков начала последующих работ. Свободный резерв времени равен разности между ранним сроком
свершения конечного события работы и ранним сроком окончания этой
работы:
Rс (i, j ) = t р ( j ) − t ро (i, j ) = t р ( j ) − t р (i ) − tij .
(3.8)
Из соотношений (3.7) и (3.8) следует, что для любой работы свободный резерв не превосходит полного резерва времени, и для работ, оканчивающихся критическими событиями, эти резервы совпадают. Свободный
резерв времени можно использовать для каждой работы произвольно, им
может распоряжаться непосредственный исполнитель данной работы, так
как затягивание работы в пределах этого резерва не препятствует своевременному исполнению остальных работ. При использовании полных резервов следует согласовать друг с другом время выполнения последующих
работ. Поэтому полным резервом времени должен распоряжаться руководитель всего комплекса работ.
55
3.6. Табличный метод расчета временных параметров
сетевой модели
Для расчета временных параметров сетевой модели предполагается,
что события сети упорядочены, каждая работа закодирована номерами начального и конечного событий, известны продолжительности всех работ.
Алгоритм табличного метода расчета состоит из семи пунктов при
заполнении таблицы 3.3.
Таблица 3.3
Табличный метод расчета
Шифр
работы
Продолжительность
работы
1
(0,1)
(0,2)
(1,3)
(1,4)
(2,4)
(2,5)
(3,4)
(3,6)
(4,5)
(4,6)
(5,6)
(5,7)
(6,7)
2
3
1
2
4
3
2
1
1
1
3
1
5
2
Срок начала
Срок окончания
Резерв времени
работы
работы
работы
ранний поздний ранний поздний полный cвободный
3
4
5
6
7
8
0
0
3
3
0
0
0
3
1
4
3
0
3
4
5
6
1
0
3
3
7
7
0
0
1
4
4
7
3
3
1
6
3
8
5
5
5
6
6
7
1
1
5
10
6
11
5
4
7
7
8
8
0
0
7
8
10
11
1
0
8
10
9
11
2
1
8
8
13
13
0
0
10
11
12
13
1
1
1. В графу 1 заносятся шифры работ в возрастающем порядке начального и конечного событий работ.
2. В графу 2 записываются значения продолжительностей работ.
3. Графы 3 и 5 заполняются совместно по следующим правилам:
а) в графу 3 для всех работ, начинающихся в исходном событии, записывается срок раннего начала, равный нулю: t рн (0, j ) = 0 . В графу 5 всех
работ, начинающихся в исходном событии, записывается срок раннего
окончания, равный продолжительности работы: t ро (0, j ) = t 0 j ;
б) срок раннего начала работы со следующим порядковым номером
начального события равен максимальному из значений сроков ранних
окончаний непосредственно предшествующих работ
t рн (i, j ) = max t ро (k , i ) ,
k
которые отыскиваются в расположенных выше строках графы 5. Полученное значение срока раннего начала работы записывается в графу 3;
56
в) срок раннего окончания работы равен сумме срока ее раннего начала и продолжительности:
t ро (i, j ) = t рн (i ) + t ij ,
в графу 5 записывается сумма чисел, содержащихся в графах 2 и 3;
г) пункты б) и в) повторяются до тех пор, пока не будут заполнены
все строки граф 3 и 5.
4. Графы 4 и 6 заполняются совместно по следующим правилам:
а) в графу 6 для работ, оканчивающихся завершающим событием,
записывается срок позднего окончания, равный максимальному из сроков
раннего окончания этих работ (критическое время). В графу 4 для работ,
оканчивающихся завершающим событием, записывается срок позднего
начала как разность критического времени и продолжительности работы;
б) срок позднего окончания работы со следующим в порядке убывания номером конечного события равен минимальному из значений сроков
поздних начал работ, непосредственно следующих за данной работой
t по (i, j ) = min t пн ( j , k ) ,
k
которые отыскиваются в расположенных ниже строках графы 4. Полученное значение срока позднего окончания работы записывается в графу 6;
в) срок позднего начала работы равен разности между сроком ее
позднего окончания и продолжительностью:
t пн (i, j ) = t по (i, j ) − t ij ,
и в графу 4 записывается разность чисел, содержащихся в графах 6 и 2;
г) пункты б) и в) повторяются до тех пор, пока не будут заполнены
все строки граф 4 и 6.
5. Полный резерв времени работы определяется как разность между
сроками ее позднего и раннего начала (или окончания). В графу 7 записывается разность чисел, содержащихся в графах 4 и 3 (или 6 и 5).
6. Свободный резерв времени работы определяется как разность между сроком раннего начала той работы, начальное событие которой совпадает с конечным событием данной работы, и сроком раннего окончания
данной работы. Свободный резерв времени записывается в графу 8.
7. Из графы 7 выписываются все работы, для которых полный резерв
времени равен нулю. Последовательность этих работ есть критический
путь. Из таблицы 3.3 следует, что критический путь образуют работы (0,1),
(1,4), (4,5), (5,7).
3.7. Линейная карта сети
Сетевой график, хотя и дает четкое представление о порядке следования работ, все же недостаточно нагляден для определения тех работ, которые должны выполняться в каждый данный момент времени. Поэтому в
случае небольшого числа работ полезно после составления пронумерованного сетевого графика составить так называемую линейную карту (диаграмму) сети.
57
Линейная карта может быть построена по ранним и поздним срокам
свершения событий. При построении линейной карты по ранним срокам
момент наступления исходного события считается равным нулю, т.е. все
отрезки (0, j ) откладываются от оси ординат. Отрезок (i, j ) откладывается
так, чтобы его начало лежало на одной вертикали с самым правым концом
всех отрезков-работ, заканчивающихся событием i . Тем самым, начало
каждой работы (i, j ) соответствует раннему сроку t р (i ) наступления события j . Линейная карта, построенная для сетевого графика рис. 3.4, приведена на рис. 3.7. На ней сплошными линиями показаны отрезки-работы,
построенные по ранним срокам свершения событий.
По линейной карте можно определить критическое время, критический путь, а также резервы времени всех работ. Критическое время равно
координате по оси времени самого правого конца всех отрезков линейной
карты. В нашем случае критическое время ( t кр ) равно 13. Критический
путь можно найти следующим образом. Находится отрезок, правый конец
которого расположен на вертикали критического времени t = t кр , это будет
работа (5,7). Затем находится отрезок, правый конец которого расположен
на одной вертикали с левым концом работы (5,7), - это работа (4,5). После
этого находится работа (1,4), и, наконец, работа (0,1), начинающаяся в момент времени t = 0 . Выделенные отрезки-работы образуют критический
путь. Если критических путей несколько, то указанный способ позволяет
найти все критические пути.
Свободный резерв времени Rс (i, j ) работы (i, j ) на линейной карте
определяется как наибольшее расстояние, на которое можно сдвинуть
вправо отрезок (i, j ) , не сдвигая ни одного отрезка с началом j , т.е. не изменяя начала t р ( j ) работ, выходящих из события j . На рис. 3.7 свободный резерв, например, работы (3,6) равен 4, так как отрезок (3,6) можно
сдвинуть вправо на 4, не сдвигая отрезка (6,7). Работа же (4,6) не имеет
свободного резерва, так как любой сдвиг вправо отрезка (4,6) возможен
лишь при таком же сдвиге отрезка (6,7).
Линейная карта сети строится с целью анализа сетевой модели и определения возможности оптимизации хода выполнения работ. По линейной карте можно узнать, например, как распределены материальные или
трудовые ресурсы в каждый момент времени. Допустим, что каждую работу выполняет один человек, при этом он может выполнять любую работу.
Из рис.3.7 видно, что в промежутке времени 5 ≤ t ≤ 6 выполняется три работы (1,4), (3,4), (3,6), и, значит, в течение того времени будет занято три
человека, а в промежутке 6 ≤ t ≤ 7 выполняется только одна работа (1,4), и
необходим один человек. Однако, если сдвинуть работу (3,4) вправо на
единицу (величина ее свободного резерва времени), то во всем промежутке
5 ≤ t ≤ 7 будет выполняться две работы, и будет занято два человека. По
сетевому графику такие взаимосвязи обнаружить значительно труднее.
58
6
5
5
7
6
4
4 5
2
2
3
6
3
4
6
5
4
1
1
0 2
0
7
4
3
1
10
5
13
t
Рис. 3.7
Задачи и упражнения
3.1. Требуется построить сетевую модель и произвести расчет ее
временных параметров: найти критический путь, критическое время, вычислить моменты раннего и позднего начала и окончания работ, полный и
свободный резервы времени работ. Построить линейную карту сети.
а)
б)
Номера
работ, i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Номера работ,
на которые
опирается i-ая
работа
1
1
1
2,3
4
2,3
7,8
7,8
5,6
9,11
10
10
12,14
Продолжи
тельность
i-ой работы
1
3
2
5
4
3
2
4
3
2
1
5
4
2
3
Номера
работ, i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
59
Номера работ,
на которые
опирается i-ая
работа
1
1
2
3
3
3
4,5
4,5
6
6
7,8,10
7,8,10
9,12
9,12
Продолжи
тельность
i-ой работы
4
5
3
4
6
3
7
4
5
5
3
7
5
3
4
3.2. Строительная фирма подписала контракт на строительство нового спортзала для колледжа. В контракте предусмотрены большие штрафы
за невыполнение работы в срок, поэтому для руководителя фирмы важно
выяснить, какие строительно-монтажные работы имеют решающее влияние на сроки окончания строительства. В таблице, составленной плановым
отделом, приведен перечень работ, составляющих процесс строительства
спортзала, указаны их продолжительности и предшествующие каждой из
них работы. Требуется построить сетевую модель и произвести расчет ее
временных параметров, а именно, найти критический путь, критическое
время, вычислить моменты раннего и позднего начала и окончания работ,
полный и свободный резервы времени работ. Построить линейную карту
сети.
Таблица 3.4
Работы
Содержание работы
1
2
3
4
5
6
7
8
8
9
10
11
Подготовка стройплощадки
Укладка фундамента
Монтаж вертикальных стен
Монтаж крыши
Укладка деревянного пола
Отделка внутренних стен
Установка сантехники
Монтаж электропроводки
Установки баскетбольных щитов
Окраска и разметка площадки
Сборка системы отопления
Монтаж внутренних беговых
дорожек
Строительство трибун
Установка электрических табло
Оборудование буфета
12
13
14
60
Продолжительность
(в днях)
1
2
4
7
5
6
4
4
1
2
6
6
Какие работы предшествуют
1
2
3
2
3
3
4
4
5
7,8
5
4
2
2
5,6
6
5,6,7
Заключение
За последние годы теория графов развилась в столь обширный самостоятельный раздел дискретной математики, что невозможно изложить все
основные направления этого раздела в одном пособии. Помимо перечисленных в пособии прикладных задач и алгоритмов их решения существует
целый ряд других методов решения задач теории графов, также применяемых на практике. Кроме того, и сама теория графов располагает более широким аппаратом, чем изложен в данной работе. Поэтому, желая помочь,
тем, кто заинтересовался и хочет продолжить изучение теории графов, наметим здесь направления для дальнейшего чтения.
Тому, кто интересуется в основном "чистой" теорией графов, следует
обратиться к книге Харари [1], которая представляет собой целый ряд всевозможных сведений и является превосходным справочником. Стоит также прочитать работы Оре [9] о планарности графов и проблемах раскрашивания. Обсуждение различных приложений теории графов можно найти у Басакера и Саати [5], Бержа [8]. В книге Кристофидеса [2] достаточно полно представлены разнообразные алгоритмы, связанные с нахождением структурных и числовых характеристик графов.
Библиографический список рекомендуемой литературы
1. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с.
2. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Наука,
1990. – 432 с.
3. Лекции по теории графов / Емеличев В.А., Мельников О.И. и др. – М.:
Наука, 1990. – 384 с.
4. Алгоритмы и программы решения задач на графах и сетях/ Нечепуренко
М.И., Попков В.К. и др. – Новосибирск: Наука, 1990. – 514 с.
5. Конечные графы и сети. / Басакер Р., Саати Т. - М.: Наука, 1974. – 366 с.
6. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. – 207 с.
7. Любкин А.А. Введение в теорию графов. – М.: изд-во МГУ, 1975 . – 134 с.
8. Берж К. Теория графов и ее применение. – М.: ИЛ, 1962. – 319 с.
9. Оре О. Теория графов. – М.: Мир, 1980. – 336 с.
10. Свами М. Графы, сети и алгоритмы. / Свами М., Тхуласираман К. - М.:
Мир, 1984. – 454 с.
11. Шипачев В.С. Основы высшей математики. – М.: Высшая школа, 1994.
– 479 с.
61
Оглавление
Введение..............................................................................................................3
Глава 1. Основные понятия...............................................................................3
1.1. Формы представления графов. Подграфы. Степени вершин.........3
1.2. Путь, цепь, контур, цикл. Связность графа.....................................8
1.3. Матричные представления графов.................................................11
1.4. Деревья..............................................................................................13
1.5. Эйлеровы и гамильтоновы графы...................................................17
Глава 2. Некоторые оптимизационные задачи на графах............................31
2.1. Задача о кратчайшем пути...............................................................31
2.2. Задача о максимальном потоке......................................................37
2.2.1. Теорема Форда-Фалкерсона...............................................39
2.2.2. Алгоритм Форда-Фалкерсона............................................41
Глава 3. Задача сетевого планирования.........................................................46
3.1. Сетевая модель комплекса работ....................................................46
3.2. Правила построения сетевого графика..........................................49
3.3. Упорядочение сетевого графика.....................................................50
3.4. Критический путь, критическое время, ранние и поздние сроки
свершения событий...........................................................................52
3.5. Моменты начала и окончания работ. Резервы времени...............54
3.6. Табличный метод расчета временных параметров сетевой
модели...............................................................................................56
3.7. Линейная карта сети.........................................................................57
Заключение.......................................................................................................61
Библиографический список рекомендуемой литературы.......................61
УЧЕБНОЕ ИЗДАНИЕ
КАВЕРИНА ВАЛЕРИЯ КОНСТАНТИНОВНА
ЗАДАЧИ ОПТИМИЗАЦИИ И ПЛАНИРОВАНИЯ
Учебное пособие
для магистрантов всех направлений
Отпечатано в авторской редакции
Подписано в печать 23.10.2015. Формат 60×84 1/16. Уч.-изд. л. 3,9.
Усл.-печ. л. 4,0. Бумага писчая. Тираж 100 экз. Заказ № .
Отпечатано: отдел оперативной полиграфии издательства учебной литературы и
учебно-методических пособий Воронежского ГАСУ
394006 Воронеж, ул. 20-летия Октября, 84
62
Документ
Категория
Без категории
Просмотров
15
Размер файла
681 Кб
Теги
сетях, оптимизация, планирование, задачи, каверин, 149
1/--страниц
Пожаловаться на содержимое документа