II. Задачи для усвоения материала.
I. Необходимые определения и формулировки теорем.
IV. Решение некоторых типовых заданий.
III. Самостоятельная работа 7.
1. Постройте граф для решения следующей задачи:
Имеются трёхлитровая банка сока и две пустые банки: одна - литровая, другая - двухлитровая. Как разлить сок так, чтобы во всех трёх банках было по одному литру?
1. Постройте граф для решения следующей задачи:
Имеются трёхлитровая банка сока и две пустые банки: одна - литровая, другая - двухлитровая. Как разлить сок так, чтобы во всех трёх банках было по одному литру?
Решение.
Считаем, что вершины графа – «количество сока в банках по порядку: в трёхлитровой, двухлитровой, однолитровой», ходы – «переливания». Тогда для решения задачи получаем граф:
9. «Поиск путей в графе».
1. Что такое «вес дуги (ребра)»?
2. Какой граф называется взвешенным?
3. Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?
4. Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?
1. Сколько существует простых путей (в которых ребра не повторяются, а вершины могут повторяться) из левой нижней в правую верхнюю вершину в данном графе?
| а)
| б*) |
2. Найти кратчайший путь из A в B в графе:
B
A
3.* Найти кратчайший путь от входа к выходу.
1. Найти кратчайший путь из вершины А в вершину F во взвешенном графе:
2. В государстве Футболия дороги платные (стоимость проезда указана на карте):
Как дешевле всего проехать из Радченко-Ленд в Степченко-Сити и сколько это стоит?
3. То же для государства
Как дешевле проехать из столицы в Улан-Кар?
4. Волк охотится за зайцем. Пройти по дороге он может, если подружится с воронами, охраняющими дороги.
С каким наименьшим количеством ворон придётся подружиться волку?
8. В государстве Гардарика почти все дороги платные. Как дешевле попасть из Северного замка в Южный и сколько ракушек понадобится для беспрепятственного проезда?
9. В штате Вайоленд дороги платные (стоимость проезда указана на карте):
Как дешевле всего проехать из Нэшройта в Детвилл и сколько это стоит?