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

Hanani–Tutte theorem

В топологическая теория графов, то Теорема Ханани – Тутте это результат на паритет из краевые переходы в рисунок графика. В нем говорится, что каждый рисунок в плоскости неплоский граф содержит пару независимых ребер (не имеющих общих конечных точек), которые пересекают друг друга нечетное количество раз. Эквивалентно, это можно сформулировать как критерий планарности: граф является плоским тогда и только тогда, когда он имеет чертеж, на котором каждая пара независимых ребер пересекается равномерно (или не пересекается вообще).[1]

История

Результат назван в честь Хаим Ханани, который в 1934 году доказал, что каждый рисунок из двух минимальные неплоские графы K5 и K3,3 имеет пару ребер с нечетным числом пересечений,[2] и после В. Т. Тутте, который явно сформулировал полную теорему в 1970 г.[3] Параллельное развитие подобных идей в алгебраическая топология был зачислен на Эгберт ван Кампен, Арнольд С. Шапиро, и У Вэньцзюнь.[4][5][6][7][8][9]

Приложения

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

Обобщения

Для других поверхностей S чем на плоскости, график можно нарисовать на S без пересечений тогда и только тогда, когда его можно нарисовать так, чтобы все пары ребер пересекались четное число раз; это известно как слабая теорема Ханани – Тутте для S. Сильная теорема Ханани – Тутте, известная проективная плоскость а также для евклидовой плоскости, утверждает, что граф может быть нарисован без пересечений на S тогда и только тогда, когда его можно нарисовать таким образом, чтобы все независимые пары ребер пересекались четное число раз, без учета количества пересечений между ребрами, которые имеют общую конечную точку.[10]

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

Рекомендации

  1. ^ а б Шефер, Маркус (2013), «К теории планарности: варианты Ханани – Тутте и планарность», Журнал графических алгоритмов и приложений, 17 (4): 367–440, Дои:10.7155 / jgaa.00298, МИСТЕР 3094190.
  2. ^ Chojnacki, Ch. (1934), "Über wesentlich unplättbare Kurven im dreidimensionalen Raume", Fundamenta Mathematicae, Институт математики Польской академии наук, 23 (1): 135–142, Дои:10.4064 / FM-23-1-135-142. См., В частности, (1), с. 137.
  3. ^ Тутте, В. Т. (1970), «К теории чисел пересечения», Журнал комбинаторной теории, 8: 45–53, Дои:10.1016 / с0021-9800 (70) 80007-2, МИСТЕР 0262110.
  4. ^ Левоу, Рой Б. (1972), "Об алгебраическом подходе Тутте к теории пересекающихся чисел", Труды Третьей Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1972), Атлантический университет Флориды, Бока-Ратон, Флорида, стр. 315–314, МИСТЕР 0354426.
  5. ^ Шефер, Маркус, «Ханани-Тутте и связанные результаты», в Bárány, I .; Böröczky, K. J .; Tóth, G. F .; и другие. (ред.), Геометрия - интуитивная, дискретная и выпуклая - дань уважения Ласло Фейесу Тоту (PDF), Математические исследования Общества Бойяи, Берлин: Springer
  6. ^ ван Кампен, Э. (1933), "Komplexe in euklidischen Räumen", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 9 (1): 72–78, Дои:10.1007 / BF02940628, МИСТЕР 3069580.
  7. ^ Ву, Вэнь-Цунь (1955), «О реализации комплексов в евклидовых пространствах. I», Acta Mathematica Sinica, 5: 505–552, МИСТЕР 0076334.
  8. ^ Шапиро, Арнольд (1957), «Препятствия к вложению комплекса в евклидово пространство. I. Первое препятствие», Анналы математики, Вторая серия, 66 (2): 256–269, Дои:10.2307/1969998, JSTOR 1969998, МИСТЕР 0089410.
  9. ^ Ву, Вэнь Цзюнь (1985), «О плоском вложении линейных графов. I», Журнал системологии и математических наук, 5 (4): 290–302, МИСТЕР 0818118. Продолжение в 6 (1): 23–35, 1986.
  10. ^ Пельсмайер, Майкл Дж .; Шефер, Маркус; Стази, Деспина (2009), "Сильный Ханани-Тутте на проективной плоскости", Журнал SIAM по дискретной математике, 23 (3): 1317–1323, CiteSeerX 10.1.1.217.7182, Дои:10.1137 / 08072485X, МИСТЕР 2538654.
  11. ^ Фулек, Радослав; Пельсмайер, Майкл Дж .; Шефер, Маркус; Штефанкович, Даниэль (2013), «Ханани-Тутте, монотонные рисунки и планарность уровня», в Пах, Янош (ред.), Тридцать очерков по геометрической теории графов, Спрингер, ISBN 978-1-4614-0110-0.
  12. ^ Пах, Янош; Тот, Геза (2000), «Какой это номер пересечения?», Журнал комбинаторной теории, Серия B, 80 (2): 225–246, Дои:10.1006 / jctb.2000.1978, МИСТЕР 1794693.
  13. ^ Пельсмайер, Майкл Дж .; Шефер, Маркус; Штефанкович, Даниэль (2007), «Удаление четных переходов», Журнал комбинаторной теории, Серия B, 97 (4): 489–500, Дои:10.1016 / j.jctb.2006.08.001, МИСТЕР 2325793.
  14. ^ Gutwenger, C .; Муцель, П.; Шефер, М., "Практический опыт работы с Ханани-Тутте для тестирования c-планарность », 2014 Труды шестнадцатого семинара по разработке алгоритмов и экспериментов (ALENEX), стр. 86–97, Дои:10.1137/1.9781611973198.9.