Теорема Ханани – Тутте
В топологической теории графов теорема Ханани-Тутте является результатом о четности пересечений ребер на рисунке графа . Он утверждает, что каждый рисунок на плоскости непланарного графа содержит пару независимых ребер (не имеющих общую конечную точку), которые пересекают друг друга нечетное количество раз. Эквивалентно это можно сформулировать как критерий планарности: граф планарен тогда и только тогда, когда у него есть рисунок, на котором каждая пара независимых ребер пересекается равномерно (или не пересекается вообще). [ 1 ]
История
[ редактировать ]Результат назван в честь Хаима Ханани , который доказал в 1934 году, что каждый рисунок двух минимальных неплоских графов K 5 и K 3,3 имеет пару ребер с нечетным числом пересечений, [ 2 ] и после У. Т. Тутта , который явно сформулировал полную теорему в 1970 году. [ 3 ] Параллельное развитие подобных идей в алгебраической топологии приписывают Эгберту ван Кампену , Арнольду С. Шапиро и Ву Вэньцзюню . [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ]
Приложения
[ редактировать ]Одним из следствий теоремы является то, что проверку того, является ли граф плоским, можно сформулировать как решение системы линейных уравнений над конечным полем второго порядка . Эти уравнения можно решить за полиномиальное время , но полученные алгоритмы менее эффективны, чем другие известные тесты планарности. [ 1 ]
Обобщения
[ редактировать ]Для других поверхностей S, кроме плоскости, граф можно нарисовать на S без пересечений тогда и только тогда, когда его можно нарисовать таким образом, чтобы все пары ребер пересекались четное число раз; это известно как слабая теорема Ханани–Татте для S . Сильная теорема Ханани–Татте утверждает, что граф можно нарисовать без пересечений на S тогда и только тогда, когда его можно нарисовать таким образом, что все независимые пары ребер пересекаются четное число раз, без учета количества пересечений между ребра, имеющие общую конечную точку; [ 10 ] эта сильная версия справедлива не для всех поверхностей, [ 11 ] но известно, что оно справедливо для плоскость, проективная плоскость и тор . [ 12 ]
Тот же подход, в котором показано, что пары ребер с четным числом пересечений можно игнорировать или исключить в графическом изображении некоторого типа, и используется этот факт для создания системы линейных уравнений, описывающих существование рисунка, был применяется к нескольким другим задачам рисования графов, включая восходящие плоские рисунки , [ 13 ] рисунки, минимизирующие количество непересекающихся ребер, [ 14 ] [ 15 ] и кластерная планарность . [ 16 ]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Шефер, Маркус (2013), «К теории планарности: Ханани-Тутте и варианты планарности», Журнал графовых алгоритмов и приложений , 17 (4): 367–440, doi : 10.7155/jgaa.00298 (неактивен в 2024–07 гг.) -29), МР 3094190
{{citation}}:CS1 maint: DOI неактивен по состоянию на июль 2024 года ( ссылка ) . - ^ Хойнацкий, Ч. (1934), «О существенно несглаживаемых кривых в трехмерном пространстве» , Fundamenta Mathematicae , 23 (1): 135–142, doi : 10.4064/fm-23-1-135-142 . См., в частности (1), с. 137.
- ^ Тутте, В.Т. (1970), «К теории пересекающихся чисел», Журнал комбинаторной теории , 8 : 45–53, doi : 10.1016/s0021-9800(70)80007-2 , MR 0262110 .
- ^ Левоу, Рой Б. (1972), «Об алгебраическом подходе Тутте к теории пересекающихся чисел», Труды Третьей Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1972) , Атлантический университет Флориды, Бока-Ратон, Флорида, стр. 315–314, MR 0354426 .
- ^ Шефер, Маркус, «Ханани-Тутте и связанные с ним результаты», в Барани, И.; Бёрочки, К.Дж.; Тот, Г.Ф.; и др. (ред.), Геометрия — интуитивная, дискретная и выпуклая — дань уважения Ласло Фейесу Тоту (PDF) , Математические исследования Общества Бояи, Берлин: Springer
- ^ ван Кампен, Э.Р. (1933), «Комплексы в евклидовых пространствах», Статьи математического семинара Гамбургского университета , 9 (1): 72–78, doi : 10.1007/BF02940628 , MR 3069580 , S2CID 121909529 .
- ^ Ву, Вен-Цюн (1955), «О реализации комплексов в евклидовых пространствах. I», Acta Mathematica Sinica , 5 : 505–552, MR 0076334 .
- ^ Шапиро, Арнольд (1957), «Препятствия к вложению комплекса в евклидово пространство. I. Первое препятствие», Annals of Mathematics , Second Series, 66 (2): 256–269, doi : 10.2307/1969998 , JSTOR 1969998 , МР 0089410 .
- ^ Ву, Вэнь Цзюнь (1985), «О плоском вложении линейных графов. I», Журнал системных наук и математических наук , 5 (4): 290–302, MR 0818118 . Продолжение в 6 (1): 23–35, 1986 .
- ^ Пельсмайер, Майкл Дж.; Шефер, Маркус; Стаси, Деспина (2009), «Стронг Ханани-Тутте на проективной плоскости», SIAM Journal on Discrete Mathematics , 23 (3): 1317–1323, CiteSeerX 10.1.1.217.7182 , doi : 10.1137/08072485X , MR 2538654 .
- ^ Фулек, Радослав; Кынчл, Ян (2019), «Контрпример к расширению теоремы Ханани–Тутте на поверхность рода 4», Combinatorica , 39 (6): 1267–1279, arXiv : 1709.00508 , doi : 10.1007/s00493-019-3905 -7
- ^ Фулек, Радослав; Пельсмайер, Майкл Дж.; Шефер, Маркус (2021), «Сильный Ханани – Тутте для тора», в Бучине, Кевине; Колин де Вердьер, Эрик (ред.), 37-й Международный симпозиум по вычислительной геометрии, SoCG 2021, 7–11 июня 2021 г., Буффало, Нью-Йорк, США (виртуальная конференция) , LIPics, vol. 189, Schloss Dagstuhl – Центр компьютерных наук Лейбница, стр. 38:1–38:15, arXiv : 2009.01683 , doi : 10.4230/LIPIcs.SoCG.2021.38
- ^ Фулек, Радослав; Пельсмайер, Майкл Дж.; Шефер, Маркус; Штефанкович, Дэниел (2013), «Ханани-Тутте, монотонные рисунки и планарность уровней», в Пахе, Янош (ред.), Тридцать эссе по геометрической теории графов , Springer, ISBN 978-1-4614-0110-0 .
- ^ Пах, Янош ; Тот, Геза (2000), «Какое это число пересечений?», Журнал комбинаторной теории , серия B, 80 (2): 225–246, doi : 10.1006/jctb.2000.1978 , MR 1794693 .
- ^ Пельсмайер, Майкл Дж.; Шефер, Маркус; Штефанкович, Даниэль (2007), «Удаление четных пересечений», Журнал комбинаторной теории , серия B, 97 (4): 489–500, doi : 10.1016/j.jctb.2006.08.001 , MR 2325793 .
- ^ Гутвенгер, К.; Мутцель, П. ; Шефер, М. (2014), «Практический опыт использования Ханани-Тутте для проверки c-планарности», 2014 г., Материалы шестнадцатого семинара по разработке алгоритмов и экспериментам (ALENEX) , стр. 86–97, doi : 10.1137/1.9781611973198.9 , ISBN 978-1-61197-319-8 .