Графические модели. Графы

Содержание и основные понятия

← К оглавлению
Alterna · глава 23 · страница 23.3
Графические модели. Графы
Точки и линии между ними — универсальный язык для схем, карт, сетей, алгоритмов.
Граф
— набор вершин (узлов) и рёбер (связей). Графами описывают карты дорог, компьютерные сети, социальные связи, блок-схемы алгоритмов. Всё началось с задачи о кёнигсбергских мостах в 1736 году.
ФГОС
ФОП
ОГЭ №4,9
ЕГЭ №1
01
Таблица смежности
Числовое представление графа
Как записать граф числом
Таблица смежности
— двумерная таблица размером |V| × |V|. В клетке
A[i][j]
стоит:
0
— между вершинами нет ребра
1
— есть ребро (или число рёбер для мультиграфа)
Неориентированный граф
— матрица симметрична: A[i][j] = A[j][i]
Ориентированный граф
— матрица несимметрична: A[i][j] ≠ A[j][i]
Весовая матрица
— то же, но в клетке — вес ребра (число или ∞).
Пример: неориентированный граф (4 вершины)
V = {A, Б, В, Г}, E = {{A,Б}, {A,В}, {Б,Г}, {В,Г}} — четыре ребра.
A
Б
В
Г
A
Б
В
Г
Степень
A
0
1
1
0
2
Б
1
0
0
1
2
В
1
0
0
1
2
Г
0
1
1
0
2
Сумма элементов = 8 = 2 × 4 рёбер. Матрица симметрична относительно диагонали.
02
Кёнигсбергские мосты
Откуда берётся теория графов
1736 год — Леонард Эйлер
В городе Кёнигсберге (ныне Калининград) река Прегель разделяла сушу на 4 части, соединённых 7 мостами. Жители задались вопросом:
можно ли пройти по всем мостам ровно по одному разу и вернуться в начальную точку?
Эйлер абстрагировал задачу: берега стали
вершинами
, мосты —
рёбрами
. Он доказал, что такой обход невозможен — две вершины имеют нечётную степень (Б=5, Г=3), а для цикла нужны чётные у всех.
Эйлеров цикл:
все вершины — чётная степень
Эйлерова цепь:
ровно 2 вершины — нечётная степень
🌇
Задача о кёнигсбергских мостах
A
Альтштадт
Б
Кнайпхоф
В
Форштадт
Г
Ломзе
a
b
c
d
e
f
g
Таблица смежности:
A
Б
В
Г
deg
A
0
2
0
0
2
Б
2
0
2
1
5
В
0
2
0
2
4
Г
0
1
2
0
3
✗ Б (5) и Г (3) — нечётные → нет эйлерова цикла
7 мостов: a,b — Альтштадт↔Кнайпхоф; c,d — Форштадт↔Кнайпхоф; e — Кнайпхоф↔Ломзе; f,g — Форштадт↔Ломзе
Анимация идёт по мостам. Две вершины с нечётной степенью делают полный обход невозможным.
03
Основные понятия
Вершины, рёбра, степень, петля, смежность, инциденция
ФГОС
Определения
Граф G=(V, E)
— множество вершин V и множество рёбер E.
Вершина
(узел) — объект графа.
Ребро
(дуга) — связь между двумя вершинами.
Концевые вершины
— вершины, определяющие ребро.
Степень
deg(v) — количество рёбер, инцидентных вершине.
Петля
— ребро, начало и конец в одной вершине.
Смежные вершины
— концевые вершины одного ребра.
Смежные рёбра
— имеющие общую концевую вершину.
Инцидентность
— ребро e инцидентно вершинам v
i
и v
j
.
Изолированная вершина
— степень 0.
Параллельные рёбра
— с одинаковыми концевыми вершинами.
Подграф
— часть графа, сама являющаяся графом.
Лемма о рукопожатиях
Сумма степеней всех вершин равна удвоенному числу рёбер:
Σ deg(v) = 2 · E
Следствие: число вершин нечётной степени всегда
чётно
.
04
Способы задания графов
Алгебраический, геометрический, матрица смежности, матрица инцидентности
1. Алгебраический
Два множества: V = {a, b, c, d} и E = {{a,b}, {b,c}, {a,c}, {c,d}}.
a
b
d
c
2. Геометрический
Рисунок: точки — вершины, линии — рёбра.
a
b
d
c
3. Матрица смежности
A[i][j] = количество рёбер между v
i
и v
j
.
A
Б
В
Г
A
Б
В
Г
A
0
1
1
0
Б
1
0
0
1
В
1
0
0
1
Г
0
1
1
0
4. Матрица инцидентности
B[i][j] = 1 если v
i
инцидентна e
j
. Строки — вершины, столбцы — рёбра.
A
Б
В
e1
e2
05
Виды графов
Простой, полный, ноль-граф, мультиграф, дерево, лес
Простой граф
Нет петель, нет параллельных рёбер.
A
Б
Полный K
n
Каждая пара вершин смежна. Рёбер: n(n-1)/2.
A
Б
В
Г
Ноль-граф
Множество рёбер пусто. Только вершины.
A
Б
В
Мультиграф / Псевдограф
Параллельные рёбра и/или петли.
A
Б
В
паралл.
петля
Дерево
Связный граф без циклов. E = V - 1.
A
Б
В
Лес
Несвязный граф, каждая компонента — дерево.
A
Б
В
Г
Д
Е
нет связи
06
Маршруты и пути
Маршрут → Цепь → Путь → Цикл
Иерархия маршрутов
Маршрут
— чередующаяся последовательность вершин и рёбер. Могут повторяться.
Цепь
— маршрут, где
все рёбра различны
.
Путь
— цепь, где
все вершины различны
.
Цикл
— замкнутый путь (первая вершина = последняя).
Маршрут
⊆
Цепь
⊆
Путь
|
Цикл
= замкнутый путь
🗺
Маршруты на графе: интерактив
v1
v2
v3
v4
Свойства путей и циклов
Степень неконцевой вершины пути = 2, концевых = 1.
Каждая вершина цикла имеет чётную степень.
Число вершин пути = число рёбер + 1; в цикле числа равны.
07
Связность графов
Компоненты связности
Связный граф
— между каждой парой вершин существует путь.
Компонента связности
— максимальный связный подграф.
Пример: 3 компоненты
v1
v2
v3
компонента 1
v4
v5
v6
компонента 2
v7
компонента 3
08
Степень вершины. Регулярные графы
Максимальная, минимальная, регулярные графы
Степень
deg(v) — число инцидентных рёбер.
Δ(G)
— максимальная,
δ(G)
— минимальная степень.
Регулярный граф
степени r — все вершины имеют одинаковую степень.
Σ deg(v) = 2E
| Число нечётных степеней — чётно
09
Эйлеровы и гамильтоновы циклы
Обход по рёбрам vs обход по вершинам
Эйлеров цикл
Замкнутый маршрут, проходящий
каждое ребро ровно 1 раз
.
Критерий:
все вершины имеют чётную степень
Эйл. цепь:
ровно 2 вершины нечётной степени
Алгоритм Флери:
проходить по ребру, не отрезая компоненту.
Задачи:
доставка почты, инспектирование сетей, тестирование памяти
1
2
3
4
5
6
Гамильтонов цикл
Цикл, проходящий
каждую вершину ровно 1 раз
.
Задача коммивояжёра:
найти гамильтонов цикл
минимального веса
История:
Гамильтон — задача обхода 20 вершин додекаэдра.
Применения:
планирование, расписание, тестирование ОЗУ
1
2
3
4
5
Сравнение
Эйлеров
Гамильтонов
Обходит
каждое ребро
каждую вершину
Критерий
известен (чётные степени)
не известен
Алгоритм
Флери — полиномиальный
перебор — экспоненциальный
Сложность
O(E)
NP-полная
10
Матрица смежности: интерактив
Строй граф и матрицу смежности в реальном времени
ФГОС
ОГЭ №4
ЕГЭ №1
🔗
Построитель матрицы смежности
Тип графа:
Вершин:
Нажми на две вершины подряд, чтобы переключить ребро.
Рёбер:
0
11
Мини-тест: 5 вопросов
XP: 0