Граф одиничних відстаней

Граф Петерсена є графом одиничних відстаней: його можна зобразити на площі так, що кожне ребро буде одиничної довжини.

Графом одиничних відстаней у теорії графів називається граф, утворений точками на евклідовій площині, у якому ребрами з'єднані кожні дві вершини, відстань між якими дорівнює точно одиниці. Ребра графів одиничних відстаней іноді перетинаються, тож графи одиничних відстаней не завжди планарні. Граф одиничних відстаней без перетинів називається сірниковим графом.

Проблема Нельсона — Ердеша — Гадвігера стосується хроматичного числа графів одиничних відстаней. Відомо, що існують графи одиничних відстаней, що вимагають 4 кольори для правильного розфарбування і що всі такі графи можна розфарбувати не більш ніж у 7 кольорів. Інше важливе відкрите питання стосовно графів одиничних відстаней звучить так: «скільки ребер може мати такий граф відносно числа вершин?».

Приклади

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

Граф Петерсена

Інше подання графу Петерсена

Графами одиничних відстаней є такі графи:

• Будь-який цикл
• Будь-яка решітка
• Граф гіперкуба
• Будь-яка зірка
• Граф Петерсена
• Граф Хівуда Шаблон:Harv
• Колесо W₇
• Веретено Мозера, найменший граф одиничних відстаней з хроматичним числом 4.

Графи зірки S₃, S₄, S₅ и S₆.

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

Малюнок з одиничними відстанями графу Мебіуса — Кантора, в якому деякі несуміжні ребра теж перебувають на відстані одиниці.

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

Згідно з цим визначенням узагальнені графи Петерсена є графами одиничних відстаней Шаблон:Harv. Щоб розрізняти ці два визначення введемо поняття строгого графу одиничних відстаней. У строгому графі одиничних відстаней відстань між будь-якими несуміжними вершинами повинна бути відмінною від одиниціШаблон:Harv.

Граф, що утворений видаленням однієї шпиці з колеса W₇, є підграфом одиничних відстаней, але не строгим графом одиничних відстанейШаблон:Harv.

Підрахунок одиничних відстаней

Пал Ердеш Шаблон:Harv запропонував завдання оцінки серед множини з n точок кількості пар, що перебувають на відстані одиниці. У термінах теорії графів питання полягає в оцінці щільності графу одиничних відстаней.

Граф гіперкуба дає нижню межу кількості одиничних відстаней, пропорційну $n\log n$. Розглядаючи точки квадратної решітки з ретельно обраною відстанню, Ердеш знайшов поліпшену нижню межу

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

і запропонував премію в 500 дол. за з'ясування — чи позначається максимальне число одиничних відстаней функцією того ж виду Шаблон:Harv. Найкраща відома межа, згідно зі Шаблон:Не перекладено, Ендре Семереді і Вільямом Троттером Шаблон:Harv, пропорційна

$n^{4/3};$.

Цю межу можна розглядати як число влучень точок на одиничне коло і вона тісно пов'язана з теоремою Семереді — Троттера про інцидентність точок і прямих.

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

Для будь-якого алгебраїчного числа A можна знайти граф одиничних відстаней G, в якому деякі пари вершин перебувають на відстані A в усіх поданнях з одиничними відстанями G Шаблон:Harv Шаблон:Harv. Цей результат передбачає кінцеву версію Шаблон:Не перекладено для будь-яких двох точок p і q, що перебувають на відстані A, існує кінцевий жорсткий граф одиничних відстаней, що містить p і q такий, що будь-яке перетворення площини, яке зберігає одиночні відстані в цьому графові, зберігає водночас і відстань між p і q Шаблон:Harv. Повна теорема Бекмана — Куорлса стверджує, що будь-яке перетворення евклідової площини (або простору більшої розмірності), що зберігає одиничні відстані повинне бути ізометричним. Таким чином, для нескінченних графів одиничних відстаней, вершинами яких є всі точки на площині, будь-який автоморфізм графів повинен бути ізометричним Шаблон:Harv.

Узагальнення на більші розмірності

Визначення графу одиничних відстаней можна природним чином узагальнити на будь-яку розмірність евклідового простору. Будь-який граф можна вкласти у вигляді набору точок у простір досить високої розмірності. Маехара і Редль Шаблон:Harv показали, що розмірність, необхідну для вкладення графу, можна обмежити подвоєнням його максимального ступеню.

Необхідна для вкладення графу розмірність, при якій всі ребра матимуть одиничну довжину, і розмірність вкладення, при якій ребра будуть з'єднувати саме ті точки, між якими відстань одиниця, можуть істотно відрізнятися. Корону з 2n вершинами можна вкласти в чотиривимірний простір так, що всі її ребра будуть мати одиничну відстань, але потрібно розмірність щонайменше n − 2, щоб вкласти її так, щоб не було пар вершин, які перебувають на відстані одиниці і водночас не з'єднані ребром Шаблон:Harv.

Обчислювальна складність

NP-складною задачею, точніше повною задачею для Шаблон:Не перекладено називається задача перевірки, чи є певний граф просто графом одиничних відстаней, або ж він є строгим графом одиничних відстанейШаблон:Harv.

Див. також

• Граф одиничних кругів

Література

• Шаблон:Книга.
• Шаблон:Книга.

• Шаблон:Книга Як цитовано в Шаблон:Harvnb.
• Шаблон:Стаття.
• Шаблон:Книга.
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Книга.
• Шаблон:Книга.
• Шаблон:Стаття.
• Шаблон:Книга.

Посилання

• Шаблон:Citation.
• Шаблон:Mathworld