Точки и линии между ними — универсальный язык для схем, карт, сетей, алгоритмов.
Граф — набор вершин (узлов) и рёбер (связей). Графами описывают карты дорог, компьютерные сети, социальные связи, блок-схемы алгоритмов. Всё началось с задачи о кёнигсбергских мостах в 1736 году.
Числовое представление графа
Таблица смежности — двумерная таблица размером |V| × |V|. В клетке A[i][j] стоит:
Весовая матрица — то же, но в клетке — вес ребра (число или ∞).
V = {A, Б, В, Г}, E = {{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 рёбер. Матрица симметрична относительно диагонали.
Откуда берётся теория графов
В городе Кёнигсберге (ныне Калининград) река Прегель разделяла сушу на 4 части, соединённых 7 мостами. Жители задались вопросом: можно ли пройти по всем мостам ровно по одному разу и вернуться в начальную точку?
Эйлер абстрагировал задачу: берега стали вершинами, мосты — рёбрами. Он доказал, что такой обход невозможен — две вершины имеют нечётную степень (Б=5, Г=3), а для цикла нужны чётные у всех.
| 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 — Форштадт↔Ломзе
Анимация идёт по мостам. Две вершины с нечётной степенью делают полный обход невозможным.
Вершины, рёбра, степень, петля, смежность, инциденция
Сумма степеней всех вершин равна удвоенному числу рёбер:
Следствие: число вершин нечётной степени всегда чётно.
Алгебраический, геометрический, матрица смежности, матрица инцидентности
Два множества: V = {a, b, c, d} и E = {{a,b}, {b,c}, {a,c}, {c,d}}.
Рисунок: точки — вершины, линии — рёбра.
A[i][j] = количество рёбер между vi и vj.
| A | Б | В | Г | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| Б | 1 | 0 | 0 | 1 |
| В | 1 | 0 | 0 | 1 |
| Г | 0 | 1 | 1 | 0 |
B[i][j] = 1 если vi инцидентна ej. Строки — вершины, столбцы — рёбра.
Простой, полный, ноль-граф, мультиграф, дерево, лес
Нет петель, нет параллельных рёбер.
Каждая пара вершин смежна. Рёбер: n(n-1)/2.
Множество рёбер пусто. Только вершины.
Параллельные рёбра и/или петли.
Связный граф без циклов. E = V - 1.
Несвязный граф, каждая компонента — дерево.
Маршрут → Цепь → Путь → Цикл
Компоненты связности
Связный граф — между каждой парой вершин существует путь.
Компонента связности — максимальный связный подграф.
Максимальная, минимальная, регулярные графы
Степень deg(v) — число инцидентных рёбер.
Δ(G) — максимальная, δ(G) — минимальная степень.
Регулярный граф степени r — все вершины имеют одинаковую степень.
Обход по рёбрам vs обход по вершинам
Замкнутый маршрут, проходящий каждое ребро ровно 1 раз.
Алгоритм Флери: проходить по ребру, не отрезая компоненту.
Задачи: доставка почты, инспектирование сетей, тестирование памяти
Цикл, проходящий каждую вершину ровно 1 раз.
История: Гамильтон — задача обхода 20 вершин додекаэдра.
Применения: планирование, расписание, тестирование ОЗУ
| Эйлеров | Гамильтонов | |
|---|---|---|
| Обходит | каждое ребро | каждую вершину |
| Критерий | известен (чётные степени) | не известен |
| Алгоритм | Флери — полиномиальный | перебор — экспоненциальный |
| Сложность | O(E) | NP-полная |
Строй граф и матрицу смежности в реальном времени
Нажми на две вершины подряд, чтобы переключить ребро.