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

У теорії графів ві льний від t біклі к граф граф у якому немає повних двочасткових графів із 2t вершинами Kt t як підгра

Вільний від біклік граф

Вільний від біклік граф

У теорії графів ві́льний від t-біклі́к граф — граф, у якому немає повних двочасткових графів із 2t вершинами Kt,t як підграфів. Сімейство графів є вільним від біклік, якщо існує число t таке, що всі графи в сімействі вільні від t-біклік. Сімейства вільних від біциклів графів утворюють один із найзагальніших типів сімейств розріджених графів. Вони виникають у задачах інцидентності в комбінаторній геометрії, а також використовуються в [en].

Властивості

Розрідженість

За теоремою Коварі — Сос — Турана, будь-який вільний від t-біциклів граф із n вершинами має O(n2 − 1/t) ребер, тобто, граф істотно рідкший, ніж щільний граф. З іншого боку, якщо сімейство графів визначене забороненими підграфами або замкнуте відносно операції взяття підграфа і не включає щільних графів довільно великого розміру, воно має бути вільним від t-біклік для деякого t, інакше, сімейство має включати довільно великі щільні повні двочасткові графи.

Щодо нижньої межі Ердеш, Хайнал і Муун висловили припущення, що будь-який максимальний вільний від t-біклік двочастковий граф (до якого не можна додати ребро без створення t-бікліки) має принаймні (t − 1)(n + m − t + 1) ребер, де n та m — число вершин у кожній частці графа.

Зв'язок з іншими типами сімейств розріджених графів

Граф із виродженням d є обов'язково вільним від (d + 1)-біклік. Крім того, сімейство вільних від бікліків графів має бути ніде не щільним, що означає, що для будь-якого числа k існує граф, який не є k-неглибоким мінором будь-якого графа зі сімейства. Зокрема, якщо існує граф з n вершинами, який не є 1-неглибокими мінором, то сімейство має бути вільним від n-біклік, оскільки всі графи з n вершинами є 1-неглибокими мінорами графа Kn,n. Отже, вільні від біклік сімейства графів уніфікують два з найзагальніших класів розріджених графів.

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

Дискретна геометрія

У комбінаторній геометрії багато типів графів інцидентності завідомо вільні від біклік. Наприклад, граф інцидентності скінченної множини точок і прямих на евклідовій площині завідомо не містить підграфа K2,2.

Параметризована складність

Вільні від біклік графи використовують у теорії [en] для розробки алгоритмів, ефективних для розріджених графів із досить малими вхідними параметрами. Зокрема, пошук домінівної множини розміром k на вільних від t-біклік графах є фіксовано-параметризовано розв'язною задачею, якщо використати параметр k + t, навіть попри те, що існують вагомі підстави, що це неможливо, якщо використовувати тільки параметр k без t. Ті ж результати істинні для багатьох варіантів задачі про домінівну множину. Перевірка, чи має домінівна множина розмір не більше k можна також перетворити на іншу перевірку з тією ж параметризацією застосуванням низки вставок і видалень вершин, зберігаючи властивість домінування.

Примітки

  1. Kővári, T. Sós, Turán, 1954. Ця праця розглядає число ребер вільних від біклік графів, але стандартне застосування ймовірнісного методу переносить ті самі межі на довільні графи.
  2. Erdős, Hajnal, Moon, 1964.
  3. Erdős, Hajnal, Moon, 1964, с. 1107–1110.
  4. Telle, Villanger, 2012, с. 802–812.
  5. Kaplan, Matoušek, Sharir, 2012, с. 499–517.
  6. Lokshtanov, Mouawad, Panolan, Ramanujan, Saurabh, 2015, с. 506–517.

Література

  • T. Kővári, V. T. Sós, P. Turán. On a problem of K. Zarankiewicz // Colloquium Math.. — 1954. — Т. 3. — С. 50–57.
  • P. Erdős, A. Hajnal, J. W. Moon. A problem in graph theory // The American Mathematical Monthly. — 1964. — Т. 71. — С. 1107–1110. — DOI:10.2307/2311408.
  • Jan Arne Telle, Yngve Villanger. Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings / Leah Epstein, Paolo Ferragina. — Springer, 2012. — Т. 7501. — С. 802–812. — () — DOI:10.1007/978-3-642-33090-2_69.
  • Haim Kaplan, Jiří Matoušek, Micha Sharir. Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique // . — 2012. — Т. 48, вип. 3. — С. 499–517. — arXiv:1102.5391. — DOI:10.1007/s00454-012-9443-3.. Дивіться, зокрема, лему 3.1 і зауваження після леми.
  • Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings / Frank Dehne, Jörg-Rüdiger Sack, Ulrike Stege. — Springer, 2015. — Т. 9214. — С. 506–517. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-21840-3_42.

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

