Слайд 2
Содержание:
Графы: определения и примеры
Ориентированные графы
Путь в орграфе
Матрица смежности
Иерархический
список
Алгоритм Дейкстры
Программа “ProGraph”
Описание работы программы
Достоинства программы
Список литературы
Слайд 3
Графы: определения и примеры
Говоря простым языком, граф -
это множество точек (для удобства изображения - на плоскости)
и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит.
Слайд 4
Рис. 1. Три способа изображения одного графа
Например,
три графа на рис. 1 совпадают
Слайд 5
А два графа на рис. 2 - различны
Рис. 2. Пример двух разных графов
Слайд 6
Степень вершины
Любому ребру соответствует ровно две вершины, а
вот вершине может соответствовать произвольное количество ребер, это количество
и определяет степень вершины. Изолированная вершина вообще не имеет ребер (ее степень равна 0).
Слайд 7
Смежные вершины и рёбра
Две вершины называются смежными, если
они являются разными концами одного ребра.
Два ребра называются
смежными, если они выходят из одной вершины.
Слайд 8
Путь в графе
Путь в графе - это последовательность
вершин (без повторений), в которой любые две соседние вершины
смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и abc.
Слайд 9
Достижимость
Вершина v достижима из вершины u, если
существует путь, начинающийся в u и заканчивающийся в v.
Граф
называется связным, если все его вершины взаимно достижимы.
Слайд 10
Длина пути
Длина пути - количество ребер, из которых
этот путь состоит. Например, длина уже упомянутых путей adbc
и abc - 3 и 2 соответственно.
Расстояние между между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. равно 2.
Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис.
Слайд 11
Примеры неориентированных графов
Слайд 12
Ориентированные графы
Орграф - это граф, все ребра которого
имеют направление. Такие направленные ребра называются дугами. На рисунках
дуги изображаются стрелочками ( рис.3)
Рис. 3. Орграф
Слайд 13
Смешанный граф
В отличие от ребер, дуги соединяют две
неравноправные вершины: одна из них называется началом дуги (дуга
из нее исходит), вторая - концом дуги (дуга в нее входит). Можно сказать, что любое ребро - это пара дуг, направленных навстречу друг другу.
Если в графе присутствуют и ребра, и дуги, то его называют смешанным
Слайд 14
Путь в орграфе
Путь в орграфе - это последовательность
вершин (без повторений), в которой любые две соседние вершины
смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рис. 3 нет пути, ведущего из вершины 2 в вершину 5. "Двигаться" по орграфу можно только в направлениях, заданных стрелками.
Рис. 3. Орграф
Слайд 16
Взвешенные графы
Взвешенный (другое название: размеченный) граф (или орграф)
- это граф (орграф), некоторым элементам которого (вершинам, ребрам
или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.
Рис. 4 Взвешенный граф
Слайд 17
Длина пути во взвешенном графе
Длина пути во взвешенном
(связном) графе - это сумма длин (весов) тех ребер,
из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 4, равно 6.
Рис. 4 Взвешенный граф
Слайд 19
Способы представления графов
Существует довольно большое число разнообразных способов
представления графов. Однако мы изложим здесь только самые полезные
с точки зрения программирования.
Слайд 20
Матрица смежности
Матрица смежности Sm - это квадратная матрица
размером N x N (N - количество вершин в
графе), заполненная по следующему правилу:
Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = Ves(e), в противном случае Sm[u,v] = “-”.
Слайд 21
Пример матрицы смежности
Рис. 4 Взвешенный граф
Слайд 22
Преимущества матрицы смежности
Удобство матрицы смежности состоит в наглядности
и прозрачности алгоритмов, основанных на ее использовании. А неудобство
- в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.
Слайд 23
Иерархический список
В одном линейном списке содержатся номера
"начальных вершин", а в остальных - номера смежных вершин
или указатели на эти вершины. В качестве примера приведем иерархический список, задающий орграф, изображенный на рис.3
Слайд 24
Пример иерархического списка
Рис. 5 Пример иерархического списка
Рис.
3 Орграф
Слайд 25
Преимущества иерархического списка
Вершина = запись
Номер: Число;
Имя: Строка;
След Вершина: указатель на Вершина;
Список Дуг: Дуга;
end;
Дуга = запись
Стоимость: Число;
Конец Дуги: Вершина;
След Дуга: Дуга;
end;
Очевидное преимущество такого способа представления графов заключается в экономичном использовании памяти. И даже небольшая избыточность данных, к которой приходится прибегать в случае неориентированного графа, задавая каждое ребро как две дуги, искупается гибкостью всей структуры, что особенно удобно при необходимости частых перестроений в процессе работы программы.
Слайд 26
Программа “ProGraph”
Программа “ProGraph” была специально созданна для создания
графов в графической оболочке. Поддерживает возможность добавления алгоритмов на
графах.
Слайд 27
Алгоритм Дейкстры
Мы рассмотрим один из основных алгоритмов поиска
кратчайших путей в графе – алгоритм Дейкстры, применимый для
графов с неотрицательными весами.
Слайд 28
Описание алгоритма
Основная идея основана на простой формуле:
(Dist(x) – расстояние до вершины x из исходной)
Dist(Xi)
= Минимум(Dist(Xi), Dist(p) +Matr(p,i))
Слайд 29
Описание алгоритма
Допустим, нам
надо найти кратчайший путь из вершины A в вершину
D.
Перебираем все возможные расстояния до вершин, находим из них минимальное и выводим кратчайший путь.
Слайд 30
Описание работы программы
Работа делится на две части:
Создание графа
в Редакторе.
Применение алгоритма Дейкстры к получившемуся
графу и просмотр результата.
Слайд 31
Создание графа в Редакторе
Запустите программу “ProGraph.exe”
Вы увидите
это окно.
В данном окне вы должны
ввести параметры:
Количество вершин
графа
(‘AddNode’)
Ребра и их вес
(‘AddNode’, ‘Matrix’ – веса ребер)
Имена вершин
(ПКМ на вершине, поле ‘NodeName’)
Здесь вы можете дополнительно
выбрать графическое изображение
вершин.
Слайд 32
Создание графа в Редакторе
У вас должно получиться примерно
так:
Мы видим пример сети,
оформленной в виде графа.
Расстояние между
вершинами
показаны на линиях.
В оформлении вершин
используется пиктограмма
компьютера.
Для сохранения полученного
графа выбираем из меню
File -> Save as и сохраняем
под любым именем.
Полученную заготовку будем
использовать для второй части.
Слайд 33
Применение алгоритма Дейкстры
Для вызова программы загружаем (File ->
Load) ранее сохранённый файл.
Открываем из главного меню ‘ALGOR ->
algor_Dijkst’.
Появится новое окно, в котором необходимо задать начальный и конечный
номер вершины.
(Чтобы переключить показ
‘Имена вершин/Индексы’ необходимо
поставить флажок в поле ‘ShowNodInd’)
Заполнить поля ‘From’ и ‘To’
и запустить алгоритм на выполнение
(‘OK’)
Слайд 34
Просмотр результата
Вы увидите результат работы:
В окне задания параметров
появится
строка с длиной кратчайшего пути и
сам путь.
В окне редактора
отобразится
пройденный путь и вершины окрасятся в
следующие цвета:
Красный – начальная вершина.
Синий – конечная вершина.
Желтый – вершины искомого пути.
Серый – вершины, посещенные при
работе алгоритма, но не включённые в
конечный путь.
Слайд 35
Достоинства программы
С помощью этой программы вы можете создать
любой граф с помощью
удобного редактора графов: схема метро,
карта городов,
компьютерные сети, карту лабиринта и многое другое.
Представить его в графическом виде, добавляя названия вершин,
пиктограммы, расстояния.
Определить кратчайший путь между двумя заданными вершинами и
увидеть результат работы алгоритма в графическом и текстовом виде.
Программа была создана на языке “Delphi” с использованием
объектно-ориентированного программирования.
Данная программа может быть использована для подготовки к ЕГЭ
по информатике.