В лекции MIT OpenCourseWare профессор Эрик Демейн подводит итог изучению теории графов, переходя от симметричных связей к ориентированным структурам — диграфам. Основное внимание уделяется направленным ациклическим графам (DAG), которые позволяют математически описать любые процессы с зависимостями: от алгоритмов параллельных вычислений до простых повседневных дел.
🧭 От связей к векторам: Что такое диграф 0:12
Профессор Демейн начинает с того, что классические ненаправленные графы не всегда подходят для моделирования реальности. В жизни часто встречаются «односторонние» отношения: дороги с односторонним движением, подписки в соцсетях (follow вместо двустороннего friendship) или сетевые соединения, работающие только на передачу. Для таких случаев используются направленные графы, или диграфы.
Основные отличия диграфа от обычного графа:
- Ребра как упорядоченные пары: Если в обычном графе ребро ${u, v}$ — это просто набор из двух вершин, то в диграфе $(u, v)$ — это вектор, идущий строго от $u$ к $v$.
- Петли разрешены: В этой модели вершина может иметь ребро, ведущее в саму себя (например, $(d, d)$).
- Двусторонние связи: Чтобы показать связь в обе стороны, нужно нарисовать два отдельных ребра: от $u$ к $v$ и от $v$ к $u$.
🔢 Степени вершин и «рукопожатия» в новом формате 3:43
В ориентированных графах понятие «степень вершины» (количество инцидентных ребер) разделяется на две составляющие: входящую степень (in-degree) и исходящую степень (out-degree). Профессор отмечает, что использовать просто термин «степень» в данном контексте некорректно, так как это вносит двусмысленность.
Математически это меняет классическую «лемму о рукопожатиях». В ненаправленном графе сумма степеней вершин равнялась удвоенному количеству ребер. В диграфах ситуация, по мнению Демейна, даже «чище»:
- Сумма входящих степеней всех вершин в точности равна количеству ребер.
- Сумма исходящих степеней также равна общему количеству ребер.
Это логично, поскольку каждое ребро имеет ровно один «начальный» конец и ровно один «конечный».
🚶 Маршруты и достижимость: Куда ведут стрелки? 7:46
Определение прогулки (walk) остается почти прежним: это последовательность вершин, где каждая пара соединена ребром. Однако теперь необходимо строго «соблюдать стрелки» — двигаться только вперед по направлению ребра. Демейн проводит параллель с теорией автоматов (state machines), изученной ранее в курсе: прогулка в графе — это фактически выполнение (execution) в конечном автомате.
Циклы в диграфах ведут себя иначе, чем в обычных графах:
- В обычном графе минимальный цикл состоит из 3 вершин (треугольник).
- В диграфе возможен цикл длиной 1 (петля у одной вершины) или длиной 2 (две вершины, связанные ребрами «туда-обратно»).
Понятие «связности» также усложняется. Если в обычном графе связность симметрична, то в диграфе из того, что вершина $A$ достижима из $B$, вовсе не следует достижимость $B$ из $A$.
🔗 Сильная связность и конденсация графа 15:18
Вершины называются сильно связными, если они взаимно достижимы: из $u$ можно попасть в $v$, и наоборот. Если это условие выполняется для всех пар вершин, весь граф называется сильно связным. В таких графах невозможно «застрять» — из любой точки всегда есть путь в любую другую.
Демейн переносит теорему об Эйлеровом цикле на диграфы. Эйлеров цикл (проходящий через каждое ребро ровно один раз) существует тогда и только тогда, когда:
- Граф сильно связан.
- Для каждой вершины входящая степень равна исходящей ($in\text{-}degree = out\text{-}degree$).
Интересным инструментом анализа является граф конденсации. Мы берем все сильно связные компоненты (группы вершин, внутри которых можно ходить как угодно) и «схлопываем» каждую в одну супер-вершину. Ребра между этими компонентами показывают общую структуру зависимостей в графе. Самое важное свойство конденсации — полученный граф всегда будет ациклическим.
🧥 DAG: Графы без циклов и искусство одеваться 29:27
Направленные ациклические графы (Directed Acyclic Graphs, или DAG) — это «золотой стандарт» для описания зависимостей. Если в графе зависимостей есть цикл (A нужно сделать до B, B до C, а C до A), то процесс никогда не начнется.
Профессор приводит бытовой пример: процесс одевания. Каждому предмету одежды соответствует вершина, а ребра указывают на необходимую последовательность:
- Носки нужно надеть раньше обуви.
- Брюки — раньше ремня и обуви.
- Рубашку — раньше куртки, а куртку — раньше зимнего пальто и шапки.
Для таких графов существует топологическая сортировка — такой линейный порядок вершин, при котором каждое ребро ведет от более раннего элемента к более позднему. Это и есть правильная последовательность действий (например, «носки → брюки → туфли»).
🛠️ Алгоритмы и доказательства: Источники, стоки и индукция 37:33
Чтобы доказать, что для любого DAG существует топологический порядок, Демейн вводит понятия источника и стока:
- Источник (Source): Вершина с входящей степенью 0.
- Сток (Sink): Вершина с исходящей степенью 0.
Лемма гласит: в любом DAG есть хотя бы один источник и один сток. Доказательство строится от противного: если мы возьмем самый длинный путь и предположим, что перед его началом есть еще одна вершина, мы либо найдем еще более длинный путь, либо обнаружим цикл, что невозможно в DAG.
Алгоритм топологической сортировки прост:
- Найти любой источник (задачу, которую ничто не предваряет).
- Поместить его в начало списка и «удалить» из графа.
- Повторять, пока граф не опустеет.
⚡ Параллельное выполнение задач и критический путь 51:48
Если у нас есть неограниченное количество исполнителей (процессоров), мы можем выполнять независимые задачи параллельно. Например, надевать левый и правый носок одновременно. Возникает вопрос: каков минимальный span (время выполнения) всего проекта?
Теорема, которую доказывает профессор: минимальное время выполнения равно количеству вершин в самом длинном пути в графе.
Для этого вводится понятие глубины вершины — длины самого длинного пути, заканчивающегося в ней. Глубина и определяет момент времени, в который задача может быть выполнена. Задачи с глубиной 0 (источники) делаются в первый такт, с глубиной 1 — во второй и так далее.
📅 Цепи и антицепи: От теории к интерфейсу календаря 1:08:15
В завершение лекции Демейн вводит понятия из теории частичного порядка:
- Цепь (Chain): Набор вершин, где все элементы сравнимы (между любыми двумя есть путь). Это последовательные задачи.
- Антицепь (Anti-chain): Набор вершин, где никакие два элемента не сравнимы. Это задачи, которые можно делать одновременно.
Эти абстрактные понятия имеют прямое прикладное значение. Профессор объясняет, как современные электронные календари (Google Calendar или Outlook) отображают события. Конфликтующие (пересекающиеся по времени) события в графе зависимостей являются несравнимыми — они образуют антицепь. Чтобы красиво отрисовать календарь, нужно разбить все события на минимальное количество колонок. Согласно математической двойственности, количество колонок (цепей) в оптимальном интерфейсе равно размеру самой большой антицепи (максимальному числу одновременно идущих дел).
