Теорема Ханани — Татта

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

История

Результат назван именем израильского математика Хаима Ханани, который в 1934 году доказал, что любой рисунок двух минимальных непланарных графов $K_{5}$ и $K_{3,3}$ имеет пару рёбер с нечётным числом пересечений, и именем британского, позднее канадского математика У. Т. Татта, который сформулировал теорему полностью в 1970году. Параллельно развивали похожие идеи в алгебраической топологии Эгберт ван Кампен, Арнольд С. Шапиро и У Вэньцзюнь.

Приложения

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

Обобщения

Для другой поверхности S, отличной от плоскости, граф может быть нарисован на S без пересечений тогда и только тогда, когда он может быть нарисован таким образом, что все пары рёбер пересекаются чётное число раз. Это утверждение известно как слабая теорема Ханани — Татта для S. Строгая теорема Ханани — Татта, известная для проективной плоскости, как и для евклидовой плоскости, утверждает, что граф может быть нарисован без пересечений на поверхности S тогда и только тогда, когда он может быть нарисован так, что все независимые пары рёбер пересекаются чётное число раз без учёта рёбер, имеющих общие вершины.

Тот же подход, в котором показывается, что пара рёбер с чётным числом пересечений может быть игнорирована или исключена в некоторых типах рисунков графа и используется этот факт для создания системы линейных уравнения, описывающих существование визуализации графа, была применена к некоторым другим задачам рисования графа, включая восходящее планарное представление, визуализацию, минимизирующую число непересекающихся рёбер, и кластерную планарность.