Число перетинів графа — найменше число елементів у поданні даного графа як графа перетинів скінченних множин, або, еквівалентно, найменше число клік, необхідних для покриття всіх ребер графа.
Графи перетинів ред.
Нехай F — сімейство множин (дозволяється повторення множин в F. Тоді граф перетинів F — це неорієнтований граф, що має по вершині для кожного члена F і по ребру між будь-якими двома множинами, що мають непорожній перетин. Будь-який граф можна подати як граф перетинів. Кількість перетинів графа — це найменше число k таке, що існує подання такого типу, для якого об'єднання множин F має k елементів. Задача знаходження подання у вигляді графа перетинів із заданим числом елементів відома як задача знаходження базису графа перетинів.
Покриття ребер кліками ред.
Альтернативне визначення числа перетинів графа G — це найменше число клік у G (повних підграфів графа G, які покривають усі ребра G. Множина клік з такою властивістю називається покриттям ребер кліками, а тому число перетинів іноді називають числом покриття ребер кліками.
Рівність числа перетинів і числа покриття ребер кліками доводиться «прямолінійно». В одному напрямку, припустимо, що G є графом перетинів сімейства F множин, об'єднання U яких має k елементів. Тоді для будь-якого елемента x з U підмножина вершин графа G, відповідних множинам, що містять x, утворюють кліку — будь-які дві вершини цієї підмножини суміжні, оскільки відповідні їм множини мають непорожній перетин, що містить x. Далі — будь-яке ребро в G міститься в одній з таких клік, оскільки ребро відповідає непорожньому перетину, а перетин не порожній, якщо він містить принаймні один елемент U. Таким чином, ребра графа G можуть бути покриті k кліками, по одній для кожного елемента U. В іншому напрямку, якщо граф G можна покрити k кліками, то кожну вершина графа G можна подати множиною клік, що містять вершину.
Верхні межі ред.
Очевидно, що граф з m ребрами має число перетинів, яке не перевищує m — будь-яке ребро утворює кліку, і ці кліки разом покривають усі ребра.
Також правильно, що будь-який граф з n вершинами має число перетинів, яке не перевищує n2/4. Строгіше, ребра будь-якого графа з n вершинами можна поділити щонайбільше на n2/4 клік, які є або окремими ребрами, або трикутниками. Це узагальнює теорему Мантеля, яка стверджує, що граф без трикутників має не більше n2/4 ребер. Для графів без трикутників оптимальне клікове покриття ребер має кліку для кожного ребра, а тому число перетинів дорівнює числу ребер.
Навіть сильніше обмеження можливе, якщо число ребер строго більше від n2/4. Нехай p дорівнює числу пар вершин, не з'єднаних ребрами заданого графа G і нехай t дорівнює числу, для якого t(t − 1) ≤ p < t(t + 1). Тоді число перетинів графа G не перевищує p + t.
Графи, які є доповненнями розріджених графів, мають невелике число перетинів: число перетинів будь-якого графа G з n вершинами не перевищує 2e2(d + 1)2ln n де e — основа натурального логарифма, d максимальний степінь додаткового графа G.
Обчислювальна складність ред.
Перевірка, що у даного графа G число перетинів не перевищує заданого числа k є NP-повною задачею. Таким чином, NP-складною задачею є обчислення числа перетинів заданого графа.
Задача обчислення числа перетинів, проте, є фіксовано-параметрично розв'язною[en]. Тобто існує функція f така, що при рівності числа перетинів числу k час обчислення цього числа не перевищує добутку f(k) на поліном від n. Це можна показати, якщо звернути увагу на те, що існує не більше 2k різних закритих околів у графі. Дві вершини, що належать одному і тому ж набору клік, мають одних і тих же сусідів, а тоді граф, утворений вибором однієї вершини для кожного закритого околу, має те саме число перетинів, що й початковий граф. Тому за поліноміальний час вхід можна звести до меншого ядра[en] з максимум 2k вершинами. Застосування алгоритму пошуку з поверненням з експоненційним часом роботи для цього ядра приводить до функції f яка є подвійною експонентою[en] від k. Подвійну експоненційну залежність від k не можна звести до простої експоненційної залежності за допомогою виділення ядра поліноміального розміру, поки поліноміальна ієрархія не зникне, і якщо гіпотеза про експоненційний час істинна, подвійної експонеційної залежності не уникнути, будемо ми використовувати виділення ядра чи ні.
Ефективніші алгоритми відомі для окремих класів графів. Число перетинів інтервального графа завжди дорівнює числу максимальних клік графа, яке можна обчислити за поліноміальний час. Загальніше — кількість перетинів хордальних графів можна обчислити за алгоритмом, який будує порядок виключення вершин графа. На кожному кроці для кожної вершини v утворюємо кліку для вершини v і її сусідів і виключаємо вершину, якщо залишаються ребра, інцидентні v але ще не покриті кліками. За лінійний час можна знайти число перетинів для графів дуг кола. Однак, хоча ці графи мають лише поліноміальну кількість клік для вибору для покриття, наявності малого числа клік недостатньо для полегшення задачі: існують сімейства графів із поліноміальною кількістю клік, для яких знаходження число перетинів залишається NP-складним . Також за поліноміальний час можна знайти число перетинів для графів, найбільший степінь яких дорівнює 5, але задача є NP-складною для графів із найбільшим степенем 6 . На планарних графах точне обчислення числа перетинів залишається NP-складним, але воно має схему наближення до поліноміального часу, засновану на техніці Бейкер.
Див. також ред.
- Двочасткова розмірність — найменше число біклік, необхідних для покриття ребер графа
- Задача про клікове покриття — NP-повна задача знаходження малої кількості клік, що покривають усі вершини графа
Примітки ред.
- ↑ Gross, Yellen та 2006, с440.
- ↑ Roberts, 1985, с. 93–109.
- В. П. Козырев, С. В. Юшманов. Представления графов и сетей (кодирование, укладки и вложения) // Итоги науки и техники. : сер. Теор. вероятн. Мат. стат. Теор. кибернет.. — М. : ВИНИТИ, 1990. — Т. 27. — С. 148. — DOI: .
- Marczewski, 1945, с. 303–307.
- ↑ Гэри, Джонсон, 1982, с. 256, Задача ТГ59.
- ↑ Erdős, Goodman, Pósa, 1966, с. 106–112.
- Michael, Quint, 2006, с. 1309–1313.
- Balakrishnan, 1997, с. 40.
- Lovász, 1968, с. 231–236.
- Alon, 1986, с. 201–206.
- Orlin, 1977, с. 406–424.
- Kou, Stockmeyer, Wong, 1978, с. 135–139.
- Gramm, Guo, Hüffner, Niedermeier, 2009, с. 2–15.
- Cygan, Kratsch, Pilipczuk, Pilipczuk, Wahlström, 2012, с. 254–265.
- Cygan, Pilipczuk, Pilipczuk, 2013.
- Opsut, Roberts, 1981, с. 479–492.
- ↑ Scheinerman, Trenk, 1999, с. 341–351.
- Hsu, Wen Lian; Tsai, Kuo-Hui (1991). Linear time algorithms on circular-arc graphs. Information Processing Letters 40 (3): 123–129. MR 1143909. doi:10.1016/0020-0190(91)90165-E.
- Rosgen, Bill; Stewart, Lorna (2007). Complexity results on graphs with few cliques. Discrete Mathematics & Theoretical Computer Science 9 (1): 127–135. MR 2335890. doi:10.46298/dmtcs.387.
- 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.
- 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.
Література ред.
- Jonathan L. Gross, Jay Yellen. Graph Theory and its Applications. — CRC Press, 2006. — С. 440. — ISBN 978-1-58488-505-4.
- Fred S. Roberts. Applications of edge coverings by cliques // Discrete Applied Mathematics. — 1985. — Т. 10, вип. 1. — С. 93—109. — DOI: .
- E. Szpilrajn-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Math.. — 1945. — Т. 33. — С. 303—307.
- Paul Erdős, A. W. Goodman, Lajos Pósa. The representation of a graph by set intersections // Canadian Journal of Mathematics. — 1966. — Т. 18, вип. 1. — DOI: .
- T. S. Michael, Thomas Quint. Sphericity, cubicity, and edge clique covers of graphs // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 8. — DOI: .
- V. K. Balakrishnan. Schaum's outline of theory and problems of graph theory. — McGraw-Hill Professional, 1997. — ISBN 978-0-07-005489-9.
- László Lovász. Proceedings of the Colloquium held at Tihany, Hungary, 1966 / P. Erdős, G. Katona. — Academic Press, 1968. Как цитировано у Робертса (Roberts, (1985))
- Noga Alon. Covering graphs by the minimum number of equivalence relations // Combinatorica. — 1986. — Т. 6, вип. 3. — DOI: .
- J. B. Orlin. Contentment in graph theory: covering graphs with cliques // Proc. Kon. Ned. Acad. Wet.. — 1977. — Т. 80. — С. 406—424. — DOI: . Як процитиовано в Робертса (Roberts, (1985))
- L. T. Kou, L. J. Stockmeyer, C. K. Wong. Covering edges by cliques with regard to keyword conflicts and intersection graphs // Communications of the ACM. — 1978. — Т. 21, вип. 2. — DOI: .
- Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier. Data reduction and exact algorithms for clique cover // Journal of Experimental Algorithmics. — 2009. — Т. 13, вип. 2. — DOI: .
- Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, Magnus Wahlström. Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I / Artur Czumaj, Kurt Mehlhorn, Andrew Pitt, Roger Wattenhofer. — 2012. — Т. 7391. — (Lecture Notes in Computer Science) — ISBN 978-3-642-31593-0. — DOI:
- Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk. Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013). — 2013.
- R. J. Opsut, F. S. Roberts. The Theory and Applications of Graphs / G. Chartrand, Y. Alavi, D. L. Goldsmith, L. Lesniak-Foster, D. R. Lick. — New York : Wiley, 1981. Як процитиовано в Робертса (Roberts, (1985))
- Edward R. Scheinerman, Ann N. Trenk. On the fractional intersection number of a graph // Graphs and Combinatorics. — 1999. — Т. 15, вип. 3. — DOI: .
- М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — М. : «Мир», 1982.
Посилання ред.
- Weisstein, Eric W. Число перетинів(англ.) на сайті Wolfram MathWorld.