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

Набір кіл одиничного радіуса і відповідний граф.

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

Характеристики

Можливі кілька варіантів визначення графа одиничних кругів, еквівалентних з точністю до вибору коефіцієнта:

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

Властивості

Будь-який породжений підграф графа одиничних кругів є також графом одиничних кругів. Прикладом графа, що не є графом одиничних кругів, є зірка $K_{1,7}$ із центральною вершиною, з'єднаною зі сімома листками — якщо кожен із семи кругів дотикається до центрального круга, якась пара кругів має дотикатися між собою (оскільки контактне число на площині дорівнює 6). Таким чином, граф одиничних кругів не може містити $K_{1,7}$ як породжений підграф.

Застосування

Починаючи з праці Г'юсона і Сена Шаблон:Harvard citation, графи одиничних кругів використовують у інформатиці для моделювання топології бездротових децентралізованих самоорганізовуваних мереж. У цьому додатку вершини з'єднані прямим бездротовим зв'язком без базової станції . Передбачається, що всі вершини однорідні і мають Шаблон:Не перекладено . Розташування антен моделюється точками на евклідовій площині, а область де сигнал може бути отриманий іншою вершиною, моделюється кругом. Якщо всі вершини мають передавачі однакової потужності, ці кола матимуть один і той самий радіус. Випадкові геометричні графи, утворені як графи одиничних кіл із випадковими центрами, можна використовуватиме моделювання фільтрації та інших явищ.

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

Задача про те, чи можна представити абстрактно заданий граф у вигляді графа одиничних кругів є NP-складною (точніше, повною для екзистенційної теорії речових чисел)Шаблон:SfnШаблон:Sfn. Крім того, доведено неможливість за поліноміальний час знайти певні координати одиничних кругів: існують графи одиничних кругів, що вимагають експоненційного числа бітів точності в будь-якому такому поданніШаблон:Sfn.

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

Якщо дана множина вершин утворює підмножину трикутної ґратки, необхідна і достатня умова досконалості графа відомаШаблон:Sfn. Для досконалих графів багато NP-повних задач оптимізації (задача розфарбовування графа, задача про максимальну кліку і задача про незалежну множину) можна розв'язати за поліноміальний час.

Див. також

• Шаблон:Не перекладено, узагальнення графа одиничних кругів, утворює конструкцію в топологічному просторі більшого порядку з одиничних відстаней у метричному просторі.
• Граф одиничних відстаней, утворений з'єднанням точок, розташованих на відстані рівно одиниця, а не на відстані меншій від одиниці (як у графах одиничних кругів).

Посилання

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття