Топология
Topology на собеседовании
Топология - не абстракция ради абстракции. Каждый алгоритм на графах считает β₀, каждая проверка планарности использует χ, каждый анализ ДНК-укладки - теорию узлов.
- Number of Islands и связные компоненты на собеседованиях - вычисление β₀ через DSU
- Проверка планарности схемы при разводке VLSI - неравенство E ≤ 3V − 6
- Анализ конфигураций ДНК и белков с узлами - инварианты узлов из теории узлов
Связность: топологическая интерпретация
«Определи, связен ли граф» - это задача про β₀ (нулевую группу гомологий). «Найди все компоненты связности» - это вычисление H₀. «Есть ли цикл в графе?» - это вопрос про β₁. Топология даёт единый язык для десятков задач на графах, которые на первый взгляд кажутся не связанными.
Топологические факты о графе G = (V, E): β₀(G) = число компонент связности; β₁(G) = |E| − |V| + β₀ = число независимых циклов (цикломатическое число); χ(G) = |V| − |E| = β₀ − β₁. Union-Find (DSU) вычисляет β₀ за O(α(n)) на операцию - практически за константу.
| Задача на интервью | Топологический смысл | Инструмент | Сложность |
|---|---|---|---|
| Number of Islands (LeetCode 200) | β₀ - компоненты связности | BFS/DFS/DSU | O(n·α(n)) |
| Number of Provinces (LC 547) | β₀ неориентированного графа | DSU | O(n²) |
| Redundant Connection (LC 684) | Ребро, создающее β₁≥1 | DSU (extra_edges) | O(n·α(n)) |
| Course Schedule (LC 207) | β₁ орграфа = есть ли цикл | Топологическая сортировка | O(V+E) |
| Connected Components in Graph | β₀ = количество компонент | DSU | O(n·α(n)) |
На собеседовании: услышали «связность» или «компоненты» → сразу думать про DSU. Услышали «цикл в неориентированном графе» → DSU с extra_edges. «Цикл в ориентированном» → топологическая сортировка (Kahn's BFS). Объяснить: β₀ = число компонент, β₁ = число независимых циклов.
Граф имеет 7 вершин, 9 рёбер и 2 компоненты связности. Чему равно β₁ (цикломатическое число)?
β₁ = |E| − |V| + β₀ = 9 − 7 + 2 = 4. Граф содержит 4 независимых цикла.
Теорема Жордана и планарные графы
Теорема Жордана кажется закономерной: замкнутая несамопересекающаяся кривая делит плоскость на два области (внутреннюю и внешнюю). Но её доказательство непросто - оно требует фундаментальных групп и гомологий. В программировании она лежит в основе алгоритма «точка внутри многоугольника» и проверки планарности графов.
Следствия для алгоритмов: 1. «Точка внутри многоугольника» - считаем число пересечений луча с границей. Чётное → снаружи, нечётное → внутри. 2. Планарный граф удовлетворяет формуле Эйлера: V − E + F = 2 (с одной внешней гранью). 3. K₅ и K₃,₃ непланарны - теорема Куратовского. Это можно объяснить через γ(K₅) = 1 (genus = 1, нужен тор).
На интервью: «Можно ли нарисовать граф без пересечений рёбер?» - это вопрос о планарности. Быстрый тест: если E > 3V − 6 (или E > 2V − 4 для двудольных графов) → граф непланарен. Полная проверка - алгоритм Хопкрофта-Тарьяна за O(V).
Теорема четырёх красок: любой планарный граф можно раскрасить в 4 цвета. Это теорема о топологии плоскости (или сферы, поскольку S² и ℝ² с точкой на бесконечности гомеоморфны). На торе нужно до 7 цветов - формула: χ_T = ⌊(7 + √(1+48/genus))/2⌋.
Граф K₅ имеет V=5, E=10. Почему он непланарен согласно неравенству для планарных графов?
Для любого связного планарного графа E ≤ 3V − 6. K₅: E=10 > 9=3·5−6. Необходимое условие нарушено, значит K₅ непланарен.
Теория узлов и биоинформатика
ДНК в ядре клетки суперскручена и завязана в узлы. Топоизомераза - фермент, который разрезает одну нить ДНК, пропускает сквозь неё другую и сшивает обратно - буквально изменяет тип узла. Понимание этих операций требует теории узлов. В CS: верификация программ и модели памяти используют топологические инварианты.
Узел - это вложение S¹ в S³. Два узла эквивалентны, если один можно деформировать в другой без разрезания (изотопия). Инварианты узлов позволяют различать узлы: полином Александера Δ(t), полином Джонса V(t), число расцветки (количество 3-раскрасок дуг диаграммы узла). Тривиальный узел (unknot) имеет Δ(t)=1.
Связь с биоинформатикой: 1. ДНК-репликация требует размотки двойной спирали → топоизомераза I изменяет число витков 2. рекомбинация (recombination) - это хирургия узлов 3. белки сворачиваются с непростой топологией - около 1% белков содержат настоящие узлы в цепи. Программы AlphaFold и PDB хранят топологическую информацию о цепях.
| Узел | Скрещивания | Δ(t) | Раскрасок (mod 3) | Биологический пример |
|---|---|---|---|---|
| Unknot (тривиальный) | 0 | 1 | 3 | Расслабленная ДНК |
| Trefoil 3₁ | 3 | 1−t+t² | 9 | ДНК после рекомбинации |
| Figure-eight 4₁ | 4 | −t+3−t⁻¹ | 3 | Белки с узлом 4₁ |
| Cinquefoil 5₁ | 5 | 1−t+t²−t³+t⁴ | 15 | Топоизомераза II |
| Solomon's seal 6₂ | 6 | t²−3t+5−3t⁻¹+t⁻² | 3 | Синтетическая ДНК |
Число раскрасок в 3 цвета > 3 означает, что узел нетривиален (отличен от unknot). Но обратное неверно: figure-eight имеет 3 раскраски (как unknot), однако он нетривиален. Для различения нужны более сильные инварианты - полином Александера или Джонса.
Как Fox 3-coloring помогает определить, является ли узел нетривиальным?
Unknot имеет ровно 3 раскраски. Если раскрасок больше (9, 15, ...) - узел нетривиален. Но 3 раскраски не гарантируют unknot (figure-eight тоже имеет 3).
Эйлерова характеристика и genus на интервью
«На какой поверхности можно нарисовать K₅ без пересечений?» - типичный вопрос FAANG на знание алгоритмов укладки графов. Ответ: на торе (genus 1). Это требует знания формулы χ = 2 − 2g и неравенства Эйлера для графов на поверхностях. Такие вопросы проверяют глубину понимания, а не зазубренные алгоритмы.
Для графа G, уложенного на ориентируемой поверхности рода g без пересечений рёбер: V − E + F = χ = 2 − 2g. Для граней-треугольников: 2E ≥ 3F, откуда E ≤ 3(V + 2g − 2). Для двудольных графов (нет треугольников): E ≤ 2(V + 2g − 2). Минимальный genus, при котором граф укладывается, называется genus(G).
| Граф | V | E | genus | Поверхность | Применение |
|---|---|---|---|---|---|
| K₄ | 4 | 6 | 0 | Плоскость S² | Тетраэдр, планарные схемы |
| K₅ | 5 | 10 | 1 | Тор T² | VLSI с 1 слоем переходов |
| K₃,₃ | 6 | 9 | 1 | Тор T² | 3-утилиты на торе |
| K₆ | 6 | 15 | 1 | Тор T² | Полный граф 6 вершин |
| K₇ | 7 | 21 | 1 | Тор T² | 7 стран, 7 красок на торе |
| Petersen | 10 | 15 | 1 | Тор T² | Эталонный негамильтонов |
Шпаргалка для интервью: 1. E > 3V−6 → непланарен 2. genus(Kₙ) = ⌈(n-3)(n-4)/12⌉ 3. на торе можно красить в 7 цветов (теорема Хивуда) 4. treewidth(G) ≤ 3·genus(G)·Δ+1 - связь с динамическим программированием.
Граф K₃,₃ (двудольный, V=6, E=9). Почему он непланарен по числовому критерию?
Для двудольных планарных графов: E ≤ 2V−4 = 8. Но E=9 > 8 - K₃,₃ непланарен. В двудольных нет треугольников, поэтому оценка строже.
Что унифицирует курс
- β₀ и β₁ дают единый язык для задач на связность и цикличность
- Теорема Жордана лежит в основе алгоритма «точка внутри многоугольника» и проверки планарности
- Fox 3-coloring отличает нетривиальные узлы от unknot, хотя инвариант не полный
- Genus графа определяет минимальное число слоёв в VLSI и связан с treewidth
Сборка курса целиком
Финальная лекция собирает весь курс: компактность (top-03) → метрические пространства → фундаментальная группа → накрытия → гомологии → классификация поверхностей → характеристика Эйлера → многообразия → de Rham → TDA → ML, и всё это встречается в реальных задачах.
- Топология в ML и Data Science — предыдущая лекция курса, к которой явно отсылает финал
- Компактность и связность — база, без которой β₀ не определяется
- Гомологии и классификация поверхностей — источник χ = 2 − 2g, использованного для genus графов
Вопросы для размышления
- Какая задача с собеседования теперь читается иначе через β₀ или β₁?
- Number of Islands - это β₀ подграфа из единиц. Cycle Detection в неориентированном графе - это β₁ ≥ 1. Где ещё в production-коде встречаются эти инварианты?
- Граф зависимостей задач - это вопрос об ориентированных циклах (H₁ орграфа). Какие сборщики и системы CI это используют?