Кутова роздільність (теорія графів) — Вікіпедія

Кутова́ розді́льність малюнка графа стосується найгострішого кута, утвореного будь-якими двома ребрами, які зустрічаються в одній вершині малюнка.

Властивості[ред. | ред. код]

Зв'язок зі степенем вершини[ред. | ред. код]

Форман зі співавторами^[1] помітили, що будь-який малюнок графа з ребрами-відрізками з найбільшим степенем d має кутову роздільність, що не перевищує ${\displaystyle 2\pi /d}$ — якщо v є вершиною зі степенем d, то ребра, інцидентні v, розбивають простір навколо вершини v на d клинів зі сумарним кутом ${\displaystyle 2\pi }$, а найменший із цих клинів повинен мати кут, що не перевищує ${\displaystyle 2\pi /d}$. Строгіше, якщо граф є d-регулярним, він повинен мати кутову роздільність, меншу від ${\displaystyle {\frac {\pi }{d-1}}}$, оскільки це найкраща роздільність, яку можна отримати для вершини на опуклій оболонці малюнка.

Зв'язок із розфарбуванням графа[ред. | ред. код]

Як показали Форман зі співавторами ^[1], найбільша можлива кутова роздільність графа G тісно пов'язана із хроматичним числом квадрата графа G² тобто графа з тим самим набором вершин, у якому кожна пара вершин з'єднана ребром, якщо відстань між ними у графі G не перевищує двох. Якщо граф G² можна розфарбувати в ${\displaystyle \chi }$ кольорів, то G можна намалювати з кутовою роздільністю ${\displaystyle \pi /\chi -\epsilon }$ для будь-кого ${\displaystyle \epsilon >0}$, якщо призначити різні кольори вершинам правильного ${\displaystyle \chi }$-кутника і розмістити кожну вершину графа G поруч із вершиною многокутника з тим самим кольором. Використовуючи цю побудову, вони показали, що будь-який граф з найбільшним степенем d має малюнок із кутовою роздільністю, пропорційною1/d². Ця межа близька до точної — вони використовували ймовірнісний метод для доведення існування графів з найбільшим степенем d, всі малюнки яких мають кутову роздільність ${\displaystyle O\left({\frac {\log d}{d^{2}}}\right)}$.

Існування оптимальних малюнків[ред. | ред. код]

Форман зі співавторами^[1] навели приклад, що показує, що існують графи, які не мають малюнків з найбільшою можливою кутовою роздільністю. Навпаки, ці графи мають сімейство малюнків, кутові роздільності яких прямують до деякого обмеженого значення, але не досягають його. Конкретно, вони представили граф із 11 вершинами, який має малюнок із кутовою роздільністю ${\displaystyle \pi /3-\epsilon }$ для будь-кого ${\displaystyle \epsilon >0}$, але не має малюнка з кутовою роздільністю, точно рівною ${\displaystyle \pi /3}$.

Окремі класи графів[ред. | ред. код]

Дерева[ред. | ред. код]

Будь-яке дерево можна намалювати так, щоб ребра виявились рівномірно розподіленими навколо кожної вершини, — властивість, відома як досконала кутова роздільність. Більше того, якщо ребра навколо кожної з вершин можна вільно переставляти, то такий малюнок можливий без перетинів з ребрами завдовжки одиниця або більше, а також весь малюнок міститься у прямокутнику поліноміальної площі. Однак, якщо циклічне впорядкування ребер навколо кожної вершини вже задано як частину умови задачі, отримання кутової роздільності без перетинів може іноді вимагати експоненціальної площі^[2][3].

Зовніпланарні графи[ред. | ред. код]

Досконала кутова роздільність не завжди можлива для зовніпланарних графів, оскільки вершина на опуклій оболонці малюнка зі степенем, більшим від одиниці, не може мати інцидентних їй ребер, рівномірно розподілених навколо вершини. Проте будь-який зовніпланарний граф з найбільшим степенем d має зовніпланарний малюнок з кутовою роздільністю, пропорційною1/d^[4][5].

Планарні графи[ред. | ред. код]

Для планарних графів із максимальним степенем d техніка розфарбовування квадрата графа Формана (зі співавторами)^[1] дає малюнок з кутовою роздільністю, пропорційною 1/d, оскільки квадрат планарного графа повинен мати хроматичне число, пропорційне d. Вегнер висловив 1977 року гіпотезу, що хроматичне число квадрата планарного графа не перевищує ${\displaystyle \max \left(d+5,{\frac {3d}{2}}+1\right)}$ і відомо, що хроматичне число не перевищує ${\displaystyle {\frac {5d}{3}}+O(1)}$^[6][7]. Однак малюнок, побудовнаий за цією технікою, в загальному випадку не планарний.

Для деяких планарних графів оптимальна кутова роздільність планарного малюнка з ребрами у вигляді відрізків дорівнює O(1/d³), де d є степенем графа^[5]. Крім того, такі малюнки можуть вимушено мати дуже довгі ребра, довші, ніж експоненційний множник від найкоротшого ребра малюнка. Маліц і Папакостас^[4] використали теорему про пакування кіл, щоб показати, що будь-який планарний граф з найбільшим степенем d має планарний малюнок, кутова роздільність якого в гіршому випадку є експоненційною функцією від d і яка залежить від числа вершин графа.

Обчислювальна складність[ред. | ред. код]

Задача визначення, чи має граф з найбільшим степенем d малюнок з кутовою роздільністю ${\displaystyle 2\pi /d}$, NP-складна навіть у частковому випадку d=4^[1][8]. Однак для деяких обмежених класів малюнків, зокрема для малюнків дерев, у яких поширення листя до нескінченності дає опукле розбиття площини, як і малюнки планарних графів, у яких кожна обмежена грань є центральносиметричним многокутником, рисунок з оптимальною кутовою роздільністю можна знайти за поліноміальний час^[9][10].

Історія[ред. | ред. код]

Кутову роздільність ввели Форман зі співавторами^[1].

Хоча її спочатку визначено для малюнків графів із прямолінійними ребрами, пізніше автори досліджували кутову роздільність малюнків, на яких ребра є ламаними^[11][12], дугами кіл^[13][2] або сплайнами^[14][15].

Кутова роздільність графа тісно пов'язана з його роздільністю схрещень, тобто, кутами, утвореними схрещеннями на малюнку графа. Зокрема, під час малювання графів із прямими кутами шукають подання, яке забезпечує, щоб усі ці кути були прямими, що є найбільшим можливим кутом перетину^[16].

Примітки[ред. | ред. код]

Література[ред. | ред. код]

Словники та енциклопедії Encyclopædia Britannica Нормативний контроль Freebase: /m/0h7lrcq