Русская Википедия:Гипотеза Харборта
Шаблон:Unsolved Гипотеза Харборта утверждает, что любой планарный граф имеет планарное представление, в котором каждое ребро является отрезком целочисленной длиныШаблон:SfnШаблон:SfnШаблон:Sfn. Эта гипотеза носит имя Шаблон:Нп5 и (если верна) усилила бы теорему Фари о существовании рисунка с прямолинейными рёбрами для любого планарного графа. По этой причине рисунок графа с целочисленными длинами рёбер известен также как целочисленное вложение ФариШаблон:Sfn. Не смотря на многочисленные исследования в этом направлении гипотеза остаётся открытойШаблон:Sfn.
Специальные классы графов
Хотя неизвестно, верна ли гипотеза Харборта для всех планарных графов, она была доказана для некоторых специальных видов планарных графов.
Один из классов графов, которые имеют целочисленное вложение Фари – это графы, которые могут быть сведены к нулевому графу последовательностью операций двух видов:
- Удаление вершины со степенью, не превосходящей два.
- Замена вершины степени три ребром между двумя из его соседей. (Если такое ребро уже существует, вершина может быть удалена без добавления ребра между соседями.)
Для такого графа рациональное вложение Фари может быть построено постепенно путём обращения процесса удаления, используя факт, что множество точек, находящихся на рациональном расстоянии от двух заданных точек, плотно на плоскости и что если три точки находятся на рациональном расстоянии от одной пары и на расстоянии, равном квадратным корням из рациональных чисел от двух других пар, то точки, находящиеся на рациональном расстоянии от всех трёх точек, плотны на плоскости Шаблон:SfnШаблон:Sfn. Расстояния в таком вложении можно сделать целочисленными путём масштабирования на подходящий множитель. Основываясь на этом построении, известны что следующие графы имеют целочисленные вложения Фари: двудольные планарные графы, (2,1)-разеженные планарные графы, планарные графы с древесной шириной, не превосходящей 3, и графы степени 4 и менее, которые либо содержат алмаз в качестве подграфа, либо не являются рёберно 4-связными графамиШаблон:SfnШаблон:SfnШаблон:Sfn.
В частности, графы, которые можно свести к пустому графу путём удаления только вершин степени два и менее (2-вырожденные планарные графы), включают как внешнепланарные графы, так и параллельно-последовательные графы. Однако, для внешнепланарных графов возможно прямое построение целочисленного вложения Фари, основанное на существовании бесконечных подмножеств единичной окружности, в которых все расстояния рациональныШаблон:Sfn.
Кроме того целочисленные вложения Фари известны для каждого из пяти правильных многогранниковШаблон:Sfn.
Связанные гипотезы
Более сильная версия гипотезы Харборта, представленная КлеберомШаблон:Sfn, предполагает, что любой планарный граф имеет планарный рисунок, в котором координаты вершин и длины рёбер являются целыми числамиШаблон:Sfn. Известно, что это верно для 3-регулярных графовШаблон:Sfn, для графов, имеющих максимальную степень 4, но не являющихся 4-регулярнымиШаблон:Sfn, и для планарных 3-деревьевШаблон:Sfn.
Другой открытой проблемой в геометрии является Шаблон:Нп5, касающаяся существования плотных подмножеств на плоскости, в которых все расстояния являются рациональными числами. Если бы такое подмножество существовало, оно бы формировало универсальное множество точек, которое можно было бы использовать для отрисовки всех планарных графов с рациональными длинами рёбер (а потому, после подходящего масштабирования, с целочисленными длинами рёбер). Однако, Улам высказал гипотезу, что плотные множества с рациональными расстояниями не существуютШаблон:Sfn. Согласно теореме Эрдёша — Эннинга бесконечные множества неколлинеарных точек, в которых все расстояния являются целыми числами, не существует. Это не исключает существование множеств в которых все расстояния рациональны, но из этого следует, что в любом таком множестве знаменатели рациональных расстояний могут быть произвольно большими.
См. также
- Целочисленный треугольник, целочисленное вложение Фари треугольного графа
- Спичечный граф, граф, который можно нарисовать на плоскости со всеми рёбрами длины 1
- Граф Эрдёша — Диофанта, полный граф с целыми расстояниями, который не может быть расширен до большего полного графа с тем же свойством
- Совершенный кубоид, реализация с целыми расстояниями в трёхмерном пространстве
Примечания
Литература
- Шаблон:Книга. Репринт издания 1994 Academic Press
- Шаблон:Статья. Кемнит и Харборт приписывают оригинальную публикацию гипотезы статье Харбота, Кемнита, Мёллера и Сюссенбаха (Шаблон:Harvtxt)
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
