Планарные графы и теорема Эйлера: Укладка без пересечений
Планарный (плоский) граф — это граф, который можно нарисовать на плоскости таким образом, что его ребра будут пересекаться только в своих общих вершинах (узлах). Концепция планарности имеет колоссальное значение не только в чистой дискретной математике, но и в современной инженерии: именно эти законы определяют, можно ли развести дорожки на однослойной печатной плате без замыканий, или как оптимально спроектировать топологию микропроцессора.
Основой изучения планарных графов служит формула Эйлера. Для любого связного планарного графа, уложенного на плоскости, справедливо строгое равенство: V - E + F = 2, где V — количество вершин, E — количество ребер, а F — количество граней (областей, ограниченных ребрами, включая одну бесконечную внешнюю грань). Эта формула удивительна тем, что она является топологическим инвариантом — как бы мы ни деформировали граф, соотношение остается неизменным. Это же правило применимо к выпуклым многогранникам в трехмерном пространстве (Платоновым телам).
Но как алгоритмически определить, является ли произвольный граф планарным? Долгие годы математики искали критерий планарности, пока польский математик Казимеж Куратовский не доказал свою знаменитую теорему в 1930 году. Теорема Куратовского гласит, что граф является планарным тогда и только тогда, когда он не содержит в себе подграфов, гомеоморфных (топологически эквивалентных) двум специфическим графам:
- K5 — полный граф на пяти вершинах (каждая из пяти вершин соединена с каждой). Представляет интуитивную проблему "слишком высокой плотности связей".
- K3,3 — полный двудольный граф, известный как задача о «трех домах и трех колодцах». В нем три вершины одной доли соединены со всеми тремя вершинами другой доли.
Если в вашем графе можно "найти" структуру K5 или K3,3 (путем стягивания или удаления некоторых ребер), начертить его на плоскости без пересечений физически невозможно. Для компьютерной проверки планарности графов сегодня существуют сложные алгоритмы, работающие за линейное время O(V). В IT-сфере свойства планарных графов также применяются при автоматическом построении пользовательских интерфейсов (UI-layout) и визуализации схем баз данных, где пересечение линий связей делает схему нечитаемой.
