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

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

История

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

Приложения

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

Обобщения

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

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

Примечания

  1. ↑ 1 2 Schaefer, 2013, с. 367–440.
  2. ↑ Chojnacki, 1934, с. 135–142.
  3. ↑ Tutte, 1970, с. 45–53.
  4. ↑ Levow, 1972, с. 315–314.
  5. ↑ Schaefer, 2011.
  6. ↑ van Kampen, 1933, с. 72–78.
  7. ↑ Wu, 1955, с. 505–552.
  8. ↑ Shapiro, 1957, с. 256–269.
  9. ↑ Wu, 1985, с. 290–302.
  10. ↑ Pelsmajer, Schaefer, Stasi, 2009, с. 1317–1323.
  11. ↑ Fulek, Pelsmajer, Schaefer, Štefanković, 2013.
  12. ↑ Pach, Tóth, 2000, с. 225–246.
  13. ↑ Pelsmajer, Schaefer, Štefankovič, 2007, с. 489–500.
  14. ↑ Gutwenger, Mutzel, Schaefer, 2014, с. 86–97.

Литература

  • Marcus Schaefer. Toward a theory of planarity: Hanani–Tutte and planarity variants // Journal of Graph Algorithms and Applications. — 2013. — Т. 17, вып. 4. — С. 367–440. — doi:10.7155/jgaa.00298.
  • Ch. Chojnacki. Über wesentlich unplättbare Kurven im dreidimensionalen Raume // Fundamenta Mathematicae. — Institute of Mathematics Polish Academy of Sciences, 1934. — Т. 23, вып. 1. — С. 135–142. — doi:10.4064/fm-23-1-135-142.
  • Tutte W. T. Toward a theory of crossing numbers // Journal of Combinatorial Theory. — 1970. — Т. 8. — С. 45–53. — doi:10.1016/s0021-9800(70)80007-2.
  • Roy B. Levow. On Tutte's algebraic approach to the theory of crossing numbers // Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972). — Florida Atlantic Univ., Boca Raton, Fla., 1972. — С. 315–314.
  • Marcus Schaefer. Hanani–Tutte and related results // Geometry—Intuitive, Discrete, and Convex—A Tribute to László Fejes Tóth / Bárány I., Böröczky K. J., Tóth G. F., Pach J.. — Berlin: Springer, 2011. — (Bolyai Society Mathematical Studies).
  • van Kampen E. R. Komplexe in euklidischen Räumen // Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1933. — Т. 9, вып. 1. — С. 72–78. — doi:10.1007/BF02940628.
  • Wen-Tsün Wu. On the realization of complexes in Euclidean spaces. I // Acta Mathematica Sinica. — 1955. — Т. 5. — С. 505–552.
  • Arnold S. Shapiro. Obstructions to the imbedding of a complex in a Euclidean space. I. The first obstruction // Annals of Mathematics. — 1957. — Т. 66, вып. 2. — С. 256–269. — doi:10.2307/1969998. — JSTOR 1969998.
  • Wen Jun Wu. On the planar imbedding of linear graphs. I // Journal of Systems Science and Mathematical Sciences. — 1985. — Т. 5, вып. 4. — С. 290–302.. Продолжение в 6 (1): 23–35, 1986
  • Michael J. Pelsmajer, Marcus Schaefer, Despina Stasi. Strong Hanani-Tutte on the projective plane // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вып. 3. — С. 1317–1323. — doi:10.1137/08072485X.
  • Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefanković. Hanani–Tutte, monotone drawings, and level-planarity // Thirty essays on geometric graph theory / János Pach. — Springer, 2013. — ISBN 978-1-4614-0110-0.
  • János Pach, Géza Tóth. Which crossing number is it anyway? // Journal of Combinatorial Theory. — 2000. — Т. 80, вып. 2. — doi:10.1006/jctb.2000.1978.
  • Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing even crossings // Journal of Combinatorial Theory. — 2007. — Т. 97, вып. 4. — doi:10.1016/j.jctb.2006.08.001.
  • Gutwenger C., Mutzel P., Schaefer M. Practical experience with Hanani–Tutte for testing c-planarity // 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). — 2014. — doi:10.1137/1.9781611973198.9.

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!