Составители:
Рубрика:
114
вершин, что и в G, дугам которого, соответствую-
щим дугам из G, приписаны единичные веса, а ос-
тальным дугам – бесконечные веса. Если решение
минимаксной задачи коммивояжера для G
1
имеет
конечный вес (на самом деле равный единице), то
в графе G может быть найден соответствующий
гамильтонов цикл. Если же решение имеет беско-
нечный вес, то в графе G не существует никакого
гамильтонова цикла. Следовательно, две указан-
ные задачи можно рассматривать как эквивалент-
ные, поскольку было продемонстрировано, что ал-
горитм
нахождения гамильтонова цикла позволяет
решать минимаксную задачу коммивояжера и на-
оборот.
5. Задачи по теории графов
Задача 5.1.
Как вы помните, охотник за мертвыми ду-
шами Павел Иванович Чичиков побывал у извест-
ных вам помещиков по одному разу у каждого. Он
посещал их в следующем порядке: Манилова, Ко-
робочку, Ноздрева, Собакевича, Плюшкина, Тен-
тетникова, генерала Бетрищева, Петуха, Констан-
жогло, полковника Кошкарева. Найдена схема
(рис.5.1), на которой Чичиков
набросал взаимное
расположение имений и проселочных дорог, со-
единяющих их. Установите, какое имение кому
63
Рис. 1. 23.
Так как v (G) = 8 – 6 + 1 = 3, то для получения ос-
това удаляем из графа три ребра. Сопоставим этим
ребрам номера 1, 2, 3.
Ребрам, входящим в остов, поставим в соот-
ветствие номера 4, 5, 6, 7, 8. Легко видеть, что
фундаментальный цикл С
1
, соответствующий хор-
де 1, состоит из ребер 1, 4, 6, цикл С
2
– из ребер 2,
6, 7, цикл С
3
– из ребер 3, 6, 7, 8. Поэтому матрица
фундаментальных циклов С имеет вид:
1 2 3 4 5 6 7 8
С
1
1 0 0 1 0 1 0 0
С
2
0 1 0 0 0 0 1 0
С
3
0 0 1 0 0 1 1 1
1.15. Разрезы
Понятие разреза играет важную роль при
изучении вопросов, связанных с отделением одно-
го множества вершин графа от другого. Такие за-
дачи возникают, например, при изучении потоков
в сетях.
вершин, что и в G, дугам которого, соответствую-
щим дугам из G, приписаны единичные веса, а ос-
тальным дугам – бесконечные веса. Если решение
минимаксной задачи коммивояжера для G1 имеет
конечный вес (на самом деле равный единице), то
в графе G может быть найден соответствующий
гамильтонов цикл. Если же решение имеет беско- Рис. 1. 23.
нечный вес, то в графе G не существует никакого Так как v (G) = 8 – 6 + 1 = 3, то для получения ос-
гамильтонова цикла. Следовательно, две указан- това удаляем из графа три ребра. Сопоставим этим
ные задачи можно рассматривать как эквивалент- ребрам номера 1, 2, 3.
ные, поскольку было продемонстрировано, что ал- Ребрам, входящим в остов, поставим в соот-
горитм нахождения гамильтонова цикла позволяет ветствие номера 4, 5, 6, 7, 8. Легко видеть, что
решать минимаксную задачу коммивояжера и на- фундаментальный цикл С1, соответствующий хор-
оборот. де 1, состоит из ребер 1, 4, 6, цикл С2 – из ребер 2,
5. Задачи по теории графов 6, 7, цикл С3 – из ребер 3, 6, 7, 8. Поэтому матрица
Задача 5.1. фундаментальных циклов С имеет вид:
Как вы помните, охотник за мертвыми ду-
шами Павел Иванович Чичиков побывал у извест- 1 2 3 4 5 6 7 8
ных вам помещиков по одному разу у каждого. Он С1 1 0 0 1 0 1 0 0
посещал их в следующем порядке: Манилова, Ко- С2 0 1 0 0 0 0 1 0
робочку, Ноздрева, Собакевича, Плюшкина, Тен- С3 0 0 1 0 0 1 1 1
тетникова, генерала Бетрищева, Петуха, Констан- 1.15. Разрезы
жогло, полковника Кошкарева. Найдена схема Понятие разреза играет важную роль при
(рис.5.1), на которой Чичиков набросал взаимное изучении вопросов, связанных с отделением одно-
расположение имений и проселочных дорог, со- го множества вершин графа от другого. Такие за-
единяющих их. Установите, какое имение кому дачи возникают, например, при изучении потоков
в сетях.
114 63
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
