Нерешённые проблемы математики : Любой планарный граф имеет целочисленное вложение Фари?

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

Специальные классы графов

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

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

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

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

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

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

Связанные гипотезы

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

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

См. также

• Целочисленный треугольник , целочисленное вложение Фари треугольного графа
• Спичечный граф , граф, который можно нарисовать на плоскости со всеми рёбрами длины 1
• Граф Эрдёша — Диофанта , полный граф с целыми расстояниями, который не может быть расширен до большего полного графа с тем же свойством
• Совершенный кубоид , реализация с целыми расстояниями в трёхмерном пространстве

Примечания

Литература