График единичного расстояния

В математике , в частности в геометрической теории графов , граф единичных расстояний — это граф, образованный из набора точек на евклидовой плоскости путем соединения двух точек, если расстояние между ними равно единице. Чтобы отличить эти графы от более широкого определения, которое позволяет некоторым несмежным парам вершин находиться на расстоянии единица, их также можно назвать строгими графами единичных расстояний или верными графами единичных расстояний . Как наследственное семейство графов , их можно охарактеризовать запрещенными индуцированными подграфами . Графы единичных расстояний включают графы кактусов , графы спичек и пенни , а также графы гиперкубов . Обобщенные графы Петерсена являются нестрогими графами единичных расстояний.

Нерешенная задача Пола Эрдёша спрашивает, сколько ребер может иметь граф единичных расстояний на вершинах. Лучшая известная нижняя граница немного выше линейной по — далека от верхней границы , пропорциональной . Количество цветов, необходимых для раскраски графов единичных расстояний, также неизвестно ( проблема Хадвигера–Нельсона ): некоторые графы единичных расстояний требуют пяти цветов, и каждый граф единичных расстояний можно раскрасить семью цветами. Для каждого алгебраического числа существует граф единичных расстояний с двумя вершинами, которые должны находиться на этом расстоянии друг от друга. Согласно теореме Бекмана–Куорлза , единственными преобразованиями плоскости, которые сохраняют все графы единичных расстояний, являются изометрии .${\displaystyle n}$${\displaystyle n}$${\displaystyle n^{4/3}}$

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

Граф единичных расстояний для набора точек на плоскости — это неориентированный граф, вершинами которого являются эти точки , с ребром между двумя вершинами, если их евклидово расстояние равно единице. Говорят, что абстрактный граф является графом единичных расстояний, если возможно найти различные местоположения на плоскости для его вершин, так что его ребра имеют единичную длину и так, что все несмежные пары вершин имеют неединичные расстояния. Когда это возможно, абстрактный граф изоморфен графу единичных расстояний выбранных местоположений. В качестве альтернативы некоторые источники используют более широкое определение, позволяя несмежным парам вершин находиться на единичном расстоянии. Полученные графы являются подграфами графов единичных расстояний (как определено здесь). ^[2] Там, где терминология может быть неоднозначной, графы, в которых не-ребра должны находиться на неединичном расстоянии друг от друга, можно назвать строгими графами единичных расстояний ^[3] или верными графами единичных расстояний . ^[2] Подграфы графов единичных расстояний эквивалентны графам, которые можно нарисовать на плоскости, используя только одну длину ребра. ^[4] Для краткости в этой статье они называются «нестрогими графами единичных расстояний».

Графы единичных расстояний не следует путать с графами единичных дисков , которые соединяют пары точек, когда их расстояние меньше или равно единице, и часто используются для моделирования сетей беспроводной связи. ^[5]

Полный граф на двух вершинах является графом единичных расстояний, как и полный граф на трех вершинах ( треугольный граф ), но не полный граф на четырех вершинах. ^[3] Обобщая треугольный граф, каждый циклический граф является графом единичных расстояний, реализованным правильным многоугольником . ^[4] Два конечных графа единичных расстояний, соединенных в одной общей вершине, дают другой граф единичных расстояний, поскольку один из них можно вращать относительно другого, чтобы избежать нежелательных дополнительных единичных расстояний. ^[6] Соединяя таким образом графы, каждый конечный граф дерева или кактуса может быть реализован как граф единичных расстояний. ^[7]

Любое декартово произведение графов единичных расстояний производит другой граф единичных расстояний; однако, то же самое не верно для некоторых других распространенных графовых произведений. Например, сильное произведение графов , примененное к любым двум непустым графам, производит полные подграфы с четырьмя вершинами, которые не являются графами единичных расстояний. Декартовы произведения графов путей образуют графы-сетки любой размерности, декартовы произведения полного графа на двух вершинах являются графами гиперкуба , ^[8] а декартовы произведения графов треугольников являются графами Хэмминга . ^[9]${\displaystyle H(d,3)}$

Другие конкретные графы, которые являются графами единичных расстояний, включают граф Петерсена , ^[10] граф Хивуда , ^[11] граф колеса (единственный граф колеса, который является графом единичных расстояний), ^[3] и граф веретена Мозера и граф Голомба (малые 4- хроматические графы единичных расстояний). ^[12] Все обобщенные графы Петерсена , такие как изображенный граф Мёбиуса–Кантора , являются нестрогими графами единичных расстояний. ^[13]${\displaystyle W_{7}}$

Спичечные графы являются особым случаем графов единичных расстояний, в которых ни одно ребро не пересекается. Каждый спичечный граф является планарным графом , ^[14] но некоторые в противном случае планарные графы единичных расстояний (например, веретено Мозера) имеют пересечение в каждом представлении в виде графа единичных расстояний. Кроме того, в контексте графов единичных расстояний термин «планарный» следует использовать с осторожностью, поскольку некоторые авторы используют его для обозначения плоскости, в которой определены единичные расстояния, а не для запрета на пересечения. ^[3] Пенни -графы являются еще более особым случаем графов единичных расстояний и спичечных графов, в которых каждая несмежная пара вершин находится на расстоянии более одной единицы друг от друга. ^[14]

