Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие
Подождите немного. Документ загружается.
2.1. ГРАФЫ
Рис. 10
неизбежно вернемся в вершину А, а вернувшись, окажемся перед
двумя возможными ситуациями: 1) в построенный нами цикл вхо-
дят все ребра графа, 2) остались еще не пройденные ребра.
Первый случай не так интересен: если в построенный цикл входят
все ребра, то поставленная задача решена. Что же касается второго
случая, то здесь в полученном нами цикле (обозначим его через Л)
обязательно есть вершина, из которой выходит еще не пройденное
нами ребро. Пусть это вершина В. Об этой вершине можно сказать
даже больше: число выходящих из нее ребер, не принадлежащих по-
строенному циклу Л, обязательно четно. И мы строим новую цепь из
вершины В, привлекая только ранее не пройденные ребра. Ясно, что
в результате мы вернемся в вершину В и получится новый цикл —
В (рис. 11).
Рис. 11
31
ГЛАВА 2. ГРАФЫ И СЕТИ
Теперь легко получить цикл, начинающийся в вершине А и боль-
ший построенного ранее цикла А.
Для этого мы сначала перемещаемся по маршруту А от вершины
А до вершины В, затем проходим по циклу В и, вернувшись в вер-
шину В, завершаем перемещение в вершину А по оставшейся части
цикла А (рис. 12).
Рис. 12
Если мы и на этот раз не прошли по всем ребрам графа, то, вы-
брав вершину цикла, построенного по циклам А и с. 12 которой
исходят ребра, не входящие в этот цикл, расширяем его описанным
выше способом.
Повторяя в случае необходимости подобные рассуждения доста-
точное число раз, мы всегда сможем построить эйлеров цикл за ко-
нечное число шагов.
Пример 2. Устроители больших художественных выставок
часто вынуждены решать одну и ту же задачу: как организовать
осмотр, чтобы дать возможность в отведенное время ознакомиться
со всей экспозицией наибольшему числу желающих.
Ясно, что для этого нужно расставить указатели таким образом,
чтобы, перемещаясь в соответствии с предложенными в них рекомен-
дациями, любой посетитель мог побывать у каждой картины ровно
по одному разу.
Если вход и выход совпадают, то разместить экспонаты следует
так, чтобы схема экспозиции была эйлеровым графом. Что же ка-
сается указателей, то они должны 1) быть снабжены порядковыми
номерами и 2) описывать эйлеров цикл (рис. 13).
32
2.1. ГРАФЫ
Рис. 13
Рис.
Ц
Если же вход и выход разные, то схема размещения экспонатов
должна быть графом, у которого лишь две вершины, соответствую-
щие входу и выходу, являются нечетными. На рис. 14 приведен один
из возможных способов расстановки пронумерованных указателей,
позволяющий посетителям ознакомиться с каждым экспонатом.
Эйлеровы циклы характеризуются тем свойством, что они прохо-
дят через каждое ребро графа в точности по одному разу.
Аналогичным образом, но только по отношению к вершинам оп-
ределяются для конечных связных графов так называемые гамилъ-
тоновы циклы:
цикл называется гамильтоновым, если он проходит через ка-
ждую вершину графа ровно по одному разу.
Рис. 15
На рис. 15 приведены гамильтоновы циклы для нескольких про-
стых графов.
Между эйлеровым и гамильтоновым циклами легко просматри-
вается довольно прозрачная аналогия: первый проходит ровно один
раз по каждому ребру, второй — ровно один раз через каждую вер-
шину. И на первый взгляд естественно ожидать того, что задача про-
верки, допускает ли данный граф гамильтонов цикл, должна быть
3 Зак. 7492
33
ГЛАВА 2. ГРАФЫ
И
СЕТИ
по сложности сравнима с аналогичной задачей для эйлерова цикла
(где достаточно подсчитать четность каждой вершины). Однако на
деле все обстоит значительно сложнее: несмотря на практическую
важность этой проблемы, до сих пор не найдено ни общего критерия,
позволяющего устанавливать, является ли заданный граф гамиль-
тоновым, ни универсального эффективного алгоритма построения
гамильтонова цикла.
Проблема, восходящая своей постановкой к У. Р. Гамильтону, во-
обще оказалась очень трудоемкой. Поэтому не стоит удивляться то-
му, сколько усилий высококвалифицированных математиков и про-
граммистов потребовалось и на какие вычислительные затраты при-
шлось пойти для того, чтобы рассчитать до конца кратчайшую воз-
душную линию, соединяющую столицы всех североамериканских
штатов.
Одной из практических задач, связанных с построением гамиль-
тонова цикла, является задача о коммивояжере, в которой нужно
найти кратчайший путь, проходящий через заданные пункты (все
расстояния известны) и возвращающийся в исходный пункт.
Так как число пунктов конечно, то в принципе задача может быть
решена простым перебором.
Пример 3. Торговец, живущий в городе А, намерен посетить го-
рода В, С и D, расстояния между которыми ему известны:
АВ - 11, АС = 13, AD = 17, ВС = 6, BD = 9, CD = 10
(рис. 16). Требуется указать кратчайший циклический маршрут из
города
А,
проходящий через три других города.
Возможных циклических маршрутов шесть:
ABCDA, ACDBA, ADBCA, ACBDA, ABDCA, ADCBA.
34
2.2. СЕТИ
Однако для решения задачи достаточно сравнить длины только пер-
вых трех:
ABCDA, ACDBA, ADBCA.
Эти длины равны соответственно
11 + 6 + 10 + 17 = 44, 13 + 10 + 9 + 11 = 43, 17 + 9 + 6 + 13 = 45.
Тем самым, кратчайшим является любой из маршрутов длиной
43 — ACDBA или ABDCA.
Важный класс графов составляют так называемые деревья. Де-
ревом называется связный граф, который не имеет циклов (рис. 17).
Рис. 17
Число В вершин дерева и число Р его ребер различаются на еди-
ницу:
2.2. Сети
В приложениях граф обычно интерпретируется как сеть, а его вер-
шины называют узлами.
Рассмотрим несколько характерных задач.
2.2.1. Дерево решений
При принятии важных решений для выбора наилучшего направле-
ния действий из имеющихся вариантов используется так называемое
дерево решений, представляющее собой схематическое описание про-
блемы принятия решений.
35
ГЛАВА 2. ГРАФЫ И СЕТИ
Применение дерева решений подразумевает понимание (хотя бы
интуитивное) таких понятий, как "вероятность" и "ожидаемое зна-
чение (математическое ожидание) случайной величины". Подробно
эти понятия обсуждаются в последующих главах.
Пример 4- По настоянию родителей выпускник американской
школы должен продолжить учебу. Свободный в своем выборе, он
хочет оценить возможности получения диплома в области инжини-
ринга или в области бизнеса в одном из двух университетов — в
университете родного города Йорка и в университете штата, пони-
мая, что вероятность успеха зависит от выбора как университета,
так и будущей специальности.
1. Если он останавливает свой выбор на университете штата и биз-
несе, то вероятность успеха (получение диплома) считается равной
0,60.
2. Если он останавливает свой выбор на университете штата и
инжиниринге, то вероятность успеха считается равной 0,70.
3. Если он останавливает свой выбор на университете г. Йорка и
бизнесе, то вероятность успеха считается равной 0,90.
4. Если он останавливает свой выбор на университете г. Йорка и
инжиниринге, то вероятность успеха считается равной 0,95.
5. Средний доход за год в течение первых пяти лет у окончивше-
го бизнес-школу университета штата при условии полной занятости
равен 35 тыс. долл.
6. Средний доход за год в течение первых пяти лет у. окончив-
шего школу инжиниринга университета штата при условии полной
занятости равен 30 тыс. долл.
7. Средний доход за год в течение первых пяти лет у окончившего
бизнес-школу университета г. Йорка при условии полной занятости
равен 24 тыс. долл.
8. Средний доход за год в течение первых пяти лет у окончивше-
го школу инжиниринга университета г. Йорка при условии полной
занятости равен 25 тыс. долл.
9. Если по каким-либо причинам выпускник не поступает ни в
один из этих университетов, то его средний доход в течение этих
пяти лет при условии полной занятости будет равен 18 тыс. долл.
Предположим, что единственным критерием при принятии вы-
пускником окончательного решения является величина ожидаемого
36
2.2. СЕТИ
среднего дохода в первые пять лет его трудовой деятельности. Сде-
лав это предположение, попробуем решить проблему выпускника,
используя дерево решений (рис. 18).
Рис. 18
Поясним некоторые обозначения на рисунке:
S\
— окончание бизнес-школы университета штата,
^2
— либо неудача при поступлении в бизнес-школу университета
штата, либо невозможность завершения обучения,
5з
— окончание школы инжиниринга университета штата,
.S4
— либо неудача при поступлении в школу инжиниринга уни-
верситета штата, либо невозможность завершения обучения,
5*5
— окончание бизнес-школы университета города Йорка,
5б
— либо неудача при поступлении в бизнес-школу университета
города Йорка, либо невозможность завершения обучения,
SV
— окончание школы инжиниринга университета города Йорка,
S$ — либо неудача при поступлении в школу инжиниринга уни-
верситета города Йорка, либо невозможность завершения обучения,
d\
— выбор университета штата,
d
2
— выбор университета города Йорка,
d
3
— предпочтение отдано бизнесу,
б?4
— предпочтение отдано инжинирингу.
Узлы дерева, в которых делается выбор, обозначены квадрати-
ками; узлы дерева, которые принимающий решение не контролиру-
ет, — кружками.
37
ГЛАВА 2. ГРАФЫ
И
СЕТИ
Эти два типа узлов рассчитываются по-разному.
При расчете узлов 4-7 определяются ожидаемые значения:
значение в узле 7
N
7
= (0,95)(25 000) + (0,05)(18 000) = 24 650 долл.,
значение в узле 6
N
6
= (0,90)(24 000) + (0,10)(18 000) = 23400 долл.,
значение в узле 5
N
5
= (0,70)(30 000) +
(0,30)(18
000) = 26 400 долл.,
значение в узле 4
JV
4
= (0,60)(35 000) +
(0,40)(18000)
= 28 200 долл.
Значение
N^
в узле 3 определяется так:
вследствие того что
iV
7
>
Л
Г
6,
полагаем
JV3
=
N
7
и
считаем, что
выбор
d,4
предпочтительнее выбора
d
3
.
Тем самым,
]У
3
= 24 650 долл.
$ 28 200
Рис.
19
Значение
Л^
в узле 2 определяется так:
вследствие того что
iV
4
>
N5,
полагаем
выбор
d$
предпочтительнее выбора
оЦ-
Тем самым,
iV
2
=
28 200 долл.
51
$35 000
5
2
$18 000
5
3
$30000
5
4
$18000
$24000
S
6
$18 000
$25 000
S
8
$18 000
и считаем, что
38
2.2. СЕТИ
Значение
iVi
в узле 1 определяется так:
вследствие того что
N2
>
iV
3
,
полагаем
N\
=
iV
2
и считаем, что
выбор
d\
предпочтительнее выбора
di-
Тем самым,
N
x
= 28 200 долл.
Наносим результаты расчетов на рис. 18 и принимаем оконча-
тельное решение (рис. 19).
2.2.2. Задача о соединении городов
С деревьями связана и одна из проблем минимального соединения,
внешне напоминающая задачу о коммивояжере, но значительно про-
ще разрешаемая (для решения этой проблемы построены эффектив-
ные алгоритмы).
Имеется п городов —
А\, А
2
,
...,
А
п
,
которые нужно связать ме-
жду собой сетью дорог. Стоимость сооружения дороги, соединяющей
города
Ai
и
Ak,
известна и равна
c(Ai,Ak).
Какой должна быть сеть дорог, связывающая все города, чтобы
стоимость ее сооружения была минимальной?
Граф наиболее дешевой соединяющей сети непременно должен
быть деревом. (В противном случае в графе найдется хотя бы один
цикл. При удалении любого из звеньев этого цикла стоимость сети
уменьшится, а города все еще останутся соединенными.) Тем самым,
число ребер искомого графа должно быть равным п —
1.
Алгоритм (план реализации)
На 1-м шаге связываем два города с наиболее дешевым соединя-
ющим звеном
в\.
На каждом следующем шаге добавляем самое дешевое из звеньев
е,
(если имеется несколько звеньев с одинаковой стоимостью, выби-
раем любое из них), в результате присоединения которого к уже по-
строенным звеньям найденная сеть удлиняется еще на одно звено, но
никакого цикла не образуется. При поиске добавляемого звена надо
перебирать все ребра, имеющие общую вершину с уже построенной
сетью.
Последний шаг алгоритма имеет номер п — 1.
Стоимость строительства полученной сети минимальна и равна
c(ei)
+
с(е
2
)
+
hc(e
n
_i).
39
ГЛАВА 2. ГРАФЫ
И
СЕТИ
Пример 5. Пусть, например, нужно соединить города А, В, С и
D. Стоимость строительства дорог, соединяющих любые два города,
известна и в условных единицах представлена в таблице:
Сеть дорог минимальной стоимости состоит из 3 (4—1 = 3) звеньев
и строится так: сначала выбирается самый дешевый участок доро-
ги — ВС (его цена равна 6), затем он удлиняется на самый дешевый
из оставшихся — BD (его цена равна 9). И на последнем, третьем
шаге вновь выбирается самый дешевый (но так, чтобы не образова-
лось никакого цикла) — АВ (его цена равна 11) (рис. 20). Таким
образом, стоимость строительства равна 26 (6 + 9 + 11).
Рис. 20
2.2.3. Максимальный поток
Задана сеть, каждое ребро которой имеет вполне определенную ог-
раниченную пропускную способность. Требуется определить макси-
мально возможный поток в этой сети из заданного узла в другой
узел.
Чтобы пояснить основную идею метода решения этой задачи,
предположим, что исходный и конечный пункты, пункт А и пункт
В,
находятся на разных берегах разделяющей их реки (рис. 21). Мно-
жество мостов через реку образуют так называемое разделяющее се-
чение (если все мосты по каким-либо причинам выйдут из строя,
40