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

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

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

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

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

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

Властивості

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

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

Починаючи з праці Г'юсона і Сена (Huson, Sen, 1995), графи одиничних кругів використовують у інформатиці для моделювання топології бездротових децентралізованих самоорганізовуваних мереж. У цьому додатку вершини з'єднані прямим бездротовим зв'язком без базової станції . Передбачається, що всі вершини однорідні і мають ^[en] . Розташування антен моделюється точками на евклідовій площині, а область де сигнал може бути отриманий іншою вершиною, моделюється кругом. Якщо всі вершини мають передавачі однакової потужності, ці кола матимуть один і той самий радіус. Випадкові геометричні графи, утворені як графи одиничних кіл із випадковими центрами, можна використовуватиме моделювання фільтрації та інших явищ.

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

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

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

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

Див. також

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

Примітки

1. Див., наприклад, працю Даля і Крістенсена (Dall, Christensen, 2002).
2. Breu, Kirkpatrick, 1998.
3. Kang, Müller, 2011.
4. McDiarmid, Mueller, 2011.
5. Marathe et al, 1994.
6. Matsui, 2000.
7. Clark, Colbourn, Johnson, 1990.
8. Raghavan, Spinrad, 2003.
9. Miyamoto, Matsui, 2005.

Посилання

• Heinz Breu, David G. Kirkpatrick. Unit disk graph recognition is NP-hard // Computational Geometry Theory and Applications. — 1998. — Т. 9, вип. 1–2. — С. 3–24.
• Brent N. Clark, Charles J. Colbourn, David S. Johnson. Unit disk graphs // . — 1990. — Т. 86, вип. 1–3. — С. 165–177. — DOI:10.1016/0012-365X(90)90358-O.
• Jesper Dall, Michael Christensen. Random geometric graphs // Phys. Rev. E. — 2002. — Т. 66. — С. 016121. — arXiv:cond-mat/0203026. — DOI:10.1103/PhysRevE.66.016121.
• Mark L. Huson, Arunabha Sen. Military Communications Conference, IEEE MILCOM '95. — 1995. — Т. 2. — С. 647–651. — . — DOI:10.1109/MILCOM.1995.483546.
• Ross J. Kang, Tobias Müller. Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France. — 2011. — С. 308–314.
• Madhav V. Marathe, Heinz Breu, Harry B. Hunt, III, S. S. Ravi, Daniel J. Rosenkrantz. Geometry based heuristics for unit disk graphs. — 1994. — arXiv:math.CO/9409226.
• Tomomi Matsui. Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs // Lecture Notes in Computer Science. — 2000. — Т. 1763. — С. 194–200. — (Lecture Notes in Computer Science). — . — DOI:10.1007/978-3-540-46515-7_16.
• Colin McDiarmid, Tobias, Mueller. Integer realizations of disk and segment graphs. — 2011. — arXiv:1111.2931.
• Yuichiro Miyamoto, Tomomi Matsui. Perfectness and Imperfectness of the kth Power of Lattice Graphs // Lecture Notes in Computer Science. — 2005. — Т. 3521. — С. 233–242. — (Lecture Notes in Computer Science). — . — DOI:10.1007/11496199_26.
• Vijay Raghavan, Jeremy Spinrad. Robust algorithms for restricted domains // Journal of Algorithms. — 2003. — Т. 48, вип. 1. — С. 160–172. — DOI:10.1016/S0196-6774(03)00048-8.