Interested Article - Граф единичных расстояний

Граф Петерсена является графом единичных расстояний — его можно нарисовать на плоскости так, что каждое ребро будет иметь единичную длину.

В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны . Граф единичных расстояний без пересечений называется спичечным графом .

Проблема Нелсона — Эрдёша — Хадвигера касается хроматического числа графов единичных расстояний. Известно, что существуют графы единичных расстояний, требующие 5 цветов для правильной раскраски и что все такие графы можно раскрасить не более чем в 7 цветов. Другая важная открытая задача, касающаяся графов единичных расстояний, спрашивает, сколько рёбер может иметь такой граф по отношению к числу вершин .

Примеры

Граф гиперкуба Q ₄ граф единичных расстояний.

Следующие графы являются графами единичных расстояний:

любой цикл ;
любая решётка ;
любой граф гиперкуба ;
любая звезда ;
граф Петерсена ;
граф Хивуда ( );
Колесо W ₇ ;
веретено Мозера , наименьший граф единичных расстояний с хроматическим числом 4.

Подграфы графов единичных расстояний

Рисунок с единичными расстояниями графа Мёбиуса-Кантора , в котором некоторые несмежные рёбра тоже находятся на расстоянии единица.

Некоторые авторы определяют граф единичных расстояний как граф, который можно вложить в плоскость так, что любые две смежные вершины должны находиться на расстоянии единица, но не обязательно вершины, находящиеся на расстоянии единица, должны быть смежными. Например граф Мёбиуса-Кантора имеет графическое представление такого вида.

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

Колесо W ₇ с удалённой спицей как пример графа единичных расстояний, но не строгого графа единичных расстояний

Граф, образованный удалением одной спицы из колеса W ₇ , является подграфом единичных расстояний, но не строгим графом единичных расстояний( , С. 94).

Подсчёт единичных расстояний

Нерешённые проблемы математики : Сколько единичных расстояний может быть в множестве из n точек?

Эрдёш ( ) предложил задачу оценки в множестве из n точек числа пар, находящихся на расстоянии единицы. В терминах теории графов вопрос состоит в оценке плотности графа единичных расстояний.

Граф гиперкуба даёт нижнюю границу числа единичных расстояний, пропорциональную $n\log n.$ Рассматривая точки квадратной решётки с тщательно выбранным расстоянием, Эрдёш нашёл улучшенную нижнюю границу

n^{1+c/\log \log n},

и предложил премию в 500 долл. за выяснение, выражается ли максимальное число единичных расстояний функцией того же вида ( ). Лучшая известная верхняя граница, согласно Спенсеру, Семереди и Троттеру ( ), пропорциональна

n^{4/3};

.

Эту границу можно рассматривать как число попаданий точек на единичные окружности и она тесно связана с теоремой Семереди — Троттера об инцидентности точек и прямых.

Представление алгебраических чисел и теорема Бекмана-Куорлса

Для любого алгебраического числа A можно найти граф единичных расстояний G , в котором некоторые пары вершин находятся на расстоянии A во всех представлениях с единичными расстояниями G ( ) ( ). Этот результат подразумевает конечную версию —для любых двух точек p и q , находящихся на расстоянии A , существует конечный граф единичных расстояний, содержащий p и q такой, что любое преобразование плоскости, сохраняющее единичные расстояния в этом графе сохраняет расстояние между p и q ( ). Полная теорема Бекмана — Куорлса утверждает, что любое преобразование евклидовой плоскости (или пространства большей размерности), сохраняющее расстояния должно быть конгруэнцией . Таким образом для бесконечных графов единичных расстояний, вершинами которых является вся плоскость, любой автоморфизм графа должен быть изометрией ( ).

Обобщение на большие размерности

Определение графа единичных расстояний может быть естественным образом обобщено на любую размерность евклидового пространства . Любой граф можно вложить в виде набора точек в пространство достаточно высокой размерности. Маэхара и Рёдль ( ) показали, что размерность, необходимая для вложения графа, может быть ограничена удвоенной максимальной степенью.

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

Вычислительная сложность

Является NP-трудной задачей , точнее полной для теории существования вещественных чисел , проверить, является ли данный граф графом единичных расстояний или строгим графом единичных расстояний ( ).

См. также

Граф единичных кругов , граф на плоскости, у которого две вершины соединены ребром, если расстояние между точками не превосходит единицы.

Примечания

F. S. Beckman, D. A., Jr. Quarles. On isometries of Euclidean spaces // Proceedings of the American Mathematical Society. — 1953. — Т. 4 . — С. 810—815 .
Paul Erdős. On sets of distances of n points. — American Mathematical Monthly . — The American Mathematical Monthly, 1946. — Т. 53. — С. 248—250. — doi : . .
Paul Erdős, Miklós Simonovits. On the chromatic number of geometric graphs // Ars Combinatoria. — 1980. — Т. 9 . — С. 229—246 . Как цитировано в , p. 97.
Eberhard H.-A. Gerbracht. . — 2009. — arXiv : . .
Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Planar unit-distance graphs having planar unit-distance complement // Discrete Mathematics. — 2008. — Т. 308 , вып. 10 . — С. 1973—1984 . — doi : . .
Greg Kuperberg. . — 1992. 29 сентября 2006 года.
Hiroshi Maehara. Distances in a rigid unit-distance graph in the plane // Discrete Applied Mathematics. — 1991. — Т. 31 , вып. 2 . — С. 193—200 . — doi : . .
Hiroshi Maehara. Extending a flexible unit-bar framework to a rigid one // Discrete Mathematics. — 1992. — Т. 108 , вып. 1-3 . — С. 167—174 . — doi : . .
Hiroshi Maehara, Vojtech Rödl. // Graphs and Combinatorics. — 1990. — Т. 6 , вып. 4 . — С. 365—367 . — doi : . .
Marcus Schaefer. Thirty Essays on Geometric Graph Theory / János Pach. — Springer, 2013. — С. 461—482. — doi : . .
Alexander Soifer. The Mathematical Coloring Book. — Springer-Verlag, 2008. — ISBN 978-0-387-74640-1 .
Joel Spencer, Endre Szemerédi, William T. Trotter. Graph Theory and Combinatorics. — Academic Press, 1984. — С. 293—308.
Apoloniusz Tyszka. Discrete versions of the Beckman-Quarles theorem // Aequationes Mathematicae. — 2000. — Т. 59 , вып. 1—2 . — С. 124—133 . — doi : . .
Arjana Žitnik, Boris Horvat, Tomaž Pisanski. . — 2010. — Т. 1109 .