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