Нерешенная задача по математике :

Сколько единичных расстояний можно определить по набору точек?${\displaystyle n}$

(еще нерешенные проблемы по математике)

Пол Эрдёш  (1946) поставил задачу оценки того, сколько пар точек в наборе точек могут находиться на единичном расстоянии друг от друга. В терминах теории графов вопрос заключается в том, насколько плотным может быть граф единичных расстояний, и публикация Эрдёша по этому вопросу была одной из первых работ в экстремальной теории графов . ^[15] Графы гиперкубов и графы Хэмминга обеспечивают нижнюю границу числа единичных расстояний, пропорциональную Рассматривая точки в квадратной сетке с тщательно выбранным интервалом, Эрдёш нашел улучшенную нижнюю границу вида для константы и предложил 500 долларов за доказательство того, может ли число единичных расстояний также быть ограничено сверху функцией этого вида. ^[16] Самая известная верхняя граница для этой задачи: Эту границу можно рассматривать как подсчет инцидентностей между точками и единичными окружностями, и она тесно связана с неравенством числа пересечений и теоремой Семереди–Троттера о инцидентностях между точками и прямыми. ^[17]${\displaystyle n}$${\displaystyle n\log n.}$$${\displaystyle n^{1+c/\log \log n}}$$${\displaystyle с}$$${\displaystyle {\sqrt[{3}]{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$

Для малых значений точное максимальное число возможных ребер известно. Для этих чисел ребер: ^[18]${\displaystyle n}$${\displaystyle n=2,3,4,\точки}$

Если заданный граф не является нестрогим графом единичных расстояний, то не является и любой суперграф . Похожая идея работает для строгих графов единичных расстояний, но с использованием концепции индуцированного подграфа , подграфа, образованного из всех ребер между парами вершин в заданном подмножестве вершин. Если не является строгим графом единичных расстояний, то не является и любой другой , имеющий в качестве индуцированного подграфа. Из-за этих отношений между тем, является ли подграф или его суперграф графом единичных расстояний, можно описать графы единичных расстояний их запрещенными подграфами . Это минимальные графы, которые не являются графами единичных расстояний данного типа. Их можно использовать для определения того, является ли заданный граф графом единичных расстояний любого типа. является нестрогим графом единичных расстояний, тогда и только тогда, когда не является суперграфом запрещенного графа для нестрогих графов единичных расстояний. является строгим графом единичных расстояний, тогда и только тогда, когда не является индуцированным суперграфом запрещенного графа для строгих графов единичных расстояний. ^[8]${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle H}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

Для обоих графов нестрогих и строгих единичных расстояний запрещенные графы включают как полный граф, так и полный двудольный граф . Для , где бы ни размещались вершины на двухвершинной стороне этого графа, существует не более двух позиций на единичном расстоянии от них для размещения остальных трех вершин, поэтому невозможно разместить все три вершины в различных точках. ^[8] Это единственные два запрещенных графа для нестрогих единичных расстояний графов с числом вершин до пяти; существует шесть запрещенных графов с числом вершин до семи ^[6] и 74 для графов с числом вершин до девяти. Поскольку склеивание двух единичных расстояний графов (или их подграфов) в вершине дает строгие (соответственно нестрогие) единичные расстояний графы, каждый запрещенный граф является двусвязным графом , который не может быть образован этим процессом склеивания. ^[19]${\displaystyle К_{4}}$ ${\displaystyle К_{2,3}}$${\displaystyle К_{2,3}}$

Граф колеса может быть реализован как строгий граф единичных расстояний с шестью вершинами, образующими единичный правильный шестиугольник , и седьмой в центре шестиугольника. Удаление одного из ребер из центральной вершины создает подграф, который все еще имеет ребра единичной длины, но который не является строгим графом единичных расстояний. Размещение его вершин в виде правильного шестиугольника является единственным способом ( с точностью до конгруэнтности ) разместить вершины в различных местах таким образом, чтобы смежные вершины находились на единичном расстоянии друг от друга, и это размещение также помещает две конечные точки отсутствующего ребра на единичное расстояние. Таким образом, это запрещенный граф для строгих графов единичных расстояний ^[20], но не один из шести запрещенных графов для нестрогих графов единичных расстояний. Другие примеры графов, которые являются нестрогими графами единичных расстояний, но не строгими графами единичных расстояний, включают граф, образованный путем удаления внешнего ребра из , и граф с шестью вершинами, образованный из треугольной призмы путем удаления ребра из одного из ее треугольников. ^[19]${\displaystyle W_{7}}$ ${\displaystyle W_{7}}$

Для каждого алгебраического числа , можно построить граф единичных расстояний , в котором некоторая пара вершин находится на расстоянии во всех представлениях единичных расстояний . ^[21] Этот результат подразумевает конечную версию теоремы Бекмана–Куорлза : для любых двух точек и на расстоянии друг от друга существует конечный жесткий граф единичных расстояний , содержащий и такой, что любое преобразование плоскости, которое сохраняет единичные расстояния в этом графе, также сохраняет расстояние между и . ^[22] Полная теорема Бекмана–Куорлза утверждает, что единственными преобразованиями евклидовой плоскости (или евклидова пространства большей размерности), которые сохраняют единичные расстояния, являются изометрии . Эквивалентно, для бесконечного графа единичных расстояний , порожденного всеми точками на плоскости, все автоморфизмы графа сохраняют все расстояния на плоскости, а не только единичные расстояния. ^[23]${\displaystyle \альфа}$${\displaystyle G}$${\displaystyle \альфа}$${\displaystyle G}$${\displaystyle p}$${\displaystyle д}$${\displaystyle \альфа}$${\displaystyle p}$${\displaystyle д}$${\displaystyle p}$${\displaystyle д}$

Если — алгебраическое число с модулем 1, которое не является корнем из единицы , то целочисленные комбинации степеней образуют конечно порожденную подгруппу аддитивной группы комплексных чисел , график единичных расстояний которой имеет бесконечную степень . Например, можно выбрать в качестве одного из двух комплексных корней многочлена , создавая график единичных расстояний бесконечной степени с четырьмя генераторами. ^[24]${\displaystyle \альфа}$${\displaystyle \альфа}$${\displaystyle \альфа}$${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$

Проблема Хадвигера–Нельсона касается хроматического числа графов единичных расстояний, а точнее бесконечного графа единичных расстояний, образованного всеми точками евклидовой плоскости. По теореме де Брейна–Эрдёша , которая предполагает аксиому выбора , это эквивалентно запросу наибольшего хроматического числа конечного графа единичных расстояний. Существуют графы единичных расстояний, требующие пяти цветов в любой правильной раскраске, ^[25] и все графы единичных расстояний могут быть раскрашены максимум семью цветами. ^[26]

Отвечая на другой вопрос Пола Эрдёша, для графов единичных расстояний без треугольников возможно потребовать четыре цвета. ^[27]

Число строгих графов единичных расстояний на помеченных вершинах не превышает ^[2] , как выражено с использованием нотации «большое О» и нотации «малое О».${\displaystyle n\geq 4}$ $${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

Определение графа единичных расстояний может быть естественным образом обобщено на любое многомерное евклидово пространство . В трех измерениях графы единичных расстояний точек имеют не более ребер, где — очень медленно растущая функция, связанная с обратной функцией Аккермана . ^[28] Этот результат приводит к аналогичной границе числа ребер трехмерных графов относительного соседства . ^[29] В четырех или более измерениях любой полный двудольный граф является графом единичных расстояний, реализованным путем размещения точек на двух перпендикулярных окружностях с общим центром, поэтому графы единичных расстояний могут быть плотными графами . ^[7] Формулы перечисления для графов единичных расстояний обобщаются на более высокие измерения и показывают, что в измерениях четыре или более число строгих графов единичных расстояний намного больше числа подграфов графов единичных расстояний. ^[2]${\displaystyle n}$${\displaystyle n^{3/2}\beta (n)}$${\displaystyle \бета}$

Любой конечный граф может быть вложен как граф единичных расстояний в достаточно высокой размерности. Некоторым графам могут потребоваться совершенно разные размерности для вложений как нестрогих графов единичных расстояний и как строгих графов единичных расстояний. Например, граф короны вершин может быть вложен в четыре измерения как нестрогий граф единичных расстояний (то есть так, чтобы все его ребра имели единичную длину). Однако для вложения как строгого графа единичных расстояний требуется по крайней мере размерности, так что его ребра будут единственными парами единичных расстояний. ^[30] Размерность, необходимая для реализации любого заданного графа как строгого единичного графа, не превышает удвоенной его максимальной степени. ^[31]${\displaystyle 2n}$${\displaystyle n-2}$

Построение графика единичных расстояний из его точек является важным шагом для других алгоритмов поиска конгруэнтных копий некоторого шаблона в большем наборе точек. Эти алгоритмы используют это построение для поиска позиций кандидатов, где присутствует одно из расстояний в шаблоне, а затем используют другие методы для проверки остальной части шаблона для каждого кандидата. ^[32] Метод Матоушека (1993) может быть применен к этой проблеме, ^[32] давая алгоритм для поиска графика единичных расстояний плоского набора точек во времени , где — медленно растущая функция итерированного логарифма . ^[33]${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$${\displaystyle \log ^{*}}$

NP -сложно — и, более конкретно, полно для экзистенциальной теории действительных чисел — проверить, является ли заданный граф (строгим или нестрогим) графом единичных расстояний на плоскости. ^[34] Также NP-полно определить, имеет ли планарный граф единичных расстояний гамильтонов цикл , даже если все вершины графа имеют известные целочисленные координаты. ^[35]

• Венкатасубраманиан, Суреш, «Проблема 39: Расстояния между множествами точек в R2 и R3», Проект открытых проблем
• Вайсштейн, Эрик В. , «Граф единичных расстояний», MathWorld