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

1.

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

2.

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

3.

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

4.

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

5.

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

6.

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

7.

МК
Самостоятельная работа
1. На рисунке схема дорог Н-ского района изображена в виде графа, в
таблице содержатся сведения о протяжённости каждой из этих дорог (в
километрах).
Так как таблицу и схему рисовали
независимо друг от друга, то
нумерация населённых пунктов в
таблице никак не связана с
буквенными обозначениями на
графе. Определите сумму длин дорог между пунктом А и пунктом Б, и
между пунктом Е и пунктом К. В ответе запишите целое число.
2. На рисунке слева изображена схема дорог Н-ского района, в таблице
звёздочкой обозначено наличие дороги из одного населённого пункта в
другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме
соответствует его номер в таблице, но
неизвестно, какой именно номер.
Определите, какие номера населённых
пунктов в таблице могут
соответствовать населённым пунктам A и G на схеме. В ответе запишите эти
два номера в возрастающем порядке без пробелов и знаков препинания