ПРО ДОМІНУЮЧУ МНОЖИНУ ДЛЯ 2-КЛУБІВ НА ГРАФАХ ОДИНИЧНИХ КІЛ - Наукові конференції
Головна
UA RU EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

Рік заснування видання - 2011

ПРО ДОМІНУЮЧУ МНОЖИНУ ДЛЯ 2-КЛУБІВ НА ГРАФАХ ОДИНИЧНИХ КІЛ

10.04.2023 18:22

[1. Інформаційні системи і технології]

Автор: Лісіна Ольга Юліївна, кандидат фізико-математичних наук, доцент, Харківський національний університет імені В.М. Каразіна; Лісін Ілля Денисович, Інженерний коледж Самі Шамун, Беєр Шева, Ізраїль


У цій роботі представлений один із проміжних результатів, отриманих у ході роботи з побудови ½-апроксимуючого алгоритму для знаходження максимального 2-клубу в графах одиничних кіл.

Граф одиничних дисків (Unit Disk Graph), який можна визначити як граф перетинів замкнутих дисків однакового (наприклад, одиничного) діаметра, є зручним інструментом моделювання для бездротових мереж, де здатність двох бездротових вузлів обмінюватися даними залежить від того, чи знаходяться вони не більше ніж на одиничній евклідовій відстані один від одного. У той час як багато класичних задач оптимізації на графах, таких як максимальна незалежна множина, мінімальне покриття вершин, розмальовка графа, мінімальна домінуюча множина і мінімальна зв'язна домінуюча множина, залишаються NP-складними навіть при обчисленні на UDG [1], є деякі помітні винятки. Зокрема, завдання про максимальну кліку, у загальному випадку NP-складна, поліноміально вирішувана на UDG. У 1973 р. Річард Альба вперше згадав про науковий інтерес досліджень у своїй роботі про соціометричну кліку [3]. На даний момент проблема вивчена на різних класах графів, таких як інтервальні графи, дводольні графи, планарні графи тощо [5]. Для графів загального виду відомо, що завдання знаходження максимального 2-клубу є NP-складним, а також відомо, що немає наближеного алгоритму знаходження максимального 2-клубу з постійним коефіцієнтом апроксимації. Важливість цієї роботи полягає у розширенні класів спеціальних графів, у яких можна вести пошук 2-клуба. Розробка такого алгоритму може надати нові можливості для аналізу різних мереж, а результат також допоможе краще зрозуміти нещодавно введену концепцію «малих світових мереж» [2]. На даний момент NP-складність задачі про знаходження максимального 2-клубу залишається відкритим питанням. Одне з небагатьох недавніх поступів у напрямку вирішення цієї проблеми, отримане Jeffrey Pattillo, Yiming Wang, Sergiy Butenko [4], полягає в тому, що будь-який 2-клуб на UDG є 3-домінованим.

2-клуб - це природне ослаблення поняття кліки. 2-клубом графа G називається будь-який його подграф, діаметр якого не перевищує 2. Як і задача знаходження максимальної кліки, завдання знаходження максимального 2-клубу на загальних графах є NP-складною і не може бути апроксимована з будь-яким постійним коефіцієнтом апроксимації. Однак для UDG існує поліноміальний алгоритм знаходження максимальної кліки [1], а про складність завдання знаходження максимальної 2-клуби нічого не відомо. Крім того, зважаючи на результат Jeffrey Pattillo та ін. [4] існує тривіальний 1/3-наближений алгоритм знаходження максимального 2-клубу: вершина максимального ступеня графа разом зі своєю околицею дає 2-клуб, число вершин у якому становить не менше 1 /3 від числа вершин у максимальному 2-клубі.

Для цілей, пов'язаних з аналізом маловивченої в даний час структури 2-клубів на UDG був створений програмний комплекс UDGCreate [6], що дозволяє проектувати UDG та дослідити їх характеристики. Система дозволяє моделювати UDG у різних моделях (модель вкладення та еквівалентна їй модель близькості). UDG будується шляхом переміщення вершин вздовж осей, при цьому вершини автоматично з'єднуються ребрами, якщо відстань між ними досить мала.

Одночасно з побудовою графа обчислюються діаметр графа та всі домінуючі множини графа. Останнє особливо важливо при вивченні 2-клубів: відомо, що будь-який 2-клуб на UDG має домінуючу множину з не більше ніж трьох вершин. Існують алгоритми знаходження максимальних 1-домінованих і 2-домінованих 2-клубів відповідно, єдина перешкода в побудові наближеного алгоритму знаходження максимальних 2-клубів - це 3-доміновані 2-клуби. Такі 2-клуби мають досить жорсткі структури, один з них показаний в [4], а за допомогою UDGCreate вдалося побудувати, мабуть, мінімальний за кількістю вершин 3-домінований 2-клуб на 12 вершинах.





Рис. 1. 3-домінований 2-клуб без домінуючих клік


Основним результатом даної роботи є контрприклад до гіпотези про те, що у будь-якого 3-домінованого 2-клубу існує домінуюча множина, що є клікою. За допомогою засобів, наданих UDGCreate, вдалося побудувати граф одиничних кіл, який є 3-домінованим 2-клубом без домінуючої кліки (Рис. 1). Якоюсь мірою, цей результат є негативним: якби гіпотеза про домінуючу кліку була б вірною, то ½-наближений алгоритм для знаходження максимального 2-клубу будувався б досить нескладно, проте жорстка структура єдиного відомого на даний момент 3-домінованого 2-клубу без домінуючої кліки залишає надію на побудову апроксимуючого алгоритму.


Література


1.Clark, B. N., Colbourn, C. J., & Johnson, D. S. (1990). Unit disk graphs.  Discrete Mathematics, 86(1-3), 165-177. 


2.Watts DJ, Strogatz SH. Collective dynamics of 'small-world' networks. Nature. 393 (6684): 440–2.


3.Richard D. Alba (1973) A graph-theoretic definition of a sociometric clique, The Journal of Mathematical Sociology, 3:1, 113-126,  DOI: 10.1080/0022250X.1973.9989826


4.Jeffrey Pattillo, Yiming Wang, Sergiy Butenko, Approximating 2-cliques in unit disk graphs, Discrete Applied Mathematics, Volume 166, 2014, P. 178-187, ISSN 0166-218X


5.Erik van Leeuwen E.J. (2009) Optimization and approximation on systems of geometric objects. 


6.Матеріали конференції «Psychological and Pedagogical Problems of Higher and Secondary Education in Response to Modern Challenges: Theory and Practice»(Kharkiv, May 20–21, 2022)

Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Інші наукові праці даної секції

Конференції

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення