Часть 1: Arborescence (Общее определение)

в данной статье могу быть неточности или упрощения

1.1. Интуитивное представление: Представьте себе обычное неориентированное дерево (tree). Теперь назначьте одной из его вершин особую роль — корень (root). Затем сориентируйте все ребра так, чтобы они указывали от корня наружу, т.е. в направлении от корня к листьям. Полученная структура и есть арборесценция.

Простой пример - структура папок на компьютере ⬇️

• Корень — C:\ (или / на Linux)
• Все папки созданы через "Создать папку", нет ярлыков или ссылок.
• Каждая папка имеет ровно одного "родителя" (папка, в которой она лежит).
• Вверх можно подняться только к родителю. Это классическое дерево (арборесценция).

DAG с потенциальной Arborescence (реальная система с mklink или .lnk):

Допустим, есть структура:

C:\Projects\
├── SecretData\
└── CurrentProject\   <-- содержит ярлык "Data" → C:\Projects\SecretData

Теперь это DAG, но не арборесценция, потому что:

• SecretData имеет двух "родителей":
  1. Прямой: C:\Projects\
  2. Через ярлык: C:\Projects\CurrentProject\Data\
• Нарушается условие входящая_степень = 1 для арборесценции.
• Но циклов нет — это DAG.

"Arborescence(DAG)" в этой аналогии:

Если администратор строго запретил создавать ярлыки, ссылки и точки монтирования, то файловая система является одновременно и DAG (циклов нет), и Arborescence (деревом). Это и есть тот самый простой случай "просто дерево папок".

1.2. Формальное определение:

пояснение обозначений в конце

Пусть G = (V, E) — ориентированный граф (directed graph).

G называется арборесценцией (ориентированным деревом) с корнем r ∈ V, если выполняются следующие условия:

1. Существование корня: Существует ровно одна вершина r, в которую не входит ни одно ребро (т.е. её входящая степень deg⁻(r) = 0). Эта вершина называется корнем.
2. Единственность пути от корня: Для любой другой вершины v ∈ V \ {r} существует ровно один ориентированный путь из r в v.
3. Отсутствие циклов: Граф G не содержит ориентированных циклов.

1.3. Ключевые следствия и свойства:

Из определения вытекают важные и эквивалентные характеристики:

• Структура входящих рёбер: У каждой вершины v ≠ r входящая степень равна 1 (deg⁻(v) = 1). У корня r — 0.

1. Корень — это тоже вершина.
   В теории графов понятия «вершина» и «узел» (node) означают одно и то же. Корень — это просто особая, выделенная вершина.

2. Входящая степень корня равна нулю.
   Это значит, что в корень не ведёт ни одно ребро — нет ни одной стрелки, которая указывала бы на него. Он является началом всех путей в графе.

3. У всех остальных вершин входящая степень равна единице.
   Каждая вершина, кроме корня, имеет ровно одно входящее ребро — одну стрелку, которая приходит в неё от другой вершины.

4. Это прямое следствие определения арборесценции.
   Именно потому, что граф является арборесценцией (ориентированным деревом), в нём соблюдаются эти правила: один корень без входящих рёбер и у каждой другой вершины ровно один «родитель».

Таким образом, структура входящих рёбер в арборесценции строго определена:
0 → у корня, 1 → у всех остальных вершин.

• Связность (в ориентированном смысле): Граф является слабо связным (если игнорировать направления рёбер, он связен) и достижимым из корня (из r можно дойти до любой вершины v).
• Число рёбер: Если в арборесценции n вершин, то в ней ровно n-1 ребро.
• Ориентация от предка к потомку: Для любого ребра (u, v) вершина u является предком (ancestor) вершины v, а v — потомком (descendant) u. Корень является предком всех вершин.
• Эквивалентность дереву: Если заменить ориентированные рёбра на неориентированные, получится обычное связное ациклическое неориентированное дерево.

Часть 2: Arborescence в ориентированном ациклическом графе (DAG)

Теперь рассмотрим ситуацию, когда арборесценция является подграфом большего ориентированного ациклического графа (Directed Acyclic Graph, DAG).

2.1. Контекст и мотивация:

DAG — это ориентированный граф без циклов. Примеры: зависимость задач (makefile), порядок курсов в учебном плане, частичная упорядоченность событий. В таком графе часто возникает задача найти структуру, связывающую все или многие вершины в виде дерева.

2.2. Определение Arborescence в DAG:

Пусть дан DAG G = (V, E). Арборесценцией в DAG (часто называют ориентированным остовным деревом) называется такой подграф T = (V, E_T), где E_T ⊆ E, который сам является арборесценцией (в смысле Части 1) с некоторым корнем r ∈ V. Остовное — это ключевое слово, означающее «покрывающее все вершины».