U teoriyi grafiv vi lnij vid t bikli k graf graf u yakomu nemaye povnih dvochastkovih grafiv iz 2t vershinami Kt t yak pidgrafiv Simejstvo grafiv ye vilnim vid biklik yaksho isnuye chislo t take sho vsi grafi v simejstvi vilni vid t biklik Simejstva vilnih vid bicikliv grafiv utvoryuyut odin iz najzagalnishih tipiv simejstv rozridzhenih grafiv Voni vinikayut u zadachah incidentnosti v kombinatornij geometriyi a takozh vikoristovuyutsya v en VlastivostiRozridzhenist Za teoremoyu Kovari Sos Turana bud yakij vilnij vid t bicikliv graf iz n vershinami maye O n2 1 t reber tobto graf istotno ridkshij nizh shilnij graf Z inshogo boku yaksho simejstvo grafiv viznachene zaboronenimi pidgrafami abo zamknute vidnosno operaciyi vzyattya pidgrafa i ne vklyuchaye shilnih grafiv dovilno velikogo rozmiru vono maye buti vilnim vid t biklik dlya deyakogo t inakshe simejstvo maye vklyuchati dovilno veliki shilni povni dvochastkovi grafi Shodo nizhnoyi mezhi Erdesh Hajnal i Muun vislovili pripushennya sho bud yakij maksimalnij vilnij vid t biklik dvochastkovij graf do yakogo ne mozhna dodati rebro bez stvorennya t bikliki maye prinajmni t 1 n m t 1 reber de n ta m chislo vershin u kozhnij chastci grafa Zv yazok z inshimi tipami simejstv rozridzhenih grafiv Graf iz virodzhennyam d ye obov yazkovo vilnim vid d 1 biklik Krim togo simejstvo vilnih vid biklikiv grafiv maye buti nide ne shilnim sho oznachaye sho dlya bud yakogo chisla k isnuye graf yakij ne ye k neglibokim minorom bud yakogo grafa zi simejstva Zokrema yaksho isnuye graf z n vershinami yakij ne ye 1 neglibokimi minorom to simejstvo maye buti vilnim vid n biklik oskilki vsi grafi z n vershinami ye 1 neglibokimi minorami grafa Kn n Otzhe vilni vid biklik simejstva grafiv unifikuyut dva z najzagalnishih klasiv rozridzhenih grafiv ZastosuvannyaDiskretna geometriya U kombinatornij geometriyi bagato tipiv grafiv incidentnosti zavidomo vilni vid biklik Napriklad graf incidentnosti skinchennoyi mnozhini tochok i pryamih na evklidovij ploshini zavidomo ne mistit pidgrafa K2 2 Parametrizovana skladnist Vilni vid biklik grafi vikoristovuyut u teoriyi en dlya rozrobki algoritmiv efektivnih dlya rozridzhenih grafiv iz dosit malimi vhidnimi parametrami Zokrema poshuk dominivnoyi mnozhini rozmirom k na vilnih vid t biklik grafah ye fiksovano parametrizovano rozv yaznoyu zadacheyu yaksho vikoristati parametr k t navit popri te sho isnuyut vagomi pidstavi sho ce nemozhlivo yaksho vikoristovuvati tilki parametr k bez t Ti zh rezultati istinni dlya bagatoh variantiv zadachi pro dominivnu mnozhinu Perevirka chi maye dominivna mnozhina rozmir ne bilshe k mozhna takozh peretvoriti na inshu perevirku z tiyeyu zh parametrizaciyeyu zastosuvannyam nizki vstavok i vidalen vershin zberigayuchi vlastivist dominuvannya PrimitkiKovari T Sos Turan 1954 Cya pracya rozglyadaye chislo reber vilnih vid biklik grafiv ale standartne zastosuvannya jmovirnisnogo metodu perenosit ti sami mezhi na dovilni grafi Erdos Hajnal Moon 1964 Erdos Hajnal Moon 1964 s 1107 1110 Telle Villanger 2012 s 802 812 Kaplan Matousek Sharir 2012 s 499 517 Lokshtanov Mouawad Panolan Ramanujan Saurabh 2015 s 506 517 LiteraturaT Kovari V T Sos P Turan On a problem of K Zarankiewicz Colloquium Math 1954 T 3 S 50 57 P Erdos A Hajnal J W Moon A problem in graph theory The American Mathematical Monthly 1964 T 71 S 1107 1110 DOI 10 2307 2311408 Jan Arne Telle Yngve Villanger Algorithms ESA 2012 20th Annual European Symposium Ljubljana Slovenia September 10 12 2012 Proceedings Leah Epstein Paolo Ferragina Springer 2012 T 7501 S 802 812 DOI 10 1007 978 3 642 33090 2 69 Haim Kaplan Jiri Matousek Micha Sharir Simple proofs of classical theorems in discrete geometry via the Guth Katz polynomial partitioning technique 2012 T 48 vip 3 S 499 517 arXiv 1102 5391 DOI 10 1007 s00454 012 9443 3 Divitsya zokrema lemu 3 1 i zauvazhennya pislya lemi Daniel Lokshtanov Amer E Mouawad Fahad Panolan M S Ramanujan Saket Saurabh Algorithms and Data Structures 14th International Symposium WADS 2015 Victoria BC Canada August 5 7 2015 Proceedings Frank Dehne Jorg Rudiger Sack Ulrike Stege Springer 2015 T 9214 S 506 517 Lecture Notes in Computer Science DOI 10 1007 978 3 319 21840 3 42

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