stringtranslate.com

Теорема Ханани–Тутте

В топологической теории графов теорема Ханани–Татте является результатом о четности пересечений ребер в рисунке графа . Она утверждает, что каждый рисунок на плоскости непланарного графа содержит пару независимых ребер (не имеющих общей конечной точки), которые пересекают друг друга нечетное число раз. Эквивалентно, ее можно сформулировать как критерий планарности: граф является планарным тогда и только тогда, когда он имеет рисунок, в котором каждая пара независимых ребер пересекается равномерно (или не пересекается вообще). [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] .

Ссылки

  1. ^ ab Шефер, Маркус (2013), «К теории планарности: Ханани–Тутте и варианты планарности», Журнал графовых алгоритмов и приложений , 17 (4): 367–440, doi : 10.7155/jgaa.00298 , MR  3094190.
  2. ^ Хойнацкий, Ч. (1934), «Über wesentlich unplättbare Kurven im drei Dimensionen Raume», Fundamenta Mathematicae , 23 (1): 135–142, doi : 10.4064/fm-23-1-135-142. См. в частности (1), стр. 137.
  3. ^ Tutte, WT (1970), «К теории чисел пересечения», Журнал комбинаторной теории , 8 : 45–53, doi :10.1016/s0021-9800(70)80007-2, MR  0262110.
  4. ^ Левоу, Рой Б. (1972), «Об алгебраическом подходе Тутта к теории кроссинговых чисел», Труды Третьей юго-восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский атлантический университет, Бока-Ратон, Флорида, 1972) , Флоридский атлантический университет, Бока-Ратон, Флорида, стр. 315–314, MR  0354426.
  5. ^ Шефер, Маркус, «Ханани-Тутте и связанные с ним результаты», в Барани, И.; Бёрочки, К.Дж.; Тот, Г.Ф.; и др. (ред.), Геометрия — интуитивная, дискретная и выпуклая — дань уважения Ласло Фейесу Тоту (PDF) , Математические исследования Общества Бояи, Берлин: Springer
  6. ^ ван Кампен, ER (1933), «Komplexe in euklidischen Räumen», Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 9 (1): 72–78, doi : 10.1007/BF02940628, MR  3069580, S2CID  121909529.
  7. ^ У, Вэнь-Цюнь (1955), «О реализации комплексов в евклидовых пространствах. I», Acta Mathematica Sinica , 5 : 505–552, MR  0076334.
  8. ^ Шапиро, Арнольд (1957), «Препятствия к вложению комплекса в евклидово пространство. I. Первое препятствие», Annals of Mathematics , Вторая серия, 66 (2): 256–269, doi :10.2307/1969998, JSTOR  1969998, MR  0089410.
  9. ^ Ву, Вэнь Цзюнь (1985), «О планарном вложении линейных графов. I», Журнал системной науки и математических наук , 5 (4): 290–302, MR  0818118. Продолжение в 6 (1): 23–35, 1986.
  10. ^ Pelsmajer, Michael J.; Schaefer, Marcus; Stasi, Despina (2009), «Сильный Hanani–Tutte на проективной плоскости», SIAM Journal on Discrete Mathematics , 23 (3): 1317–1323, CiteSeerX 10.1.1.217.7182 , doi :10.1137/08072485X, MR  2538654 .
  11. ^ Фулек, Радослав; Кинчл, Ян (2019), «Контрпример к расширению теоремы Ханани–Тутте на поверхности рода 4», Combinatorica , 39 (6): 1267–1279, arXiv : 1709.00508 , doi : 10.1007/s00493-019-3905-7
  12. ^ Фулек, Радослав; Пельсмайер, Майкл Дж.; Шефер, Маркус (2021), «Сильный Ханани – Тутте для тора», Бучин, Кевин; Колин де Вердьер, Эрик (ред.), 37-й Международный симпозиум по вычислительной геометрии, SoCG 2021, 7–11 июня 2021 г., Буффало, Нью-Йорк, США (виртуальная конференция) , LIPics, vol. 189, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, стр. 38:1–38:15, arXiv : 2009.01683 , doi : 10.4230/LIPIcs.SoCG.2021.38
  13. ^ Фулек, Радослав; Пельсмайер, Майкл Дж.; Шефер, Маркус; Штефанкович, Дэниел (2013), «Ханани-Тутте, монотонные рисунки и планарность уровней», в Пахе, Янош (ред.), Тридцать эссе по геометрической теории графов , Springer, ISBN 978-1-4614-0110-0.
  14. ^ Пах, Янош ; Тот, Геза (2000), «Какое же это число пересечения?», Журнал комбинаторной теории , Серия B, 80 (2): 225–246, doi : 10.1006/jctb.2000.1978 , MR  1794693.
  15. ^ Pelsmajer, Michael J.; Schaefer, Marcus; Štefankovič, Daniel (2007), «Удаление четных пересечений», Journal of Combinatori Theory , Series B, 97 (4): 489–500, doi :10.1016/j.jctb.2006.08.001, MR  2325793.
  16. ^ Гутвенгер, К.; Мютцель, П.; Шефер, М. (2014), «Практический опыт использования Ханани–Тутта для проверки c-планарности», Труды шестнадцатого семинара по разработке алгоритмов и экспериментам (ALENEX) 2014 г. , стр. 86–97, doi : 10.1137/1.9781611973198.9, ISBN 978-1-61197-319-8.