Ключевой момент: Все рёбра арборесценции T берутся исходного DAG'а G и сохраняют свою ориентацию. Арборесценция "вписывается" в топологический порядок DAG'а.

Топологический порядок (или топологическая сортировка) — это такой способ линейного упорядочивания вершин ориентированного графа, при котором для любого ребра от вершины A к вершине B, вершина A всегда идет в списке раньше, чем B.

• Главное условие: Работает только в графах без циклов (DAG). Если можно вернуться из конца в начало, порядок построить нельзя.
• Суть: Если есть путь из A в B, то в списке A всегда будет левее B. Это «линия времени» или очередь выполнения задач.
• Достижимость vs Порядок: Если A→B, то A раньше B (всегда).Если A раньше B в списке, это не значит, что между ними есть путь (они могут быть просто независимыми параллельными задачами).
  Запомни: Топологический порядок — это список дел, где ты никогда не встретишь ситуацию, что для выполнения текущего шага нужно было сделать что-то, что идет дальше по списку. (нету никаких циклов)

2.3. Существование и построение:

В произвольном DAG арборесценция, покрывающая все вершины (т.е. остовная), существует не всегда.

Необходимые условия существования остовной арборесценции в DAG:

1. Существование единственного корня-источника: В DAG должен существовать ровно один узел с нулевой входящей степенью (источник). Этот узел станет кандидатом в корень r арборесценции. Если таких узлов несколько, построить одно остовное дерево невозможно (получатся несколько несвязных деревьев).
2. Достижимость из корня: Этот единственный источник r должен быть достижим до всех остальных вершин DAG'а. Это условие не следует автоматически из первого — в DAG могут существовать изолированные от r компоненты, даже если r является единственным источником во всём графе.

Важное замечание: Даже если оба условия выполнены, не любой выбор по одному входящему ребру для каждой вершины приведёт к связной арборесценции. Неудачный выбор может создать лес (несколько деревьев) или нарушить достижимость из корня.

Корректный алгоритм построения (обход из корня): Если условия выполнены, остовную арборесценцию можно гарантированно построить с помощью обхода (BFS/DFS), начиная с корня r, и выбора родительских рёбер.

• Инициализировать пустой подграф T.
• Выбрать единственный источник r как корень и добавить его в T.
• Запустить обход (например, BFS) из r по рёбрам исходного DAG'а G.
• Для каждой новой вершины v, достигнутой в результате обхода по ребру (u, v) ∈ E, добавить это ребро (u, v) в T как единственное входящее ребро для v в арборесценции.
• По завершении обхода проверить, что T содержит все вершины V. Если да, то T — искомая остовная арборесценция. Если некоторые вершины не были достигнуты, то, несмотря на выполнение условий, выбор рёбер в процессе обхода мог привести к тупику; в этом случае требуется более сложный алгоритм поиска охватывающего дерева (spanning arborescence).

Альтернативный подход (выбор родителя): Более простой для реализации способ, который гарантирует построение арборесценции, если она существует:

1. Выполнить топологическую сортировку DAG'а G.
2. Для каждой вершины v ≠ r (в порядке топологической сортировки) выбрать в качестве её родителя любую вершину u, для которой существует ребро (u, v) ∈ E. Благодаря топологическому порядку, u будет обработана раньше v, что гарантирует отсутствие циклов и достижимость из корня (при условии, что корень r является первой вершиной в порядке). Все выбранные рёбра (u, v) образуют искомую арборесценцию T.

Всякая арборесценция по определению является DAG (ориентированным ациклическим графом).

Часть 3: Сравнение и итоговая таблица

Пример для DAG (построение арборесценции):

Рассмотрим DAG:

     A (источник, deg⁻=0)
    / \
   B   C
    \ / \
     D   E

Здесь есть один источник A. Попробуем построить арборесценцию (остовное дерево):

• Корень: A.
• Для B: Выбираем ребро A -> B.
• Для C: Выбираем ребро A -> C.
• Для D: Есть два входящих ребра (B->D, C->D). Выбираем, например, B->D.
• Для E: Есть ребро C->E. Выбираем его.

Получили арборесценцию: A -> B, A -> C, B -> D, C -> E. Она покрывает все вершины.

Заключение

• Arborescence — это фундаментальная структура, ориентированный аналог дерева.
• Arborescence в DAG — это способ выбрать в графе зависимостей "главного предка" для каждой вершины, превратив его в иерархию.
• Утверждение, что граф является и тем, и другим, обычно подчеркивает его строгую древовидную природу и ацикличность, что упрощает анализ (например, можно применять обходы из корня и ДП на DAG одновременно).

Обозначения:

