Граф — это комбинаторный объект, состоящий из вершин и связей между ними.
Он используется для моделирования различных систем: дорог, сетей, зависимостей, функций.

Обозначается:

где

• $V$ — множество вершин (узлов),
• $E$ — множество рёбер (или дуг), соединяющих вершины.

Если рёбра имеют направление — это дуги, и граф называется ориентированным.

Виды графов

Основные понятия

• Вершина (vertex) — объект, точка графа.
• Ребро (edge) — связь между двумя вершинами.
• Дуга (arc) — ориентированное ребро.
• Инцидентность — ребро инцидентно вершине, если оно в неё входит или из неё выходит.
• Степень вершины — количество рёбер, связанных(инцидентных) с вершиной.
  • В ориентированном графе:
    • входящая степень — $deg^-(v)$ число дуг, входящих в вершину,
    • исходящая степень — $deg^+(v)$ число дуг, выходящих из вершины.
• Смежность — вершины смежны, если соединены ребром.
• Путь (path) — последовательность вершин, соединённых рёбрами.
• Цикл (cycle) — путь, который начинается и заканчивается в одной вершине.
• Компонента связности — часть графа, в которой все вершины соединены между собой.

Граф как комбинаторный объект

Графы — часть комбинаторики, потому что они изучают возможные соединения элементов множества.
Вершины — это элементы, рёбра — это пары элементов.
Комбинаторика помогает считать:

• сколько рёбер может быть в полном графе,

• сколько путей, циклов, маршрутов существует,

• как построить минимальный остов и т.д.

Например, полный граф на $n$ вершинах имеет:

n(n−1)2\frac{n(n-1)}{2}2n(n−1)​

рёбер (в неориентированном случае).

Математическое представление графа

1. Списки смежности

Для каждой вершины перечисляются вершины, в которые можно перейти.

Пример:

$A: B, C$ $B: A, D$ $C: A, D$ $D: B, C$

Пояснение:

• Такой способ хранения графа экономит память.
• Для каждой вершины известен список её соседей.
• Удобно перебирать все рёбра, но сложнее проверять наличие конкретного ребра между двумя вершинами.

2. Матрица смежности

Если есть $n$ вершин, составляется матрица $A_{ij}$:

Пример для графа $A–B–C$:

Пояснение:

• Строки и столбцы соответствуют вершинам графа.
• Если граф ориентированный, то матрица не обязательно симметрична.
• Если граф неориентированный, то $A_{ij} = A_{ji}$.
• Взвешенные графы можно представить аналогично, только вместо $1$ записывается вес ребра.

3. Матрица инцидентности

Для графа $G = (V, E)$ с вершинами $V = {v_1, v_2, \dots, v_n}$
и рёбрами $E = {e_1, e_2, \dots, e_m}$ строится матрица $B = [b_{ij}]$, где:

Для ориентированного графа:

Пояснение:

• Используется, чтобы описывать структуру графа через связь “вершина–ребро”.
• Удобна в задачах на потоки, баланс, электрические цепи и алгоритмы поиска путей.

Функциональный граф

Функциональный граф — это ориентированный граф, в котором из каждой вершины выходит ровно одна дуга.

Каждая дуга показывает функциональный переход: из вершины $x$ переходим в вершину $f(x)$.

Такой граф описывает функцию:

Пример:

Тогда граф:

graph LR
1 --"f(x)"--> 2
2 --"f(x)"--> 3
3 --"f(x)"--> 1

Этот граф образует цикл длины 3, то есть функция возвращается в исходную точку.

Если же из вершины может выходить несколько дуг, то это уже не функция, а ориентированное отношение $R \subseteq V \times V$.

Ключевые идеи теории графов

1. Граф — это способ описать связи.
   Узлы — объекты, рёбра — взаимодействия.

2. Алгоритмы на графах:
   • DFS (поиск в глубину) — обходит граф по ветвям.
   • BFS (поиск в ширину) — обходит по уровням.
   • Дейкстра — находит кратчайший путь во взвешенном графе.
   • Краскал, Прим — находят минимальное остовное дерево.
3. Функциональные графы применяются в:
   • моделях состояний и переходов,
   • автоматах,
   • анализе игр и алгоритмов.

Примеры графов

1. Неориентированный граф

graph LR
A --- B
B --- C
C --- D
D --- A

Содержит цикл $A–B–C–D–A$.

2. Ориентированный граф

graph LR
A --> B
B --> C
C --> D
D --> A

Дуги задают направления переходов.

3. Взвешенный граф

graph LR
A <--"3"--> B
B <--"2"--> C
C <--"5"--> D
D <--"4"--> A

Цифры — веса рёбер (например, длина пути).

4. Дерево`

graph LR
A --> B
A --> C
B --> D
B --> E

Связный, без циклов. Из корня $A$ можно попасть в любую вершину.

5. Функциональный граф

graph LR
1 --"f(x)"--> 2
2 --"f(x)"--> 3
3 --"f(x)"--> 1

Из каждой вершины выходит ровно одна дуга. Каждая дуга — это функциональный переход: $f(x) = y$.

Основные формулы и соотношения

Количество рёбер в полном неориентированном графе

Графы — часть комбинаторики, потому что они изучают возможные соединения элементов множества.
Вершины — это элементы, рёбра — это пары элементов.
Комбинаторика помогает считать:

• сколько рёбер может быть в полном графе,
• сколько путей, циклов, маршрутов существует,
• как построить минимальный остов и т.д.

Например, полный граф на $n$ вершинах имеет:

$m$ рёбер (в неориентированном случае).

Сумма степеней вершин $ \sum_{i=1}^{n} \deg(v_i) = 2m $

Кратчайший путь (идея алгоритма Дейкстры) $ d[v] = \min(d[v],\ d[u] + w(u,v)) $

Где применяются графы

• Сети и маршруты (дороги, интернет, электричество)
• Зависимости между задачами (планирование, алгоритмы)
• Функциональные переходы (автоматы, программы, игры)
• Анализ социальных сетей (друзья, связи, влияние)
• Биология и химия (цепочки, молекулы, родословные)

Дополнительные термины

|Термин|Смысл| |—|—| |Связный граф|Между любыми двумя вершинами есть путь| |Дерево|Связный граф без циклов| |Остовное дерево|Подграф, соединяющий все вершины без циклов| |Полный граф|Каждая вершина соединена со всеми другими| |Планарный граф|Можно нарисовать без пересечения рёбер| |Подграф|Граф, составленный из подмножества вершин и рёбер исходного графа| |Изоморфные графы|Совпадают по структуре связей (могут различаться по именам вершин)|

Ключевые идеи

1. Граф — это способ представить связи между объектами.
2. Ориентация задаёт направление связи.
3. Функциональный граф описывает однозначное соответствие $x \to f(x)$ (функцию).
4. Через матрицы смежности и инцидентности удобно описывать граф в виде чисел.
5. Основные задачи: поиск путей, циклов, степеней, связности, компонент, остовов.