Теорема Ханани — Татта
Теорема Ханани — Татта — утверждение относительно чётности пересечений рёбер в визуализации графа. Теорема утверждает, что любой рисунок непланарного графа на плоскости содержит пару независимых рёбер (не имеющих общие вершины), которые пересекают друг друга нечётное число раз. Эквивалентно, утверждение может быть переформулировано как критерий планарности — граф планарен тогда и только тогда, когда он имеет рисунок, в котором каждая пара независимых рёбер пересекается чётное число раз (или не пересекается вообще)Шаблон:Sfn.
История
Результат назван именем израильского математика Хаима Ханани, который в 1934 году доказал, что любой рисунок двух минимальных непланарных графов и имеет пару рёбер с нечётным числом пересечений,Шаблон:Sfn и именем британского, позднее канадского математика У. Т. Татта, который сформулировал теорему полностью в 1970годуШаблон:Sfn. Параллельно развивали похожие идеи в алгебраической топологии Эгберт ван Кампен, Арнольд С. Шапиро и У ВэньцзюньШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
Приложения
Одно из следствий теоремы — проверка, является ли граф планарным, может быть сформулирована как решение системы линейных уравнений над Шаблон:Нп5. Эти уравнения могут быть решены за полиномиальное время, но получающиеся алгоритмы менее эффективны, чем другие известные тесты планарностиШаблон:Sfn.
Обобщения
Для другой поверхности S, отличной от плоскости, граф может быть нарисован на S без пересечений тогда и только тогда, когда он может быть нарисован таким образом, что все пары рёбер пересекаются чётное число раз. Это утверждение известно как слабая теорема Ханани — Татта для S. Строгая теорема Ханани — Татта, известная для проективной плоскости, как и для евклидовой плоскости, утверждает, что граф может быть нарисован без пересечений на поверхности S тогда и только тогда, когда он может быть нарисован так, что все независимые пары рёбер пересекаются чётное число раз без учёта рёбер, имеющих общие вершиныШаблон:Sfn.
Тот же подход, в котором показывается, что пара рёбер с чётным числом пересечений может быть игнорирована или исключена в некоторых типах рисунков графа и используется этот факт для создания системы линейных уравнения, описывающих существование визуализации графа, была применена к некоторым другим задачам рисования графа, включая восходящее планарное представлениеШаблон:Sfn, визуализацию, минимизирующую число непересекающихся рёберШаблон:SfnШаблон:Sfn, и Шаблон:Нп5Шаблон:Sfn.