После весенних каникул студенты Массачусетского технологического института (MIT) вернулись в аудитории, чтобы продолжить погружение в дискретную математику и теорию графов. Профессор Эрик Демейн посвятил лекцию детальному разбору неориентированных графов, понятию связности, историческим математическим загадкам и уникальным свойствам деревьев. Этот материал закладывает основу для понимания алгоритмов, которые ежедневно управляют логистикой, социальными сетями и компьютерными сетями по всему миру.
🚶♂️ Обход графа: маршруты и пути 0:00
Изучение неориентированных графов начинается с базовых определений. Простой неориентированный граф состоит из множества вершин $V$ и множества рёбер $E$. Главное условие такого графа — рёбра представляют собой пары строго различных вершин, то есть граф не содержит петель и кратных рёбер.
Для перемещения по графу вводятся понятия маршрута (walk) и пути (path), которые в разных математических курсах могут называться по-разному, что требует особой внимательности от студентов. В рамках данного курса принята следующая терминология:
- Маршрут (walk) — это конечная последовательность вершин, где каждая последующая вершина соединена с предыдущей валидным ребром графа. В маршрутах абсолютно легально повторять как вершины, так и рёбра.
- Длина маршрута — это количество рёбер в последовательности (обозначается как $k$), которое всегда на единицу меньше количества вершин. Математически допустимы даже маршруты нулевой длины, состоящие всего из одной изолированной вершины.
- Путь (path) — это частный, более строгий случай маршрута, в котором полностью запрещены повторения как вершин, так и рёбер.
Подобные абстракции лежат в основе множества прикладных задач. Профессор Демейн напомнил, что каждый раз, когда человек использует Google Maps, алгоритмы ищут кратчайший или наименее энергозатратный путь на графе дорог.
Аналогичные принципы работают при маршрутизации пакетов данных в интернете, анализе цепочек знакомств в социальных сетях (знаменитый эксперимент Стэнли Милгрэма в 1960-х годах показал правило «шести рукопожатий», а в современных цифровых сетях это расстояние сократилось примерно до пяти), и даже при анализе пространств состояний в головоломках, таких как «игра в пятнашки».
🔗 Связность и теорема о кратчайшем маршруте 7:07
Две вершины графа называются связанными, если между ними существует хотя бы один маршрут. В неориентированных графах это отношение обладает свойством симметричности: если есть маршрут от вершины $u$ к вершине $v$, то, просто развернув последовательность рёбер, мы получим маршрут от $v$ к $u$.
Помимо симметричности, отношение связности обладает свойствами рефлексивности (любая вершина связана сама с собой маршрутом нулевой длины) и транзитивности (если $u$ связана с $v$, а $v$ связана с $w$, то $u$ связана с $w$ через конкатенацию их маршрутов).
Профессор Демейн сформулировал и доказал важную фундаментальную теорему:
Вершины $u$ и $v$ связаны маршрутом тогда и только тогда, когда между ними существует путь (маршрут без повторяющихся вершин).
Доказательство этой теоремы строится в два этапа:
- Справа налево (простая часть): Любой путь по определению является разновидностью маршрута, поэтому существование пути автоматически гарантирует существование маршрута.
- Слева направо (метод противоречия): Предположим, что между $u$ и $v$ есть маршруты. Выберем среди них кратчайший маршрут. Если предположить, что в этом кратчайшем маршруте есть повторяющаяся вершина (например, $v_i = v_j$), то весь кусок маршрута между этими шагами можно просто вырезать. В результате получится ещё более короткий маршрут, что напрямую противоречит условию минимальности. Значит, кратчайший маршрут не может содержать повторов и является путём.
🧩 Компоненты связности 19:19
Весь граф называется связным, если любая пара его вершин связана между собой. Если же в графе есть изолированные, недостижимые друг от друга участки, речь заходит о компонентах связности.
Для строгого математического описания этого феномена Демейн ввёл понятие индуцированного подграфа (induced subgraph). Чтобы построить такой подграф, необходимо выбрать подмножество вершин, а затем включить в него все рёбра исходного графа, которые соединяют эти выбранные вершины.
Компонента связности — это индуцированный подграф, построенный на множестве всех вершин, достижимых из какой-то конкретной начальной вершины. Важнейшее свойство компонентов связности заключается в том, что они разбивают (партиционируют) граф. Это означает, что каждая вершина и каждое ребро графа принадлежат ровно одной компоненте связности.
Понимание структуры компонентов помогает анализировать сложные системы и игры:
- «Игра в пятнашки» (8-puzzle): Пространство состояний этой головоломки огромно (около 100 000 вершин), но оно не является связным. Граф разбивается ровно на две изолированные компоненты связности — одну для чётных перестановок и одну для нечётных. Перейти из одной компоненты в другую по правилам игры невозможно.
- Кубик Рубика: В зависимости от математического описания правил вращения, граф состояний этой головоломки может содержать 12 изолированных компонентов связности.
🔄 Замкнутые маршруты, циклы и загадка Кёнигсберга 25:57
Если маршрут начинается и заканчивается в одной и той же вершине ($v_0 = v_k$), он называется замкнутым. Если при этом внутри маршрута нет других повторений вершин и рёбер, то перед нами цикл (cycle).
Профессор подчеркнул, что в простых неориентированных графах тривиальный разворот вида $u \to v \to u$ не считается циклом, так как он дважды использует одно и то же ребро. Из этого следует, что минимальная длина цикла в таких графах всегда составляет не менее трёх.
Историческим фундаментом всей теории графов стала задача, которую в 1736 году решил великий математик Леонард Эйлер. Жители города Кёнигсберг задались вопросом: можно ли обойти все городские мосты, соединяющие острова и берега реки, пройдя по каждому из них ровно один раз?
Эйлер перевёл эту задачу на язык математических абстракций, где суша стала вершинами, а мосты — рёбрами. Так возникли два классических понятия:
- Эйлеров маршрут (Euler walk) — маршрут, который проходит через каждое ребро графа ровно один раз.
- Эйлеров цикл (Euler tour) — замкнутый эйлеров маршрут, возвращающийся в начальную точку.
🏆 Эйлеровы циклы: критерии существования 36:31
Главная теорема лекции, доказанная профессором Демейном, полностью описывает условия, при которых в графе существует эйлеров цикл:
Граф имеет эйлеров цикл тогда и только тогда, когда он связен (за исключением изолированных вершин) и каждая его вершина имеет чётную степень (чётное число входящих рёбер).
Доказательство необходимости чётной степени (слева направо) интуитивно понятно: эйлеров цикл можно представить как непрерывное движение карандаша по бумаге. Каждый раз, заходя в вершину по одному ребру, мы обязаны выйти из неё по другому («что вошло, должно выйти»). Каждое посещение вершины тратит ровно два её ребра, поэтому суммарная степень всех вершин обязана быть чётной.
Доказательство достаточности (справа налево) гораздо сложнее. Для него Демейн использовал концепцию максимального следа (trail) — маршрута, в котором рёбра не повторяются, а сам маршрут выбирается максимально возможной длины. Доказательство состоит из двух ключевых утверждений:
- Максимальный след обязан быть замкнутым: Если бы он был открытым (начинался в $v_0$ и заканчивался в $v_k$), то в конечной вершине мы бы использовали нечётное число рёбер. Но поскольку общая степень вершины чётная, там обязательно осталось бы хотя бы одно неиспользованное ребро. Это позволило бы продлить маршрут, что противоречит его максимальной длине.
- Замкнутый максимальный след обязан покрывать все рёбра графа: Если бы осталось хотя бы одно непокрытое ребро, то в силу связности графа мы смогли бы найти точку пересечения этого ребра с нашим циклом и «встроить» его внутрь, сделав след длиннее.
Из этой теоремы вытекает важное следствие (следствие из теоремы) для открытых эйлеровых маршрутов: граф имеет незамкнутый эйлеров маршрут тогда и только тогда, когда он связен и содержит ровно две вершины с нечётной степенью. Именно в одной из этих вершин маршрут начнётся, а в другой завершится. Если вершин с нечётной степенью больше двух, нарисовать граф одним росчерком пера невозможно.
Для доказательства этого следствия Эрик Демейн применил излюбленный метод программистов и математиков — редукцию (сведение задачи). Мы можем взять исходный граф с двумя нечётными вершинами $u$ и $v$, искусственно добавить виртуальную вершину $x$ и соединить её рёбрами с $u$ и $v$.
Степени $u$ и $v$ станут чётными, степень $x$ также будет равна двум (чётная). В таком модифицированном графе гарантированно существует эйлеров цикл, из которого затем достаточно удалить виртуальную вершину $x$, чтобы получить искомый открытый эйлеров маршрут.
🌳 Деревья и магия индукции через листья 1:07:35
Финальная часть лекции была посвящена фундаментальной структуре данных и математическому объекту — деревьям. В математике деревом называется простой неориентированный граф, который одновременно является связным и ацикличным (не содержащим циклов). Совокупность нескольких изолированных деревьев называют лесом.
Важнейшим элементом дерева является лист (leaf) — вершина, степень которой равна ровно 1. Профессор сформулировал «лемму о листьях»: любое дерево, содержащее хотя бы две вершины, имеет как минимум два листа. Доказывается это через поиск самого длинного пути в дереве — его начальная и конечная вершины гарантированно окажутся листьями, иначе путь можно было бы продолжить.
Наличие листьев позволяет применять к деревьям элегантный метод математической индукции через «лемму о стрижке деревьев» (tree-pruning lemma):
Если удалить из дерева любой лист вместе с его единственным ребром, оставшийся граф гарантированно останется деревом.
С помощью этого инструмента Демейн с легкостью доказал классическую теорему о размере деревьев: любое дерево с $n$ вершинами всегда содержит ровно $n - 1$ рёбер.
База индукции очевидна: дерево с одной вершиной ($n = 1$) имеет $0$ рёбер. Для шага индукции ($n > 1$) мы находим в дереве лист, отсекаем его и получаем меньшее дерево с числом вершин $n - 1$. По предположению индукции, в нём содержится $(n - 1) - 1 = n - 2$ рёбер. Возвращая отрезанный лист и его ребро обратно, мы получаем исходное дерево с $(n - 2) + 1 = n - 1$ рёбер. Теорема доказана.
Профессор Демейн подытожил, что деревья обладают и другими удивительными свойствами: между любыми двумя вершинами в дереве всегда существует один и только один путь, и они представляют собой минимально возможные связные графы (удаление любого ребра приведёт к потере связности). На следующей лекции студентов ждёт переход от неориентированных структур к направленным — ориентированным графам.