• V (от Vertices) — множество вершин графа.
  Например: V = {A, B, C, D}

• E (от Edges) — множество рёбер графа.
  Ребро — это пара вершин.
  Для неориентированного графа: E = {{A,B}, {B,C}}. Для ориентированного графа (дуги): E = {(A→B), (B→C), (C→A)} — где порядок вершин важен.

1. r ∈ V

• r — обозначает корень (root)
• ∈ — знак принадлежности ("принадлежит")
• V — множество всех вершин графа
• Полный смысл: r — это одна из вершин графа

2. deg⁻(r) = 0

• deg⁻(v) — входящая степень вершины (количество рёбер, входящих в вершину)
  • Часто обозначается как deg^{-}(v) или d_in(v).
• (r) — для вершины r
• = 0 — равна нулю
• Полный смысл: в корень не входит ни одного ребра (нет ни одной стрелки, которая указывает на эту вершину)

3. v ∈ V \ {r}

• v — произвольная вершина
• ∈ — принадлежит
• V \ {r} — множество всех вершин кроме корня r
• Полный смысл: для каждой вершины, которая не является корнем

4. Ориентированный путь из r в v

• Ориентированный путь — последовательность вершин r → ... → v, где каждое ребро направлено от предыдущей вершины к следующей
• Ровно один — существует только один такой путь, нельзя дойти разными способами

5. Ориентированный цикл

• Ориентированный цикл — путь, который начинается и заканчивается в одной вершине, следуя направлению рёбер
• Пример: A → B → C → A
• Отсутствие циклов — таких замкнутых маршрутов в графе нет

Простыми словами:

1. Есть одна особая вершина-корень r
2. В неё ничего не ведёт (как начало реки)
3. Из корня в любую другую вершину можно пройти только одним способом
4. Нельзя ходить по кругу — только от корня вниз

Решение задачи 207. Course Schedule (Leetcode)

Смысл задачи максимально простой:
Проверь, есть ли в списке зависимостей циклы.

• Если циклов нет: Ты сможешь составить план обучения и пройти все курсы → true.
• Если есть цикл: (например, для курса 0 нужен курс 1, а для курса 1 нужен курс 0), ты попадешь в "замкнутый круг" и не сможешь даже начать → false.

Визуально:
[[1,0]] — это прямая линия (0→1). Все ок. [[1,0],[0,1]] — это кольцо (0↔1). Тупик.

class Solution {
    public boolean canFinish(int num_courses, int[][] prerequisites) {
        // 1. ПОДГОТОВКА СТРУКТУРЫ ГРАФА
        // Создаем список смежности (adj), где индекс — это курс,
        // а список внутри — это те курсы, которые станут доступны после него.
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < num_courses; i++) adj.add(new ArrayList<>());

        // 2. ЗАПОЛНЕНИЕ ГРАФА И СЧЕТЧИКА "ДОЛГОВ"
        // indegree[i] — это количество курсов-пререквизитов, которые нужно сдать ДО курса i.
        int[] indegree = new int[num_courses];
        for (int[] pair : prerequisites) {
            int course = pair[0]; // Целевой курс
            int pre = pair[1];    // Курс-условие
            adj.get(pre).add(course); // Проводим стрелку: pre -> course
            indegree[course]++;       // Увеличиваем счетчик "входящих" стрелок для цели
        }

        // 3. ПОИСК СТАРТОВЫХ ТОЧЕК
        // Очередь q хранит курсы, у которых НЕТ пререквизитов (их можно учить прямо сейчас).
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < num_courses; i++) {
            // Если долгов (indegree) нет, добавляем в очередь на прохождение
            if (indegree[i] == 0) q.offer(i);
        }

        // 4. ПРОЦЕСС "ОБУЧЕНИЯ" (Обход)
        int visited_count = 0; // Считаем, сколько курсов мы реально смогли пройти
        while (!q.isEmpty()) {
            int curr = q.poll(); // Берем доступный курс из очереди
            visited_count++;     // "Проходим" его и увеличиваем счетчик

            // Смотрим на все курсы, которые зависели от только что пройденного (curr)
            for (int neighbor : adj.get(curr)) {
                indegree[neighbor]--; // Уменьшаем их счетчик долгов на 1

                // Если после уменьшения долгов стало 0 — значит, все условия для
                // этого курса выполнены, его можно учить. Добавляем в очередь.
                if (indegree[neighbor] == 0) {
                    q.offer(neighbor);
                }
            }
        }

        // 5. ПРОВЕРКА НА ЦИКЛЫ
        // Если visited_count равен общему числу курсов, значит мы прошли всё.
        // Если меньше — значит часть курсов "зависла" в цикле и мы до них не добрались.
        return visited_count == num_courses;
    }
}