Графы

1. Графы. Решение алгоритмических задач, связанных с анализом графов

Информатика
Графы. Решение
алгоритмических задач,
связанных с анализом графов
11 класс

2.

МК
Ключевые слова
▪
▪
▪
▪
▪
▪
▪
▪
Граф
Неориентированный граф
Дерево
Лес
Ориентированное (направленное) дерево
Двоичное (бинарное) дерево
Списки
Линейный односвязный список

3.

МК
!
!
Граф - это множество точек или вершин и множество линий или
ребер, соединяющих между собой все или часть этих точек. Граф
является информационной моделью некоторого объекта или
системы объектов.
Неориентированный граф - это граф , в котором нет направления
линий. Направленные ациклические графы широко используются в
приложениях: в компиляторах, в искусственном интеллекте, в
статистике и машинном обучении.
Дерево — это связный ациклический
граф.
Связность означает наличие
путей между любой парой вершин,
ацикличность — отсутствие циклов и
то, что между парами вершин имеется
только по одному пути.
Лес — упорядоченное множество
упорядоченных деревьев.

4.

МК
!
Ориентированное (направленное) дерево — ацикличный орграф
(ориентированный граф, не содержащий циклов), в котором
только одна вершина имеет нулевую степень захода (в неё не
ведут дуги), а все остальные вершины имеют степень захода 1 (в
них ведёт ровно по одной дуге). Вершина с нулевой степенью
захода называется корнем дерева, вершины с нулевой степенью
исхода (из которых не исходит ни одна дуга) называются
концевыми вершинами или листьями.
Двоичное (бинарное) дерево —
иерархическая структура данных,
в которой каждый узел имеет не
более двух потомков (детей). Как
правило, первый называется
родительским узлом, а дети
называются левым и правым
наследниками.

5. Пример задачи с использованием графа для определения различных путей и определения кратчайшего пути на графе.

МК
Пример задачи с использованием графа для
определения различных путей и определения
кратчайшего пути на графе.
Решение:
Как
преобразовать
информацию,
представленную в табличной форме в граф? Как
определить все пути в графе? Определить кратчайший
путь?
Проанализируем таблицу.
Такую таблицу называют весовой матрицей. Части таблицы, разделённые
диагональю – симметричны, т.е. содержат одни и те же данные.
Следовательно, можно рассматривать данные любой половины таблицы,
разделенной диагональю. Теперь приступим к построению взвешенного
графа по этой таблице.
Определим все пути в графе и расстояние, пройденное на этом пути (вес в
данном случае - расстояние в км.)

6.

МК
Существует еще один метод задания графа: таблица
инцидентности
Для заполнения этой таблицы необходимо
пронумеровать ребра графа:
Правило заполнения:
1 – вершина с ребром соединена
0 – вершина с ребром не соединяется
Названия строк таблицы инцидентности – названия вершин графа,
названия столбцов – номера ребер графа. Эта таблица не является
симметричной и не имеет главной диагонали.
Примером применения неориентированного графа
служит дорожная сеть.
Схема дорожной сети не является картой местности, здесь не
соблюдается масштаб, схема не ориентирована по сторонам света.
Вершинами графа дорожной сети являются названия населенных
пунктов, а ребрами –дороги между ними. Чем сеть гуще, тем больше
вариантов проезда между населенными пунктами.

7. Рассмотрим пример:

МК
Рассмотрим пример:
Район состоит из пяти поселков: Марьино, Прокшино,
Софьино, Булатово и Лукино. Автомобильные дороги
проложены между: Марьино и Прокшино, Марьино и
Булатово, Прокшино и Лукино, Прокшино и Булатово,
от Булатово до Софьино.
Пример схемы по этому описанию:
Поселки обозначены первыми буквами названий:
М – Марьино, П – Прокшино, С – Софьино, Б –
Булатово, Л - Лукино
Глядя на этот граф, можно ответить на вопрос – через
какие поселки нужно проехать, чтобы добраться из
Софьино в Лукино?
Возможно два пути:
1 вариант С – Б – П – Л (Софьино-Булатово-ПрокшиноЛукино)
2 вариант С – Б – М – П – Л (Софьино-БулатовоМарьино-Прокшино-Лукино)

8.

МК

9.

МК

10.

МК

11.

МК

12. Домашнее задание. Задача 1.

МК
Домашнее задание. Задача 1.

13. Домашнее задание. Задача 2

МК
Домашнее задание. Задача 2