diskrete_math/razdel3_lekc2.md

## Продолжение лекции: Связность графов. Пути и циклы. Деревья

Продолжим наше знакомство с графами. Уважаемые студенты, после того как мы научились различать графы по типу рёбер и весам, а также понимать, когда графы одинаковы с точностью до переименования вершин, необходимо перейти к изучению внутренней структуры графа – как вершины связаны между собой, какие существуют маршруты и как выделяются особые подграфы, играющие ключевую роль в информатике. Сегодня мы рассмотрим понятия пути, цикла, связности и, самое главное, **деревья** – один из самых полезных типов графов для практического программирования и построения алгоритмов.

### Пути, цепи и циклы

Представьте, что вам нужно в компьютерной сети передать пакет данных от одного узла к другому, но прямого соединения между ними нет. Тогда пакет будет проходить через промежуточные узлы – маршрутизаторы. Последовательность вершин, в которой каждые две соседние вершины соединены ребром (или дугой), называется **маршрутом** (или **путём**). Длина маршрута – это количество рёбер в нём. Если в маршруте ни одно ребро не повторяется, такой маршрут называют **цепью**. Если, кроме того, в цепи не повторяются вершины (за исключением, возможно, первой и последней), то это **простая цепь**. Когда в простой цепи первая и последняя вершины совпадают, а длина не меньше трёх, получается **цикл** (или **контур** в ориентированном случае). Цикл – это замкнутый путь, который часто встречается в реальных системах: например, циклическая зависимость в программе, когда функция A вызывает B, B вызывает C, а C вызывает A. Такой цикл может привести к бесконечной рекурсии, если не предусмотрено корректное условие выхода.

В неориентированных графах циклы бывают разной длины. Самый короткий цикл – треугольник (три вершины, соединённые попарно). Важно уметь находить циклы, потому что они сигнализируют о наличии избыточных связей, альтернативных путей или потенциальных проблем (например, петли маршрутизации в сетях). В ориентированных графах различают **ориентированный цикл**, где все дуги направлены последовательно вдоль обхода. Ориентированные графы без циклов называются **ациклическими** и играют огромную роль в организации вычислений, о чём мы поговорим чуть позже.

### Связность графов

Теперь введём ключевое понятие – **связность**. Неориентированный граф называется **связным**, если для любой пары его вершин существует хотя бы один путь, соединяющий их. Иными словами, из любой вершины можно добраться до любой другой. Если граф не является связным, он распадается на несколько **компонент связности** – максимальных связных подграфов, которые не соединены между собой рёбрами. Например, если в офисной сети произошёл обрыв кабеля и группа компьютеров оказалась изолирована от остальных, то сеть разделилась на две компоненты связности. Каждая компонента – это отдельный связный граф.

В ориентированных графах понятие связности сложнее. Различают **слабую связность** – если заменить все дуги на неориентированные рёбра, граф станет связным. **Сильная связность** означает, что для любых двух вершин u и v существует путь из u в v и одновременно путь из v в u (т.е. они взаимно достижимы). Сильно связные компоненты (SCC) – одно из важнейших понятий при анализе веб-ссылок, компиляции и параллельных вычислений. Например, в социальной сети сильно связная компонента – это группа пользователей, где каждый может отправить сообщение любому другому (возможно, через посредников) и получить ответ.

Как определить компоненты связности в неориентированном графе? Это делается простым обходом в глубину (DFS) или ширину (BFS). Вы начинаете с произвольной вершины, помечаете все достижимые из неё вершины – это первая компонента. Затем переходите к следующей непомеченной вершине и повторяете процесс. Для больших графов (например, графа дружеских связей во «ВКонтакте» с сотнями миллионов вершин) существуют эффективные алгоритмы, которые работают за линейное время O(n + m). Именно так социальные сети находят группы людей, не связанных с остальными, и предлагают «друзей по рекомендации».

### Деревья – особый вид графов

Перейдём к одному из самых важных семейств графов в информатике – **деревьям**. Дерево – это связный неориентированный граф без циклов. Другое определение: дерево – это граф, в котором между любыми двумя вершинами существует ровно один простой путь. Примеры из реальной жизни: иерархическая файловая система (папки и файлы), схема разбора арифметического выражения в компиляторе, генеалогическое древо, структура XML-документа. В каждой операционной системе папки (каталоги) вложены друг в друга, образуя дерево (если игнорировать жёсткие ссылки и символические ссылки, которые могут создавать циклы). Это позволяет эффективно выполнять поиск файлов, навигацию и управление правами доступа.

Важные свойства деревьев:
- В дереве с n вершинами ровно n-1 ребро. Это легко проверить: для одной вершины 0 рёбер, добавление каждой новой вершины требует ровно одного ребра, чтобы не образовать цикл.
- Если в дереве добавить любое ребро между двумя существующими вершинами, появится ровно один цикл.
- Если удалить любое ребро, дерево распадётся на два дерева (две компоненты связности).
- В любом дереве есть хотя бы две висячие вершины (листья) – вершины степени 1, если только дерево не состоит из одной вершины.

В ориентированном варианте дерево называют **корневым деревом** (или ориентированным деревом), где выделена одна вершина – **корень**, а все дуги направлены от корня к листьям (или наоборот). Именно такие деревья лежат в основе иерархических структур. Например, дерево каталогов: корень – это диск C:\, затем папки, в них подпапки. В алгоритмах сжатия (код Хаффмана) используется бинарное дерево, где листья имеют веса – частоты символов.

### Лес и остовные деревья

Граф, все компоненты связности которого являются деревьями, называется **лесом**. Лес – это ациклический граф (возможно, несвязный). Любой ациклический граф – это лес, и число его рёбер равно n - k, где k – количество компонент связности.

Очень важное практическое понятие – **остовное дерево** (или каркас) связного графа. Это подграф, который содержит все вершины исходного графа, является деревом (то есть связным и без циклов) и использует только некоторые рёбра исходного графа. Иными словами, мы удаляем «лишние» рёбра так, чтобы сохранить связность, но убрать все циклы. Зачем это нужно? Например, при проектировании сети связи между серверами нужно проложить минимальное количество кабелей, чтобы все серверы были соединены (возможно, не напрямую, а через другие серверы). Остовное дерево даёт ровно n-1 соединение. Если каждому ребру приписать вес (стоимость кабеля), то задача построения **минимального остовного дерева** (MST) становится оптимизационной. Классические алгоритмы – алгоритм Прима и алгоритм Краскала – изучаются во многих курсах алгоритмов и структур данных. Они широко применяются в проектировании локальных сетей (LAN), маршрутизации в многоадресных рассылках (multicast), кластеризации данных и даже в задачах компьютерного зрения.

Ещё один ИТ-пример: в базах данных для выполнения запроса с соединением таблиц (JOIN) оптимизатор строит дерево соединений – это остовное дерево графа связей между таблицами, чтобы минимизировать время выполнения запроса. Весами могут быть оценочные размеры промежуточных результатов. Без теории деревьев невозможно понять, как работают современные реляционные СУБД (например, PostgreSQL, MySQL) при выборе плана выполнения.