Урок 10

Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе

Термины теории графов

Уточни формулировки новых понятий.

Вершина графа

Схематическое отображение объекта.

Ребро

Схематическое отображение связи между объектами.

Путь в графе

Последовательность ребер, соединяющая две выбранные вершины, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается боле одного раза.

Ориентированный граф

Граф, в котором направление ребер принципиально.

Исток

Вершина в ориентированном графе, в которую не входит ни одно ребро.

Сток

Вершина в ориентированном графе, из которой не выходит ни одно ребро.

Взвешенный граф

Граф, ребра которого имеют числовое значение, например, цена или километраж.

Весовая матрица

Табличная модель графа, значения в которой соответствуют весам ребер.

Циклический граф

Граф, в котором начальная и конечная вершины совпадают.

Эйлеров граф

Граф, содержащие эйлеров путь. Цикл без повторения ребер, обходящий все вершины графа.

Поиск кратчайшего пути в графе

Для данного нециклического ориентированного графа найдите кратчайший путь из вершины А в вершину G.

Исходный граф

Шаг 1

Отметь все вершины непосещенными.

Шаг 2

Присвой первой вершине метку ноль. Это будет вершина-источник. А метка равна расстоянию до нее.

Шаг 3

Оцени минимальные расстояния до всех смежных вершин, пометь их следующей по порядку меткой.

Шаг 4

Если следующая вершина отмечена как посещенная, завершите алгоритм. Иначе переходите к шагу 3.

Шаг 5

Как в пункте 3 пометьте непосещенную вершину (E, F) следующей меткой, посчитайте минимальное расстояние до них.

Шаг 6

Шаг 4 не выполнится, потому что остается еще непосещенная вершина G.

Шаг 7

Все вершины отмечены как посещенные. Алгоритм завершен.

Самостоятельная практическая работа

Выполни аналогичное задание.

Вариант 1

Для данного нециклического ориентированного графа найдите кратчайший путь из вершины А в вершину K.

Вариант 2

Для данного нециклического ориентированного графа найдите кратчайший путь из вершины А в вершину K.

Вычисление количества путей в направленном ациклическом графе

Миша живет на Урале в городе Березовск, у него много друзей, которые живут в разных городах. В свободное от уроков время он составил маршруты, по которым хотел бы проехать и навестить своих друзей. Посчитай, сколько разных маршрутов приведут Мишу в город Жуковский — подмосковный наукоград и в Екатеринбург — крупнейший административный, культурный, научно-образовательный центр Урала.

1. Составление таблицы

Составим таблицу, в которую будем заносить откуда отправляется Миша, куда намерен прибыть и сколько различных путей приведёт его туда.

2. Заполнение таблицы

Рассмотрим пример города Златоуст, туда Миша может приехать из Дмитрова, но в Дмитров он может попасть двумя различными путями, поэтому и в Златоуст он попадёт двумя путями, сразу из Березовска или через Верхотурье.

Начнем заполнять:

3. Ответ на вопрос задания

В Жуковский можно доехать тремя путями, в Екатеринбург — двумя.

4. Самостоятельная практическая работа

Выполни задание:

На рисунке – схема дорог, связывающих города A, H, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город G?

9_1_3.pptx

Урок 2. Графы

Интерактивные тесты

Домашнее задание. §1.3, вопросы и задания № 1–4, 7, 11 к параграфу; № 35, 37, 39, 41 в РТ. Дополнительное задание: № 44 или № 45 в РТ.

Page updated

Google Sites

Report abuse