Тема — Моделирование на графах

Цели и задачи урока:

1.   Получить знания о графах, их видах, свойствах.

2.   Получить навыки преобразования весовой матрицы (табличной формы представления информации) в граф.

3.   Сформировать навык построения путей в графе и поиска кратчайшего пути.

На уроке вы узнаете:

1.   Что такое граф, как наглядное средство представления и состава системы.

2.   Как применять графы при решении различных задач.

3.   Как представлять информацию на графах.

4.   Как находить кратчайший путь по графу.

Давайте рассмотрим, пожалуй, самую известную головоломку, придуманную аж в XVIII веке, и захватившую умы человечества на многие годы. Называется она задача о семи Кёнигсбергских мостах. В Кёнигсберге начиная с XIV было построено 7 мостов: Медовый мост, Лавочный мост, Зелёный мост, Рабочий мост, Кузнечный мост, Деревянный мост и Высокий мост, соединяющий остров и полуострова в единый город. Тогда и возникла головоломка: «Как пройти по всем мостам, не проходя ни по одному дважды?»

Десятилетиям жители города пытались решить эту задачу как практически (гуляя по городу), так и теоретически.

И только Леонард Эйлер, введя новое понятие — ГРАФ, смог решить ее раз и навсегда.

Граф — абстрактный математический объект, представляющий собой множество вершин графа (обозначены красным цветом) и набор рёбер (обозначены синим), то есть соединений между парами вершин. При этом каждое ребро представляет собой отношение двух вершин.

Графы делятся на:

— Неориентированные и ориентированные (когда движение по ребру возможно только в одну сторону).

— Взвешенными (когда у вершины или у ребра есть вес, отличающий его от другого) и невзвешенный.

— И другие более сложные графы (мультиграф, псевдограф, изоморфный граф и другие).

Эйлер установил, что:

1. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно или не может существовать граф, который имел бы нечётное число нечётных вершин.

2. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

3. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

ВЫВОД: пройти только один раз по каждому мосту невозможно.

Графы находят широкое применение во многих сферах нашей жизни. Например, с их помощью можно планировать оптимальные транспортные маршруты, упростить решение математических задач, визуализировать решения компьютерных программ, визуализировать различную информацию (схема метро, карта звездного неба и т. д.).

Очень часто для решения задач требуется найти кратчайший путь между двумя вершинами.

Кратчайшим путем мы будем называть путь, если: эти вершины соединены минимальным числом ребер (в случае, если граф невзвешенный); сумма ребер, соединяющих эти вершины, минимальна (для взвешенного графа).

Существует огромное количество алгоритмов, находящих кратчайший путь и один из них — это алгоритм Дейсктры.

Алгоритм заключается в том, что надо пошагово перебрать все вершины графа, вычеркивая их, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.

Для примера возьмем следующий взвешенный ориентированный граф и попытаемся найти кратчайший путь от вершины A до F. Пошагово переберём все вершины графа, вычеркивая их, которые будут являются известным минимальным расстоянием от вершины «начала» до конкретной вершины.

Первым шагом: присвоим вершине А метку равную 0, потому как эта вершина — начало. Остальным вершинам присвоим метки равные бесконечности.

Вторым шагом: выберем не вычеркнутую вершину, вес которой является минимальным («источник»). Сейчас это вершина А. Вычисляем сумму веса вершины источника и веса ребра

То есть для:

B=0+2=2

C=0+5

D=0+7

F=0+10.

Если она окажется меньше веса вершины приемника, то изменим вес этой вершины.

Третьим шагом: вычеркнем вершину-«источник».

Повторим шаги 1, 2, 3 до тех пор, пока не будут вычеркнуты все вершины.

Еще один способом нахождения кратчайшего пути может служить «метод динамического программирования».

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

Составим таблицу, в которой каждая ячейка будет соответствовать определенной ячейке. Числа в ячейках будут равны минимальному числу пошлины, которое можно получить, пройдя от начала (A) до соответствующей клетки.