Графы: основы

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

← Вернуться к оглавлению
Alterna · глава 17 · страница 17.2
Графы: основы
Вершины, рёбра, степени. Матрица смежности и список смежности. Canvas-редактор.
Граф
— пара (V, E), где V — множество вершин, E — множество рёбер между ними. Простая модель, описывающая связи: соцсети, карты, схемы зависимостей.
ФГОС
ФОП
ОГЭ №4,9
ЕГЭ №1
01
Определения
Базовые понятия
Вершина (V)
— узел графа, объект.
Ребро (E)
— связь между двумя вершинами.
Степень вершины deg(v)
— число инцидентных ей рёбер.
Петля
— ребро из вершины в себя (обычно не рассматривается в простых графах).
Кратные рёбра
— несколько рёбер между одной парой вершин (мультиграф).
Путь
— последовательность вершин, где каждая соседняя пара соединена ребром.
Цикл
— путь, начинающийся и заканчивающийся в одной вершине.
Связный граф
— из любой вершины можно дойти до любой другой.
Лемма о рукопожатиях
Сумма степеней всех вершин графа равна удвоенному числу рёбер:
Σ deg(v) = 2|E|
. Это потому, что каждое ребро вносит 1 в степень каждой из двух своих вершин.
02
Типы графов
↔
Неориентированный
рёбра без стрелок
Связь двусторонняя. Дружба в соцсети, дороги.
→
Ориентированный (орграф)
рёбра-дуги
Связь односторонняя. Подписки, односторонние дороги.
⚖️
Взвешенный
рёбра с весом
Каждому ребру — число (длина, стоимость, время).
🌳
Дерево
связный без циклов
V вершин, V−1 рёбер, между любыми двумя вершинами ровно один путь.
⭐
Полный (K_n)
все возможные рёбра
Каждая пара вершин соединена. K_n: n(n−1)/2 рёбер.
🔗
Двудольный
2 группы вершин
Рёбра только между группами. Соцсеть (авторы ↔ посты).
03
Матрица смежности и список смежности
Матрица смежности A (N×N)
A[i][j] = 1
, если есть ребро i→j, иначе
0
. Для неориентированного A симметрична.
Занимает O(N²) памяти. Быстро проверять наличие ребра O(1).
Пример: граф с 4 вершинами и 4 рёбрами
Рёбра: (A,B), (A,C), (B,D), (C,D)
A
B
C
D
A
0
1
1
0
B
1
0
0
1
C
1
0
0
1
D
0
1
1
0
Список смежности (Adjacency List)
Для каждой вершины — список её соседей. Память O(V+E). Быстрее обходить граф (O(V+E) против O(V²) у матрицы).
Используется в реальных программах.
A
: [B, C]
B
: [A, D]
C
: [A, D]
D
: [B, C]
04
Canvas-редактор графа
Кликни по холсту — добавь вершину. Зажми на вершине и потяни к другой — создай ребро.
✏️
Создай свой граф
Кликни по холсту, чтобы добавить вершину.
05
Мини-тест
📝
6 вопросов по графам