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

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

← Вернуться к оглавлению
Alterna · глава 17 · страница 17.2
Графы: основы
Вершины, рёбра, степени. Матрица смежности и список смежности. Canvas-редактор.
Граф
— пара (V, E), где V — множество вершин, E — множество рёбер между ними. Простая модель, описывающая связи: соцсети, карты, схемы зависимостей.
ФГОС
ФОП
ОГЭ №4,9
ЕГЭ №1
🔗
Связь с главой 16 (Логические схемы)
Логические схемы состоят из элементов и связей между ними. Если забыть про электрические сигналы и оставить только «что с чем соединено» — получится граф! Вершины — это элементы (И, ИЛИ, НЕ), рёбра — провода между ними. Так глава 16 неявно готовила вас к понятию графа: любая схема — частный случай графа, только ориентированного и чаще всего без циклов. Графы — универсальный язык для описания любых связей: дороги между городами, друзья в соцсетях, зависимости задач в проекте.
📊
Примеры графовых моделей
А
Б
В
Г
Д
друзья в соцсети
Друзья в соцсети
Неориентированный граф
Вершины — пользователи, рёбра — дружба. Связь двусторонняя.
Москва
Тверь
Питер
Выборг
170
300
120
Карта дорог
Взвешенный неориентированный
Вершины — города, веса — расстояния. Найти кратчайший путь.
/
usr
etc
f1
f2
f3
f4
Файловая система
Дерево
Папки — вершины, файлы — листья. Иерархия вложенности.
Старт
A
B
C
Финиш
Схема зависимостей задач
Ориентированный граф (ДАГ)
Что должно быть сделано до начала следующей задачи.
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
Построение графа из матрицы
🔄
Обратный режим: матрица → граф
Введи матрицу смежности:
1
= есть ребро,
*
= вес/длина,
0
= нет ребра. Граф построится автоматически.
Ориентированный
A
B
C
D
A
B
C
D
Рёбра: A→B, A→C, B→D, C→D
06
Мини-тест
📝
Основы графов — 5 вопросов из 50
Уровень:
Новичок
0
/
50
XP
⬡
0
Вопрос 1 из 5
🔥 Серия:
0