Гипотеза Харборта

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Нерешённые проблемы математики: Любой планарный граф имеет целочисленное вложение Фари?

Гипотеза Харборта утверждает, что любой планарный граф имеет планарное представление, в котором каждое ребро является отрезком целочисленной длины[1][2][3]. Эта гипотеза носит имя Хайко Харборта[англ.] и (если верна) усилила бы теорему Фари о существовании рисунка с прямолинейными рёбрами для любого планарного графа. По этой причине рисунок графа с целочисленными длинами рёбер известен также как целочисленное вложение Фари[4]. Не смотря на многочисленные исследования в этом направлении гипотеза остаётся открытой[5].

Целочисленное вложение Фари октаэдрального графа

Специальные классы графов[править | править код]

Хотя неизвестно, верна ли гипотеза Харборта для всех планарных графов, она была доказана для некоторых специальных видов планарных графов.

Один из классов графов, которые имеют целочисленное вложение Фари – это графы, которые могут быть сведены к нулевому графу последовательностью операций двух видов:

  • Удаление вершины со степенью, не превосходящей два.
  • Замена вершины степени три ребром между двумя из его соседей. (Если такое ребро уже существует, вершина может быть удалена без добавления ребра между соседями.)

Для такого графа рациональное вложение Фари может быть построено постепенно путём обращения процесса удаления, используя факт, что множество точек, находящихся на рациональном расстоянии от двух заданных точек, плотно на плоскости и что если три точки находятся на рациональном расстоянии от одной пары и на расстоянии, равном квадратным корням из рациональных чисел от двух других пар, то точки, находящиеся на рациональном расстоянии от всех трёх точек, плотны на плоскости [6][7]. Расстояния в таком вложении можно сделать целочисленными путём масштабирования на подходящий множитель. Основываясь на этом построении, известны что следующие графы имеют целочисленные вложения Фари: двудольные планарные графы, (2,1)-разеженные планарные графы, планарные графы с древесной шириной, не превосходящей 3, и графы степени 4 и менее, которые либо содержат алмаз в качестве подграфа, либо не являются рёберно 4-связными графами[4][8][9].

В частности, графы, которые можно свести к пустому графу путём удаления только вершин степени два и менее (2-вырожденные планарные графы), включают как внешнепланарные графы, так и параллельно-последовательные графы. Однако, для внешнепланарных графов возможно прямое построение целочисленного вложения Фари, основанное на существовании бесконечных подмножеств единичной окружности, в которых все расстояния рациональны[10].

Кроме того целочисленные вложения Фари известны для каждого из пяти правильных многогранников[3].

Связанные гипотезы[править | править код]

Более сильная версия гипотезы Харборта, представленная Клебером[11], предполагает, что любой планарный граф имеет планарный рисунок, в котором координаты вершин и длины рёбер являются целыми числами[12]. Известно, что это верно для 3-регулярных графов[13], для графов, имеющих максимальную степень 4, но не являющихся 4-регулярными[14], и для планарных 3-деревьев[14].

Другой открытой проблемой в геометрии является проблема Эрдёша — Улама[англ.], касающаяся существования плотных подмножеств на плоскости, в которых все расстояния являются рациональными числами. Если бы такое подмножество существовало, оно бы формировало универсальное множество точек, которое можно было бы использовать для отрисовки всех планарных графов с рациональными длинами рёбер (а потому, после подходящего масштабирования, с целочисленными длинами рёбер). Однако, Улам высказал гипотезу, что плотные множества с рациональными расстояниями не существуют[15]. Согласно теореме Эрдёша — Эннинга бесконечные множества неколлинеарных точек, в которых все расстояния являются целыми числами, не существует. Это не исключает существование множеств в которых все расстояния рациональны, но из этого следует, что в любом таком множестве знаменатели рациональных расстояний могут быть произвольно большими.

См. также[править | править код]

