Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Не плутати з числом схрещень Число перетинів графа найменше число елементів у поданні даного графа як графа перетинів ск

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

Число перетинів графа
Не плутати з числом схрещень.

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

Графи перетинів

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

Покриття ребер кліками

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

Альтернативне визначення числа перетинів графа 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-складним, але воно має схему наближення до поліноміального часу, засновану на техніці Бейкер.

Див. також

Примітки

  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, , 40 (3): 123—129, doi:10.1016/0020-0190(91)90165-E, MR 1143909
  19. Rosgen, Bill; (2007), Complexity results on graphs with few cliques, , 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.; (ред.), 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. — .
  • Fred S. Roberts. Applications of edge coverings by cliques // Discrete Applied Mathematics. — 1985. — Т. 10, вип. 1. — С. 93—109. — DOI:10.1016/0166-218X(85)90061-7.
  • E. . 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:10.4153/CJM-1966-014-3.
  • T. S. Michael, Thomas Quint. Sphericity, cubicity, and edge clique covers of graphs // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 8. — DOI:10.1016/j.dam.2006.01.004.
  • V. K. Balakrishnan. Schaum's outline of theory and problems of graph theory. — McGraw-Hill Professional, 1997. — .
  • 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 // . — 1986. — Т. 6, вип. 3. — DOI:10.1007/bf02579381.
  • J. B. Orlin. Contentment in graph theory: covering graphs with cliques // Proc. Kon. Ned. Acad. Wet.. — 1977. — Т. 80. — С. 406—424. — DOI:10.1016/1385-7258(77)90055-5. Як процитиовано в Робертса (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:10.1145/359340.359346.
  • 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:10.1145/1412228.1412236.
  • 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) — . — DOI:10.1007/978-3-642-31594-7_22.
  • 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 // . — 1999. — Т. 15, вип. 3. — DOI:10.1007/s003730050068.
  • М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. — М. : «Мир», 1982.

