Число перетинів графа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Не плутати з числом схрещень.

Число перетинів графа — найменше число елементів у поданні даного графа як графа перетинів скінченних множин, або, еквівалентно, найменше число клік, необхідних для покриття всіх ребер графа[1][2][3].

Графи перетинів[ред. | ред. код]

Нехай F — сімейство множин (дозволяється повторення множин у F. Тоді граф перетинів F — це неорієнтований граф, що має по вершині для кожного члена F і по ребру між будь-якими двома множинами, що мають непорожній перетин. Будь-який граф можна подати як граф перетинів[4]. Кількість перетинів графа — це найменше число k таке, що існує подання такого типу, для якого об'єднання множин F має k елементів[1]. Задача знаходження подання у вигляді графа перетинів із заданим числом елементів відома як задача знаходження базису графа перетинів[5].

Покриття ребер кліками[ред. | ред. код]

Граф з числом перетинів чотири. Чотири виділені ділянки показують кліки, що покривають усі ребра графа.

Альтернативне визначення числа перетинів графа G — це найменше число клік у G (повних підграфів графа G, які покривають усі ребра G[1][6]. Множина клік з такою властивістю називається покриттям ребер кліками, а тому число перетинів іноді називають числом покриття ребер кліками[7].

Рівність числа перетинів і числа покриття ребер кліками доводиться «прямолінійно». В одному напрямку, припустимо, що G є графом перетинів сімейства F множин, об'єднання U яких має k елементів. Тоді для будь-якого елемента x з U підмножина вершин графа G, відповідних множинам, що містять x, утворюють кліку — будь-які дві вершини цієї підмножини суміжні, оскільки відповідні їм множини мають непорожній перетин, що містить x. Далі — будь-яке ребро в G міститься в одній з таких клік, оскільки ребро відповідає непорожньому перетину, а перетин не порожній, якщо він містить принаймні один елемент U. Таким чином, ребра графа G можуть бути покриті k кліками, по одній для кожного елемента U. В іншому напрямку, якщо граф G можна покрити k кліками, то кожну вершина графа G можна подати множиною клік, що містять вершину[6].

Верхні межі[ред. | ред. код]

Очевидно, що граф з m ребрами має число перетинів, яке не перевищує m — будь-яке ребро утворює кліку, і ці кліки разом покривають усі ребра[8].

Також правильно, що будь-який граф з n вершинами має число перетинів, яке не перевищує n2/4. Строгіше, ребра будь-якого графа з n вершинами можна поділити щонайбільше на n2/4 клік, які є або окремими ребрами, або трикутниками[2][6]. Це узагальнює теорему Мантеля, яка стверджує, що граф без трикутників має не більше n2/4 ребер. Для графів без трикутників оптимальне клікове покриття ребер має кліку для кожного ребра, а тому число перетинів дорівнює числу ребер[2].

Навіть сильніше обмеження можливе, якщо число ребер строго більше від n2/4. Нехай p дорівнює числу пар вершин, не з'єднаних ребрами заданого графа G і нехай t дорівнює числу, для якого t(t − 1) ≤ p < t(t + 1). Тоді число перетинів графа G не перевищує p + t[2][9].

Графи, які є доповненнями розріджених графів, мають невелике число перетинів: число перетинів будь-якого графа G з n вершинами не перевищує 2e2(d + 1)2ln n де e — основа натурального логарифма, d максимальний степінь додаткового графа G[10].

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

Перевірка, що у даного графа G число перетинів не перевищує заданого числа k є NP-повною задачею[5][11][12]. Таким чином, NP-складною задачею є обчислення числа перетинів заданого графа.

Задача обчислення числа перетинів, проте, є фіксовано-параметрично розв'язною[en]. Тобто існує функція f така, що при рівності числа перетинів числу k час обчислення цього числа не перевищує добутку f(k) на поліном від n. Це можна показати, якщо звернути увагу на те, що існує не більше 2k різних закритих околів у графі. Дві вершини, що належать одному і тому ж набору клік, мають одних і тих же сусідів, а тоді граф, утворений вибором однієї вершини для кожного закритого околу, має те саме число перетинів, що й початковий граф. Тому за поліноміальний час вхід можна звести до меншого ядра[en] з максимум 2k вершинами. Застосування алгоритму пошуку з поверненням з експоненційним часом роботи для цього ядра приводить до функції f яка є подвійною експонентою[en] від k[13]. Подвійну експоненційну залежність від k не можна звести до простої експоненційної залежності за допомогою виділення ядра поліноміального розміру, поки поліноміальна ієрархія не зникне[14], і якщо гіпотеза про експоненційний час істинна, подвійної експоненційної залежності не уникнути, будемо ми використовувати виділення ядра чи ні[15].

Ефективніші алгоритми відомі для окремих класів графів. Число перетинів інтервального графа завжди дорівнює числу максимальних клік графа, яке можна обчислити за поліноміальний час[16][17]. Загальніше — кількість перетинів хордальних графів можна обчислити за алгоритмом, який будує порядок виключення вершин графа. На кожному кроці для кожної вершини v утворюємо кліку для вершини v і її сусідів і виключаємо вершину, якщо залишаються ребра, інцидентні v, але ще не покриті кліками[17]. За лінійний час можна знайти число перетинів для графів дуг кола[18]. Однак, хоча ці графи мають лише поліноміальну кількість клік для вибору для покриття, наявності малого числа клік недостатньо для полегшення задачі: існують сімейства графів із поліноміальною кількістю клік, для яких знаходження число перетинів залишається NP-складним[19]. Також за поліноміальний час можна знайти число перетинів для графів, найбільший степінь яких дорівнює 5, але задача є NP-складною для графів із найбільшим степенем 6[20]. На планарних графах точне обчислення числа перетинів залишається NP-складним, але воно має схему наближення до поліноміального часу, засновану на техніці Бейкер[21].

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

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

  1. ↑ а б в Gross, Yellen та 2006, с440.
  2. ↑ а б в г Roberts, 1985, с. 93–109.
  3. ↑ В. П. Козырев, С. В. Юшманов. Представления графов и сетей (кодирование, укладки и вложения) // Итоги науки и техники. : сер. Теор. вероятн. Мат. стат. Теор. кибернет.. — М. : ВИНИТИ, 1990. — Т. 27. — С. 148. — DOI:10.1007/BF01097528.
  4. ↑ Marczewski, 1945, с. 303–307.
  5. ↑ а б Гэри, Джонсон, 1982, с. 256, Задача ТГ59.
  6. ↑ а б в Erdős, Goodman, Pósa, 1966, с. 106–112.
  7. ↑ Michael, Quint, 2006, с. 1309–1313.
  8. ↑ Balakrishnan, 1997, с. 40.
  9. ↑ Lovász, 1968, с. 231–236.
  10. ↑ Alon, 1986, с. 201–206.
  11. ↑ Orlin, 1977, с. 406–424.
  12. ↑ Kou, Stockmeyer, Wong, 1978, с. 135–139.
  13. ↑ Gramm, Guo, Hüffner, Niedermeier, 2009, с. 2–15.
  14. ↑ Cygan, Kratsch, Pilipczuk, Pilipczuk, Wahlström, 2012, с. 254–265.
  15. ↑ Cygan, Pilipczuk, Pilipczuk, 2013.
  16. ↑ Opsut, Roberts, 1981, с. 479–492.
  17. ↑ а б Scheinerman, Trenk, 1999, с. 341–351.
  18. ↑ Hsu, Wen Lian; Tsai, Kuo-Hui (1991), Linear time algorithms on circular-arc graphs, Information Processing Letters, 40 (3): 123—129, doi:10.1016/0020-0190(91)90165-E, MR 1143909
  19. ↑ Rosgen, Bill; Stewart, Lorna (2007), Complexity results on graphs with few cliques, Discrete Mathematics & Theoretical Computer Science, 9 (1): 127—135, doi:10.46298/dmtcs.387, MR 2335890
  20. ↑ Hoover, D. N. (1992), Complexity of graph covering problems for graphs of low degree, Journal of Combinatorial Mathematics and Combinatorial Computing, 11: 187—208, MR 1160076
  21. ↑ Blanchette, Mathieu; Kim, Ethan; Vetta, Adrian (2012), Clique cover on sparse networks, у Bader, David A.; Mutzel, Petra (ред.), Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, ALENEX 2012, The Westin Miyako, Kyoto, Japan, January 16, 2012, Society for Industrial and Applied Mathematics, с. 93—102, doi:10.1137/1.9781611972924.10

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

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Число_перетинів_графа&oldid=41990049