Теория графов — информатика, 11 класс

1.

Информатика · 11 класс
Теория графов
Вершины, рёбра, пути и алгоритмы — на
простых примерах

2.

Что такое граф?
Граф — набор вершин и рёбер, которые их
соединяют.
Вершина
объект: город, человек, компьютер
Ребро
связь: дорога, дружба, кабель

3.

Виды графов
Неориентированный
Ориентированный
Взвешенный
A—B
A→B
A —5— B
Связь работает в обе стороны.
У ребра есть направление
(стрелка).
У ребра есть число — вес.
Пример: дружба в соцсети
Пример: подписки, улица с
односторонним движением
Пример: расстояние в км, время
в пути, цена билета

4.

Степень, путь, цикл
Примеры — на графе A–E со слайда 2
Понятие
Что это
Пример
Степень вершины
число рёбер, выходящих из вершины
степень D = 4
Путь
последовательность рёбер от одной
вершины к другой
A→B→D→E
Цикл
путь, который возвращается в начало
A→B→D→A
Связный граф
из любой вершины можно дойти до
любой
наш граф связный
Правило: сумма степеней = 2 × число рёбер. 3+2+2+4+1 = 12 = 2·6

5.

Как хранить граф в памяти
Матрица смежности
A
Список смежности
A
B
C
D
E
0
1
1
1
0
B
1
0
0
1
0
C
1
0
0
1
0
A: B, C, D
B: A, D
C: A, D
D: A, B, C, E
E: D
Для каждой вершины — список соседей. Экономит память, если рёбер мало.
D
1
1
1
0
1
E
0
0
0
1
0
1 — ребро есть, 0 — ребра нет

6.

Кратчайший путь: поиск в ширину
Задача: найти самый короткий путь от C до E. Идём «волнами» — сначала все соседи, потом соседи
соседей.
Шаг 0
Шаг 1
Шаг 2
C
A, D
B, E
стартовая вершина
соседи C
соседи A и D — нашли E!
Ответ: C → D → E — 2 ребра
Для взвешенных графов (километры, минуты) используют алгоритм Дейкстры.

7.

Где применяют графы и задача
Применение
Задача
• Навигатор: перекрёстки — вершины, дороги —
В классе 6 учеников. У каждого ровно 3 друга.
Сколько всего дружб (рёбер)?
рёбра
• Соцсети: люди и дружба
• Интернет: маршрутизация пакетов
• Расписания и турниры
Подсказка: сумма степеней = 2 × число рёбер.