PROFILPELAJAR.COM

A matematika, azon belül a gráfelmélet területén egy gráf akkor $t$ -biklikk-mentes (biclique-free), t-páros klikkmentes vagy $t$ -teljes páros gráf-mentes, ha nem tartalmazza a 2 $t$ -csúcsú, tehát a $K t, t$ teljes páros gráfot részgráfjaként. Egy gráfcsalád akkor biklikkmentes, ha létezik olyan $t$ szám, amire a család összes gráfja $t$ -biklikkmentes. A biklikkmentes gráfok a ritka gráfok családjának egyik legáltalánosabb tagjai. Fellépnek diszkrét geometriai illeszkedési problémák kapcsán és parametrizált komplexitású problémákban is előkerülnek.

Tulajdonságok

Ritkaság

A Kővári–Sós–Turán-tétel szerint az $n$ -csúcsú $t$ -biklikkmentes gráfok éleinek nagyságrendje $O (n 2 - 1/ t)$ , ami jóval kevesebb egy sűrű gráf éleinél.^[1] Megfordítva, ha egy gráfcsaládot tiltott részgráfjai alapján határozunk meg, illetve a részgráfképzés műveletére nézve zárt és nem tartalmaz tetszőlegesen nagyméretű sűrű gráfokat, akkor szükségképpen $t$ -biklikkmentes valamely $t$ értékre, különben nagy, sűrű teljes páros gráfokat kellene tartalmaznia.

Alsó korlátként (Erdős, Hajnal & Moon 1964) sejtése szerint minden maximális $t$ -biklikkmentes páros gráf (maximális olyan értelemben, hogy nem adható hozzá további él anélkül, hogy $t$ -biklikk jönne létre) legalább $(t - 1)(n + m - t + 1)$ élt tartalmaz, ahol $n$ és $m$ a bipartíció két oldalának csúcsszámai.^[2]

Kapcsolat más ritkagráf-családokkal

Egy $d$ degeneráltságú gráf szükségképpen $(d + 1)$ -biklikkmentes. Ráadásul a sehol sem sűrű gráfok osztálya biklikkmentes. Általánosabban, ha létezik $n$ -csúcsú gráf, ami a gráfcsalád egyetlen tagjának sem 1 mélységű korlátos mélységű minorja, akkor a család $n$ -biklikkmentes, hiszen az összes $n$ -csúcsú gráf a $K n, n$ 1 mélységű sekély minorja. Ily módon a biklikkmentes gráfcsaládok a ritka gráfok két, legáltalánosabb osztályát egyesítik.^[3]

Alkalmazások

Diszkrét geometria

A diszkrét geometria területén fellépő illeszkedési gráfok számos fajtája biklikkmentes. Erre egyszerű példa, hogy az euklideszi síkon véges számú pont és egyenes illeszkedési gráfja sohasem tartalmazza a $K 2,2$ részgráfot.^[4]

Parametrizált komplexitás

A parametrizált komplexitás területén a biklikkmentes gráfok olyan algoritmusokban bukkannak fel, melyek hatékonyan kezelnek megfelelően kicsi bemeneti értékekkel rendelkező ritka gráfokat. Konkrétan a $t$ -biklikkmentes gráfokban a $k$ méretű domináló csúcshalmaz keresése rögzített paraméter mellett kezelhető, ha a paraméter $k + t$ , még akkor is, ha meggyőző bizonyítékok mutatnak arra, hogy ez nem lehetséges, ha kizárólag $k$ a paraméter. Hasonló eredményeket igazoltak a domináló halmaz-probléma több változatára.^[3] Ugyanezzel a paraméterezéssel tesztelhető az is, hogy valamely, legfeljebb $k$ méretű domináló halmaz átvihető-e egy másikba csúcsok hozzáadásának és törlésének láncolatán keresztül, miközben a domináló tulajdonság megmarad.^[5]

Jegyzetek

↑ Kővári, T.; T. Sós, V. & Turán, P. (1954), "On a problem of K. Zarankiewicz", Colloquium Math. 3: 50–57, <http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3110.pdf>. Kővári Tamás, T. Sós Vera és Turán Pál munkája a biklikk-mentes páros gráfok élszámával foglalkozik, de a valószínűségi módszer standard alkalmazásával ugyanezt a korlátot tetszőleges gráfokra is el lehet érni.
↑ Erdős, P.; Hajnal, A. & Moon, J. W. (1964), "A problem in graph theory", The American Mathematical Monthly 71: 1107–1110, doi:10.2307/2311408, <http://www.renyi.hu/~p_erdos/1964-02.pdf>.
↑ ^a ^b Telle, Jan Arne & Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah & Ferragina, Paolo, Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, vol. 7501, Lecture Notes in Computer Science, Springer, pp. 802–812, DOI 10.1007/978-3-642-33090-2_69.
↑ Kaplan, Haim; Matoušek, Jiří & Sharir, Micha (2012), "Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique", Discrete and Computational Geometry 48 (3): 499–517, DOI 10.1007/s00454-012-9443-3. Lásd a Lemma 3.1-et és az azt követő megjegyzéseket.
↑ Lokshtanov, Daniel; Mouawad, Amer E. & Panolan, Fahad et al. (2015), "Reconfiguration on sparse graphs", in Dehne, Frank; Sack, Jörg-Rüdiger & Stege, Ulrike, Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings, vol. 9214, Lecture Notes in Computer Science, Springer, pp. 506–517, doi:10.1007/978-3-319-21840-3_42, <http://folk.uib.no/amo110/assets/papers/WADS2015TW.pdf>. Hozzáférés ideje: 2017-05-24 Archiválva 2017. november 13-i dátummal a Wayback Machine-ben Archivált másolat. [2017. november 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. május 24.)Archivált másolat. [2017. november 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. május 24.).