При использовании данной презентации при объяснении новой темы появляется возможность применять методы личностно-ориентированного обучения: проблемный метод, метод эвристической беседы и элементы исследования. Постановка проблемы ставит учащихся в условия, которые побуждают его решать учебную проблему, проводить анализ материала и оперировать им. Такая деятельность позволяет учащимся получить новую информацию, освоит новые способы применения знаний
Из истории теории графов
Термин «граф» впервые ввел в 1936
г. венгерский математик Д. Кениг,
хотя задачи по теории графов решал
еще Л.Эйлер в XVIII веке.
Кенигсбергские мосты
К XVIII веку через реку, на которой
стоял город Кенигсберг (ныне
Калининград), было построено 7
мостов, которые связывали с берегами
и друг с другом два острова,
расположенные в пределах города.
Задача: нужно пройти (если это
возможно) по всем семи мостам так,
чтобы на каждом из них побывать
лишь по одному разу и вернуться к тому
месту, откуда начал маршрут.
Граф G(V, E)
–множество вершин V и
набор E неупорядоченных и
упорядоченных пар вершин.
Ребро – это
неупорядоченная
пара вершин.
Неориентированный
граф
Дуга – это
упорядоченная
пара вершин.
Ориентированный
(орграф)
Вершины, соединенные
ребром или дугой,
называются
смежными.
Ребра, имеющие общую
вершину, тоже
называются
смежными.
Представление графа в
памяти ЭВМ
Матрица смежности
Перечень списков
смежных вершин
Матрица смежности
– это двумерный массив А
размерностью N N,
где N – количество вершин графа.
1, если вершины i, j смежные
A[i,j]=
0, если вершины i, j несмежные
Перечень списков
смежных вершин
– это N списков, каждый из
которых содержит номера
всех смежных вершин.
Указатели на первые
элементы списков объединены
в массив.
Пример
1
2
4
1
2
3
4
5
3
1
0
1
0
0
1
1
2
3
4
5
2
1
0
1
1
0
3
0
1
0
0
1
4
0
1
0
0
0
5
1
0
1
0
0
5
Списки смежных вершин
Матрица смежности
4 nil
2
1
2
2 nil
1
5 nil
3
5 nil
3 nil
Поиск в глубину
2
3
(2)
1
(1)
Начиная с первой вершины идем
«вглубь», пока это возможно.
(4)
Выбирается вершина, смежная с
5
предыдущей, и процесс повторяется.
Если на очередном шаге оказалось,
что нет непросмотренных вершин,
связанных с текущей, то
(3)
выполняется возврат к предыдущей
и ищется новая вершина, связанная с
ней, и так до тех пор, пока не
вернемся к начальной вершине.
(5)
4
Очередность просмотра
вершин
Поиск в ширину
1
(1)
Начиная с начальной вершины
проверяются все вершины,
(3)
смежные с данной. Их номера
5
заносятся в очередь.
Далее процесс продолжается
с первой из вершин, записанной в
очереди. И до тех пор, пока
очередь не окажется пустой.
(4)
(2)
3
2
(5)
4
Очередность просмотра
вершин
Задание
1
3
6
1
2
3
4
5
6
5
2
4
1
2
3
4
5
6
2
1
1
2
3
1
2
3
4
5
1
1
1
6
0 1 1 0 0 1
1 0 0 1 0 0
1 1 0
1 0 0
0
1
0
0
1 0 1
0 0 1
0 1 0
1 0 0
3
6 nil
4 nil
4
3
4
5 nil
5 nil
6 nil
5 nil
Очередность обхода
графа при поиске в
глубину
(1)
1
(6)
6
(2)
2
3
(4)
(3)
4
(5)
5
Очередность обхода
графа при поиске в
ширину
(1)
1
(4)
6
(2)
2
3
(3)
(5)
4
(6)
5
Дерево
циклов.
Корень
– это связный граф без
Узлы
Листь
вершины пройти по
я
нескольким различным
(В нем нельзя из некоторой
ребрам и вернуться в ту же
?
вершину)
?
Взвешенный граф
– это такой граф,
1
10
4
50
ребрам или дугам которого
Матрица смежности
5
поставлены в
30
2
соответствие числовые
20
величины (вес ребер).
3
25
2
50
0
30
20
0
4
3
0
0
30 20
0
0
0
0
25
0
5
10
0
25
0
0
1
2
3
4
5
1
0
50
0
0
10
Остовное связное дерево
– это подграф, включающий
все вершины исходного
графа, каждая вершина
которого достижима из
любой другой и не
содержащий циклов.
Преобразование графа в остовное
связное дерево с помощью
цикломатического числа ,
показывающего, сколько ребер
графа нужно удалить, чтобы в
нем не осталось ни одного цикла.
= m – n +1 , где
m – количество ребер,
n – количество вершин
50
2
20
4
1
10
= 5 – 5 + 1= 1
= ?
30
3
25
4
2
1
3
5
5
2
1
3
5
2
4
1
2
1
3
3
5
5
4
4
Построение остовного связного
дерева минимального веса
(алгоритм Крускала)
1
1. Из графа удаляются все ребра и
получается остовной подграф,
где все вершины изолированы.
2
5
3
4
2. Ребра последовательно по возрастанию их весов
включаются в остовное дерево.
3. Алгоритм заканчивается, когда все вершины
будут объединены в одно связное множество,
оставшиеся ребра не включаются в остовное
дерево.
1
10
5
2
30
3
20
4
25
Примеры неориентированных графов
Граф
Семья
Город
Сеть
Домино
Дом
Лабиринт
Метро
Листок в
клеточку
Вершины
Ребра
Люди
Родственные связи
Перекрестки
Улицы
Компьютеры Кабели
Костяшки
Квартиры
Развилки и
тупики
Станции
Клеточки
Возможность
Соседство
Переходы
Пересадки
Наличие общей
границы
Примеры ориентированных графов
Орграф Вершины Дуги
Чайнворд
Слова
Стройка
Работы
Обучение
Курсы
Одевание
ребенка
Предметы
гардероба
Совпадение последней и первой букв
(возможность связать два слова в цепочку)
Необходимое предшествование (например,
стены нужно построить раньше, чем
крышу, т. п.)
Необходимое предшествование (например,
курс по языку Pascal полезно изучить
прежде, чем курс по Delphi, и т.п.)
Необходимое предшествование (например,
носки должны быть надеты раньше, чем
ботинки, и т.п.)
Перекрестки Узкие улицы с односторонним движением
Европейский
город
Организация Сотрудники Иерархия (начальник подчиненный)
Примеры взвешенных графов
Вершины Вес
Ребра (дуги) Вес ребра
Гра
ф
Тамо
жни
Переез
ды
Супер
чайнво
рд
Государства
вершины
Площадь
территории
Города
Слова
Стоимость
ночевки в
гостинице
Наличие
наземной
границы
Дороги
Совпадение конца
и начала
слов(возможнос
ть "сцепить"
слова)
(дуги)
Стоимость
получения
визы
Длина дороги
Длина
пересекающи
хся частей
Стоимость
кабеля
Карта Государства
Цвет на карте Наличие общей
Сеть
Компьютеры
границы
Сетевой кабель
Примеры деревьев
Вершины Ребра (дуги)
Солдаты
и офицеры
Иерархия
(командир
подчиненный)
Отношение
"отец сын"
Дерево
Армия
Монархи
Династия
(родословная
по мужской
линии)
grafi.ppt