Примечания[править | править код]

  1. ↑ Hartsfield, Ringel, 2013, с. 247.
  2. ↑ Kemnitz, Harborth, 2001, с. 191–195.
  3. ↑ 1 2 Harborth, Kemnitz, Möller, Süssenbach, 1987, с. 118–122.
  4. ↑ 1 2 Sun, 2013.
  5. ↑ Brass, Moser, Pach, 2005, с. 250.
  6. ↑ Almering, 1963, с. 192–199.
  7. ↑ Berry, 1992, с. 391–398.
  8. ↑ Biedl, 2011.
  9. ↑ Sun, 2011.
  10. ↑ Klee, Wagon, 1991, с. 132–135.
  11. ↑ Kleber, 2008.
  12. ↑ Kleber, 2008, с. 50–53.
  13. ↑ Geelen, Guo, McKinnon, 2008, с. 270–274.
  14. ↑ 1 2 Benediktovich, 2013, с. 2061–2064.
  15. ↑ Solymosi, de Zeeuw, 2010, с. 393–401.

Литература[править | править код]

  • Nora Hartsfield, Gerhard Ringel. Pearls in Graph Theory: A Comprehensive Introduction. — Courier Dover Publications, 2013. — (Dover Books on Mathematics). — ISBN 9780486315522.. Репринт издания 1994 Academic Press
  • Arnfried Kemnitz, Heiko Harborth. Plane integral drawings of planar graphs // Discrete Mathematics. — 2001. — Т. 236, вып. 1–3. — doi:10.1016/S0012-365X(00)00442-8.. Кемнит и Харборт приписывают оригинальную публикацию гипотезы статье Харбота, Кемнита, Мёллера и Сюссенбаха (Harborth et al. (1987))
  • Peter Brass, William O. J. Moser, János Pach. Research Problems in Discrete Geometry. — Springer, 2005. — ISBN 9780387299297.
    • П. Брасс, У. Мозер, Я. Пах. Открытые проблемы дискретной геометрии. — M., 2021. — ISBN 978-5-4439-4057-1.
  • Almering J. H. J. Rational quadrilaterals // Indagationes Mathematicae. — 1963. — Т. 25. — doi:10.1016/S1385-7258(63)50020-1.
  • Berry T. G. Points at rational distance from the vertices of a triangle // Acta Arithmetica. — 1992. — Т. 62, вып. 4. — doi:10.4064/aa-62-4-391-398.
  • Heiko Harborth, Arnfried Kemnitz, Meinhard Möller, Andreas Süssenbach. Ganzzahlige planare Darstellungen der platonischen Körper // Elemente der Mathematik. — 1987. — Т. 42, вып. 5. — С. 118–122.
  • Therese Biedl. Drawing some planar graphs with integer edge-lengths // Proc. Canadian Conference on Computational Geometry (CCCG 2011). — 2011.
  • Timothy Sun. Rigidity-Theoretic Constructions of Integral Fary Embeddings // Proc. Canadian Conference on Computational Geometry (CCCG 2011). — 2011.
  • Timothy Sun. Drawing some 4-regular planar graphs with integer edge lengths // Proc. Canadian Conference on Computational Geometry (CCCG 2013). — 2013.
  • Victor Klee, Stan Wagon. Problem 10: Does the plane contain a dense rational set? // Old and New Unsolved Problems in Plane Geometry and Number Theory. — Cambridge University Press, 1991. — Т. 11. — (Dolciani mathematical expositions). — ISBN 978-0-88385-315-3.
  • Michael Kleber. Encounter at far point // Mathematical Intelligencer. — 2008. — Т. 1. — doi:10.1007/BF02985756.
  • Jim Geelen, Anjie Guo, David McKinnon. Straight line embeddings of cubic planar graphs with integer edge lengths // Journal of Graph Theory. — 2008. — Т. 58, вып. 3. — doi:10.1002/jgt.20304.
  • Vladimir I. Benediktovich. On rational approximation of a geometric graph // Discrete Mathematics. — 2013. — Т. 313, вып. 20. — doi:10.1016/j.disc.2013.06.018.
    • Владимир Иванович Бенедиктович. О рациональной аппроксимации геометрического графа // Дискретная математика. — 2013. — Т. 313, вып. 20.
  • József Solymosi, Frank de Zeeuw. On a question of Erdős and Ulam // Discrete and Computational Geometry. — 2010. — Т. 43, вып. 2. — doi:10.1007/s00454-009-9179-x. — arXiv:0806.3095.
Источник — https://ru.wikipedia.org/w/index.php?title=Гипотеза_Харборта&oldid=135995890