🔀 Дискретка

Граф

англ. Graph

Множество вершин, соединённых рёбрами: универсальная модель сетей — от дружб в соцсети до маршрутов и зависимостей задач.

Граф $G = (V, E)$ — это вершины и рёбра между ними. Карта метро — граф (станции и линии), интернет — граф (серверы и связи), расписание — граф (задачи и зависимости).

Ориентированный — рёбра со стрелками (подписки в соцсети); неориентированный — дружба взаимна
Взвешенный — у рёбер есть числа (длина дороги, стоимость)
Связный — из любой вершины можно дойти до любой
Дерево — связный граф без циклов: $n$ вершин, ровно $n - 1$ ребро

Частые вопросы

Что такое степень вершины?

Число рёбер при ней. Сумма степеней всех вершин равна удвоенному числу рёбер (каждое ребро считаем дважды) — первая теорема теории графов, доказанная Эйлером в 1736 году.