Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
g Совместные репетиции 30 e,f
h Закупка декораций 40 b
i Установка декораций 14 h
j Заказ костюмов 20 с, d
к Подготовка музыкального оформления 30 b
I Работа с осветителями 10 i, g
m Генеральная репетиция 1 g, i, k, I
n Премьера спектакля 1 n
72
Составляем граф, отражающий взаимозависимость операций:
Поскольку операция не может начаться, пока не будут выполнены все
предшествующие операции, общее время, необходимое для выполнения всей
работы, определяется максимальным маршрутом в графе (он называется
критическим путем).
Граф не является ордеревом: в некоторые вершины могут входить несколько
дуг. В тоже время в графе отсутствуют циклы: для любых двух операций
всегда можно однозначно решить, какие из них предшествуют другой (или же
они независимы).
Отсутствие циклов приводит к тому, что в графе (и в любом его подграфе)
найдется хоть одна корневая вершина. Поэтому для нахождения максимального
маршрута можно применить алгоритм Дикстры со следующими модификациями:
a) в качестве ведущей выбирать корневую вершину подграфа, который
получается после удаления всех закрытых к этому времени вершин вместе с
их ребрами.
b) когда у какой-либо вершины появляются две метки (Sj, dx) и (.s'2,
о?2), то оставлять метку с большим значением d.
При практической реализации такого алгоритма удобно вначале подсчитывать
индекс I каждой вершины, равный числу входящих дуг.
После того как вершина х закрывается, следует уменьшить на 1 индекс
каждой вершины, в которую можно попасть из х. Это соответствует удалению
вершины из графа.
Поясним алгоритм на более простом примере:
73
1) Ведущая вершина а
Индекс S d
а 0
Ь 1 а 10
с 0 а 20
d 2
е 2
f 2
2) Ведущая вершина с
Индекс S d
+ а 0
Ь 0 а с 30
- с 0 а 20
d 2
е 1 с 22
f 2
3) Ведущая вершина Ъ
Индекс S d
+ а 0
- Ь 0 с 30
+ с 0 а 20
d 1 Ь 55
е 0 Ь 35
/ 2
4) Ведущая вершина е
Индекс S d
+ а 0
+ Ь 0 с 30
+ с 0 а 20
d 0 Ъ 55
- е 0 Ъ 35
f 1 е 51
5) Ведущая вершина <1
Индекс S d
+ а 0
+ Ь 0 с 30
+ с 0 а 20
- d 0 Ь 55
+ е 0 Ь 35
f 0 d 58
6) Ведущая вершина /
Индекс S d
+ а 0
+ Ь 0 с 30
+ с 0 а 20
+ d 0 b 55
+ е 0 Ь 35
+ I 0 d 58
Теперь все вершины закрыты и в окончательной таблице величина d(x) равна
максимальной длине пути а -* х.
Критический путь а -* / имеет вид
Путь = (а, с, Ъ, d,f),
а длина его равна 58.
То, что описанный алгоритм решает поставленную задачу, можно доказать
следующим образом.
Пусть W-множество уже закрытых вершин на некотором шаге алгоритма. Тогда
для любой помеченной вершины л: метка d(x) равна максимальной длине пути
из а в х, в котором все промежуточные вершины принадлежат W. Выбираем
теперь очередную ведущую вершину х ? W. Ее индекс равен 0, и таковым он
стал благодаря удалению некоторых вершин из множества W.
Таким образом в вершину л: можно попасть лишь из некоторой вершины у Е W.
В свою очередь вершина >' была когда-то ведущей, и в нее можно попасть
только из множества W. Таким образом: любой путь, ведущий в х, состоит из
вершин множества W. Поэтому d(x) является максимальной длиной по всем
путям а -* х.
4.10. Эйлеров граф
Мультиграф называется эйлеровым, если существует замкнутый путь,
проходящий через каждое ребро ровно один раз. Эйлеров граф можно
нарисовать, не отрывая карандаш от бумаги. Можно представить себе также
путешественника, который отправляется в путь, начиная с некоторой
вершины, по ребрам (мостам) графа, имеющим одностороннее движение (даже
для пешеходов). После того, как очередной мост пройден, он взрывается.
Если граф эйлеров, то существует такой вариант обхода, при котором в
конце путешествия путник оказывается в начальной вершине, а все мосты
уничтожены. Соответствующий обход называется эйлеровым контуром.
75
Пусть х-некоторое слово, Где-его циклический сдвиг. Пара слов х (r) Тх,
очевидно, соответствует некоторому эйлерову графу:
х (abadabbcdc\
Txybadabbcdca)'
Каждое ребро графа соответствует паре соседних букв слова х, так что
слово х и является эйлеровым контуром.
С другой стороны, если задан граф, то мы превращаем его в пару слов <8>
у0, где слово xQ отсортировано:
х0 faaabbbccdd'
bbdabcadac
\ /
Кроме того, мы знаем переходную матрицу:
abed
а 2 1 3
b 1 1 1 3
с 1 1 2
d 1 1 2
3 3 2 2 10
В то же время совсем не ясно, существует ли такое слово х, что дс0 (r) у0 и
х(r) Тх определяют один и тот же граф. Одно
несомненно:
Граф xQ <S> _у0 является эйлеровым тогда и только тогда, когда а(х0 (r) У0)
= х (r) Тх
для некоторого слова х и некоторой подстановки а.
Отсюда заключаем:
Если граф xQ (r) yQ эйлеров, то он является связным графом
и слова Xq и имеют одну и ту же композицию.
Это значит, что в переходной матрице суммарный столбец совпадает с
суммарной строкой (в нашем примере 3, 3, 2, 2). Оказывается, что эти
условия являются также достаточными: Связный граф xQ <8> з"0, у которого
и имеют одну и
ту же композицию, является эйлеровым.
Для доказательства мы должны построить эйлеров путь, т.е. найти такое