Посилання

  • Weisstein, Eric W. Число перетинів(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Ne plutati z chislom shreshen Chislo peretiniv grafa najmenshe chislo elementiv u podanni danogo grafa yak grafa peretiniv skinchennih mnozhin abo ekvivalentno najmenshe chislo klik neobhidnih dlya pokrittya vsih reber grafa Grafi peretinivNehaj F simejstvo mnozhin dozvolyayetsya povtorennya mnozhin u F Todi graf peretiniv F ce neoriyentovanij graf sho maye po vershini dlya kozhnogo chlena F i po rebru mizh bud yakimi dvoma mnozhinami sho mayut neporozhnij peretin Bud yakij graf mozhna podati yak graf peretiniv Kilkist peretiniv grafa ce najmenshe chislo k take sho isnuye podannya takogo tipu dlya yakogo ob yednannya mnozhin F maye k elementiv Zadacha znahodzhennya podannya u viglyadi grafa peretiniv iz zadanim chislom elementiv vidoma yak zadacha znahodzhennya bazisu grafa peretiniv Pokrittya reber klikamiGraf z chislom peretiniv chotiri Chotiri vidileni dilyanki pokazuyut kliki sho pokrivayut usi rebra grafa Alternativne viznachennya chisla peretiniv grafa G ce najmenshe chislo klik u G povnih pidgrafiv grafa G yaki pokrivayut usi rebra G Mnozhina klik z takoyu vlastivistyu nazivayetsya pokrittyam reber klikami a tomu chislo peretiniv inodi nazivayut chislom pokrittya reber klikami Rivnist chisla peretiniv i chisla pokrittya reber klikami dovoditsya pryamolinijno V odnomu napryamku pripustimo sho G ye grafom peretiniv simejstva F mnozhin ob yednannya U yakih maye k elementiv Todi dlya bud yakogo elementa x z U pidmnozhina vershin grafa G vidpovidnih mnozhinam sho mistyat x utvoryuyut kliku bud yaki dvi vershini ciyeyi pidmnozhini sumizhni oskilki vidpovidni yim mnozhini mayut neporozhnij peretin sho mistit x Dali bud yake rebro v G mistitsya v odnij z takih klik oskilki rebro vidpovidaye neporozhnomu peretinu a peretin ne porozhnij yaksho vin mistit prinajmni odin element U Takim chinom rebra grafa G mozhut buti pokriti k klikami po odnij dlya kozhnogo elementa U V inshomu napryamku yaksho graf G mozhna pokriti k klikami to kozhnu vershina grafa G mozhna podati mnozhinoyu klik sho mistyat vershinu Verhni mezhiOchevidno sho graf z m rebrami maye chislo peretiniv yake ne perevishuye m bud yake rebro utvoryuye kliku i ci kliki razom pokrivayut usi rebra Takozh pravilno sho bud yakij graf z n vershinami maye chislo peretiniv yake ne perevishuye n2 4 Strogishe rebra bud yakogo grafa z n vershinami mozhna podiliti shonajbilshe na n2 4 klik yaki ye abo okremimi rebrami abo trikutnikami Ce uzagalnyuye teoremu Mantelya yaka stverdzhuye sho graf bez trikutnikiv maye ne bilshe n2 4 reber Dlya grafiv bez trikutnikiv optimalne klikove pokrittya reber maye kliku dlya kozhnogo rebra a tomu chislo peretiniv dorivnyuye chislu reber Navit silnishe obmezhennya mozhlive yaksho chislo reber strogo bilshe vid n2 4 Nehaj p dorivnyuye chislu par vershin ne z yednanih rebrami zadanogo grafa G i nehaj t dorivnyuye chislu dlya yakogo t t 1 p lt t t 1 Todi chislo peretiniv grafa G ne perevishuye p t Grafi yaki ye dopovnennyami rozridzhenih grafiv mayut nevelike chislo peretiniv chislo peretiniv bud yakogo grafa G z n vershinami ne perevishuye 2e2 d 1 2ln n de e osnova naturalnogo logarifma d maksimalnij stepin dodatkovogo grafa G Obchislyuvalna skladnistPerevirka sho u danogo grafa G chislo peretiniv ne perevishuye zadanogo chisla k ye NP povnoyu zadacheyu Takim chinom NP skladnoyu zadacheyu ye obchislennya chisla peretiniv zadanogo grafa Zadacha obchislennya chisla peretiniv prote ye en Tobto isnuye funkciya f taka sho pri rivnosti chisla peretiniv chislu k chas obchislennya cogo chisla ne perevishuye dobutku f k na polinom vid n Ce mozhna pokazati yaksho zvernuti uvagu na te sho isnuye ne bilshe 2k riznih zakritih okoliv u grafi Dvi vershini sho nalezhat odnomu i tomu zh naboru klik mayut odnih i tih zhe susidiv a todi graf utvorenij viborom odniyeyi vershini dlya kozhnogo zakritogo okolu maye te same chislo peretiniv sho j pochatkovij graf Tomu za polinomialnij chas vhid mozhna zvesti do menshogo en z maksimum 2k vershinami Zastosuvannya algoritmu poshuku z povernennyam z eksponencijnim chasom roboti dlya cogo yadra privodit do funkciyi f yaka ye en vid k Podvijnu eksponencijnu zalezhnist vid k ne mozhna zvesti do prostoyi eksponencijnoyi zalezhnosti za dopomogoyu vidilennya yadra polinomialnogo rozmiru poki polinomialna iyerarhiya ne znikne i yaksho istinna podvijnoyi eksponencijnoyi zalezhnosti ne uniknuti budemo mi vikoristovuvati vidilennya yadra chi ni Efektivnishi algoritmi vidomi dlya okremih klasiv grafiv Chislo peretiniv intervalnogo grafa zavzhdi dorivnyuye chislu maksimalnih klik grafa yake mozhna obchisliti za polinomialnij chas Zagalnishe kilkist peretiniv hordalnih grafiv mozhna obchisliti za algoritmom yakij buduye poryadok viklyuchennya vershin grafa Na kozhnomu kroci dlya kozhnoyi vershini v utvoryuyemo kliku dlya vershini v i yiyi susidiv i viklyuchayemo vershinu yaksho zalishayutsya rebra incidentni v ale she ne pokriti klikami Za linijnij chas mozhna znajti chislo peretiniv dlya grafiv dug kola Odnak hocha ci grafi mayut lishe polinomialnu kilkist klik dlya viboru dlya pokrittya nayavnosti malogo chisla klik nedostatno dlya polegshennya zadachi isnuyut simejstva grafiv iz polinomialnoyu kilkistyu klik dlya yakih znahodzhennya chislo peretiniv zalishayetsya NP skladnim Takozh za polinomialnij chas mozhna znajti chislo peretiniv dlya grafiv najbilshij stepin yakih dorivnyuye 5 ale zadacha ye NP skladnoyu dlya grafiv iz najbilshim stepenem 6 Na planarnih grafah tochne obchislennya chisla peretiniv zalishayetsya NP skladnim ale vono maye shemu nablizhennya do polinomialnogo chasu zasnovanu na tehnici Bejker Div takozhDvochastkova rozmirnist najmenshe chislo biklik neobhidnih dlya pokrittya reber grafa Zadacha pro klikove pokrittya NP povna zadacha znahodzhennya maloyi kilkosti klik sho pokrivayut usi vershini grafaPrimitkiGross Yellen 2006 ta s440 Roberts 1985 s 93 109 V P Kozyrev S V Yushmanov Predstavleniya grafov i setej kodirovanie ukladki i vlozheniya Itogi nauki i tehniki ser Teor veroyatn Mat stat Teor kibernet M VINITI 1990 T 27 S 148 DOI 10 1007 BF01097528 Marczewski 1945 s 303 307 Geri Dzhonson 1982 s 256 Zadacha TG59 Erdos Goodman Posa 1966 s 106 112 Michael Quint 2006 s 1309 1313 Balakrishnan 1997 s 40 Lovasz 1968 s 231 236 Alon 1986 s 201 206 Orlin 1977 s 406 424 Kou Stockmeyer Wong 1978 s 135 139 Gramm Guo Huffner Niedermeier 2009 s 2 15 Cygan Kratsch Pilipczuk Pilipczuk Wahlstrom 2012 s 254 265 Cygan Pilipczuk Pilipczuk 2013 Opsut Roberts 1981 s 479 492 Scheinerman Trenk 1999 s 341 351 Hsu Wen Lian Tsai Kuo Hui 1991 Linear time algorithms on circular arc graphs 40 3 123 129 doi 10 1016 0020 0190 91 90165 E MR 1143909 Rosgen Bill 2007 Complexity results on graphs with few cliques 9 1 127 135 doi 10 46298 dmtcs 387 MR 2335890 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 u Bader David A red Proceedings of the 14th Meeting on Algorithm Engineering amp Experiments ALENEX 2012 The Westin Miyako Kyoto Japan January 16 2012 Society for Industrial and Applied Mathematics s 93 102 doi 10 1137 1 9781611972924 10LiteraturaJonathan L Gross Jay Yellen Graph Theory and its Applications CRC Press 2006 S 440 ISBN 978 1 58488 505 4 Fred S Roberts Applications of edge coverings by cliques Discrete Applied Mathematics 1985 T 10 vip 1 S 93 109 DOI 10 1016 0166 218X 85 90061 7 E Sur deux proprietes des classes d ensembles Fund Math 1945 T 33 S 303 307 Paul Erdos A W Goodman Lajos Posa The representation of a graph by set intersections Canadian Journal of Mathematics 1966 T 18 vip 1 DOI 10 4153 CJM 1966 014 3 T S Michael Thomas Quint Sphericity cubicity and edge clique covers of graphs Discrete Applied Mathematics 2006 T 154 vip 8 DOI 10 1016 j dam 2006 01 004 V K Balakrishnan Schaum s outline of theory and problems of graph theory McGraw Hill Professional 1997 ISBN 978 0 07 005489 9 Laszlo Lovasz Proceedings of the Colloquium held at Tihany Hungary 1966 P Erdos G Katona Academic Press 1968 Kak citirovano u Robertsa Roberts 1985 Noga Alon Covering graphs by the minimum number of equivalence relations 1986 T 6 vip 3 DOI 10 1007 bf02579381 J B Orlin Contentment in graph theory covering graphs with cliques Proc Kon Ned Acad Wet 1977 T 80 S 406 424 DOI 10 1016 1385 7258 77 90055 5 Yak procitiovano v Robertsa 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 T 21 vip 2 DOI 10 1145 359340 359346 Jens Gramm Jiong Guo Falk Huffner Rolf Niedermeier Data reduction and exact algorithms for clique cover Journal of Experimental Algorithmics 2009 T 13 vip 2 DOI 10 1145 1412228 1412236 Marek Cygan Stefan Kratsch Marcin Pilipczuk Michal Pilipczuk Magnus Wahlstrom 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 T 7391 Lecture Notes in Computer Science ISBN 978 3 642 31593 0 DOI 10 1007 978 3 642 31594 7 22 Marek Cygan Marcin Pilipczuk Michal 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 Yak procitiovano v Robertsa Roberts 1985 Edward R Scheinerman Ann N Trenk On the fractional intersection number of a graph 1999 T 15 vip 3 DOI 10 1007 s003730050068 M Geri D Dzhonson Vychislitelnye mashiny i trudnoreshaemye zadachi M Mir 1982 PosilannyaWeisstein Eric W Chislo peretiniv angl na sajti Wolfram MathWorld

Дата публікації:
Топ