matematikai fogalom a gráfelméletben From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén a karommentes gráf (claw-free graph) olyan gráf, mely nem tartalmazza a karomgráfot feszített részgráfként.
A karom a K1,3 teljes páros gráf másik neve (tehát arról a csillaggráfról van szó, ami három éllel, három levéllel és egy csomóponttal rendelkezik). Egy karommentes gráf onnan ismerszik meg, hogy egyetlen feszített részgráfja sem karom; tehát semelyik négy csúcspontja között nincs ilyen módon csatlakozó három él. Ezzel egyenértékű megfogalmazás, hogy a karommentes gráf olyan gráf, melyben bármely csúcs szomszédsága egy háromszögmentes gráf komplementere.
A karommentes gráfokat eredetileg az élgráfok általánosításaként vizsgálták, de három fő felfedezést tettek velük kapcsolatban, melyek indokolták a további vizsgálódást: hogy bármely páros rendű karommentes összefüggő gráf rendelkezik teljes párosítással; a karommentes gráfok független csúcshalmazait polinom időben megtaláló algoritmusok felfedezése; a karommentes perfekt gráfok karakterizációja.[1] Több száz matematikai tanulmány és áttekintő munka foglalkozik velük.[1]
Egy n csúccsal és m éllel rendelkező gráf karommentessége O(n4) időben könnyen ellenőrizhető, a gráf minden csúcs-négyesét ellenőrizve, hogy nem alkotnak-e karmot.[5] Ennél hatékonyabb, de bonyolultabb megoldás annak ellenőrzése a gráf minden egyes csúcsára, hogy szomszédainak komplementer gráfja nem tartalmaz-e háromszöget. Egy gráf pontosan akkor tartalmaz háromszöget, ha szomszédsági mátrixának köbének átlójában található nem nulla elem, ezért a háromszög keresése aszimptotikusan ugyanannyi idő alatt végezhető el, mint az n × n mátrixszorzás.[6] Ezért a Coppersmith–Winograd-algoritmust használva az algoritmus futási ideje O(n3,376).
(Kloks, Kratsch & Müller 2000) felismerése szerint bármely karommentes gráf csúcsainak legfeljebb 2√m szomszédja van, egyébként a Turán-tétel szerint a csúcsoknak nem jutna elég él ahhoz, hogy egy háromszögmentes gráf komplementerét alkossák. Ez a megfigyelés alkalmat ad arra, hogy a fent említett gyors mátrixszorzáson alapuló algoritmussal ellenőrizzük az összes szomszédságot a mátrixszorzás 2√m × 2√m idejében, vagy alacsonyabb fokszámú csúcsoknál még gyorsabban. Az algoritmus számára a legrosszabb eset, amikor Ω(√m) csúcsnak van Ω(√m) szomszédja, míg a maradéknak néhány szomszédja van, ilyenkor az összidő O(m3,376/2) = O(m1,688).
Mivel a karommentes gráfok háromszögmentes gráfok komplementereit tartalmazzák, az n csúcsú karommentes gráfok száma legalább olyan gyorsan nő, mint a háromszögmentes gráfoké, exponenciálisan az n négyzete arányában. Az n csúcspontú összefüggő karommentes gráfok száma n = 1, 2, ...-re:
Ha megengedjük a nem összefüggő gráfokat is, még nagyobb számokat kapunk:
A (Palmer, Read & Robinson 2002) által vázolt technika lehetővé teszi a karommentes 3-reguláris gráfok igen hatékony leszámlálását, ami nem jellemző a gráfleszámlálási problémák esetében.
(Sumner 1974) és tőle függetlenül (Las Vergnas 1975) is bebizonyította, hogy minden páros elemszámú karommentes összefüggő gráf rendelkezik teljes párosítással.[7] Ez azt jelenti, hogy létezik a gráfnak olyan élhalmaza, hogy a gráf minden csúcsa pontosan egy párosított él végpontja. Az eredmény élgráfokra vonatkozó speciális esetéből következik, hogy bármely gráfban, mely páros számú éllel rendelkezik, particionálható kettő hosszúságú utakra. A teljes párosítás lehetővé teszi a karommentes gráfok karakterizálását, mint pontosan azok a gráfok, melyek minden páros rendű összefüggő feszített részgráfjában van teljes párosítás.[7]
Sumner bizonyítása ennél erősebb állítást mutat meg, miszerint bármely összefüggő karommentes gráfban található olyan szomszédos csúcspár, melyek eltávolításával a maradék gráf összefüggő marad. Ennek megmutatására Sumner veszi az egymástól lehető legtávolabb lévő u és v csúcsokat, majd úgy választja ki a w csúcsot, hogy v-nek az u-tól lehető legtávolabb lévő szomszédja legyen; megmutatja, hogy sem v, sem w nem lehet rajta a bármely más csúcstól u-ba vezető legrövidebb utak egyikén sem, így v és w eltávolításával a maradék gráf biztosan összefüggő marad. A párosított csúcsok ilyeténként történő sorozatos eltávolítása pedig az adott karommentes gráf teljes párosítását hozza létre.
Ugyanez a bizonyítási ötlet általánosabban is felhasználható: legyen u egy tetszőleges csúcs, v a tőle lehető legtávolabb lévő csúcs, w pedig v-nek az a szomszédja, ami a lehető legnagyobb távolságra van u-tól. Ekkora a v és w eltávolítása egyetlen csúcs u-tól való távolságát sem változtatja meg. Így a párosítás létrehozása az u-tól minél távolabb lévő vw párok megkeresésével és eltávolításával lineáris időben elvégezhető egy u gyökerű szélességi bejárás egyszeri posztorder bejárásával. (Chrobak, Naor & Novick 1989) megadnak egy alternatív, mélységi bejáráson alapuló lineáris algoritmust, valamint ugyanezen probléma hatékony megoldására szolgáló párhuzamos algoritmusokat.
(Faudree, Flandrin & Ryjáček 1997) számos kapcsolódó eredményt sorol fel, köztük ezeket: a páros rendű (r − 1)-szorosan összefüggő K1,r-mentes gráfok rendelkeznek tökéletes párosítással bármely r ≥ 2-re; a legfeljebb egy 1 fokszámú csúccsal rendelkező, páratlan rendű karommentes gráfok particionálhatók egy páratlan hosszúságú körre és egy párosításra; bármely k-ra, ami legfeljebb a karommentes gráf minimális fokszámának a fele igaz, hogy ha akár k, akár a csúcsok száma (a gráf rendje) páros, akkor a gráfnak létezik k-faktora (k-reguláris feszítő részgráfja); és ha egy karommentes gráf (2k + 1)-összefüggő, akkor bármely k-élből álló párosítás teljes párosítássá egészíthető ki.
Egy élgráf független csúcshalmaza az eredeti gráf párosításának felel meg, azaz olyan élhalmaznak, melyben az élek egyike sem ered közös csúcsból. Az (Edmonds 1965) által leírt Edmonds-algoritmus bármely gráf maximális párosítását polinom időben keresi meg, ami egyenértékű az élgráf maximális független csúcshalmazának megkeresésével. Az algoritmust egymástól függetlenül (Sbihi 1980) és (Minty 1980) egészítették ki karommentes gráfokra.[8]
Mindkét megközelítés azt használja ki, hogy a karommentes gráfokban egy csúcsnak sem lehet kettőnél több szomszédja egy független csúcshalmazban, így két független csúcshalmaz szimmetrikus differenciájának feszített részgráfjának fokszáma legalább kettő; tehát körgráfok és útgráfok uniójából előállítható. Ami főként érdekes, hogy ha I egy nem maximális független csúcshalmaz, a maximális független csúcshalmaztól csak páros körökkel és úgynevezett „javító utakkal” különbözik: ezek olyan feszített utak, melyben szereplő csúcsok váltakozva I-beliek, illetve I-n kívüliek, és végpontjaiknak csak egy szomszédjuk szerepel I-ben. Mivel I és bármelyik javító út szimmetrikus differenciája nagyobb független halmazt eredményez, a feladat redukálódott javító utak keresésére, amíg azok el nem fogynak, hasonlóan a maximális párosítást kereső algoritmushoz.
A Sbihi által leírt algoritmus az Edmonds-algoritmus virág-összehúzási lépése helyett egy hasonló, de bonyolultabb klikk-összehúzási lépést tartalmaz. Minty megközelítésében a problémagráfot transzformáljuk egy segéd-élgráffá, amin közvetlenül alkalmazzuk az Edmonds-algoritmust a javító utak megtalálására. A Nakamura & Tamura 2001 által adott javítás után Minty eredménye használható egy általánosabb probléma, a maximális súlyú független csúcshalmazok karommentes gráfokban való keresésének polinom időben történő megoldására. Ezeket az eredményeket szélesebb gráfosztályokra is sikerült általánosítani.[8] Egy újszerű struktúratétel segítségével (Faenza, Oriolo & Stauffer 2011) megadott egy harmadfokú polinom-időben futó, súlyozott esetben is működő algoritmust.
Egy perfekt gráf olyan gráf, melynek kromatikus száma és klikkszáma megegyezik és ez minden feszített részgráfjára is igaz. Az erős perfektgráf-tétel alapján tudjuk, hogy a perfekt gráfok jellemezhetők úgy, mint azok a gráfok, melyek nem tartalmaznak feszített részgráfként sem páratlan kört, sem páratlan kör komplementerét (úgynevezett „páratlan lyukat”).[9] Ez azonban évekig csak egy megoldatlan sejtés maradt, melyet csak egyes gráfosztályokra sikerült igazolni. Az ilyen gráfosztályok egyike éppen a karommentes gráfok voltak: több szerző is felfedezte, hogy a páratlan körök és páratlan lyukak nélküli karommentes gráfok perfektek. A perfekt karommentes gráfok polinom időben felismerhetők. Egy perfekt karommentes gráfban bármely csúcs szomszédsága egy páros gráf komplementerét alkotja. A perfekt karommentes gráfok polinom időben színezhetők és polinom időben találhatók bennük maximális klikkek.[10]
 | A matematika megoldatlan problémája: Vajon a karommentes gráfok listakromatikus száma mindig megegyezik a kromatikus számukkal? (A matematika további megoldatlan problémái) |
Általánosságban NP-nehéz probléma egy karommentes gráf legnagyobb klikkjét megtalálni.[5] Az optimális színezése szintén NP-nehéz, mivel (az élgráfokon keresztül) a probléma a gráf élkromatikus száma kiszámításának NP-nehéz problémáját általánosítja.[5] Hasonló okból NP-nehéz olyan színezést találni, ami 4/3-nál jobb approximációs arányt ér el. Mohó színezési algoritmussal azonban elérhető a 2 approximációs arány, mivel a karommentes gráf kromatikus száma meghaladja a maximális fokszámának felét. A lista-élszínezési sejtés szerint karommentes gráfok listakromatikus száma megegyezik a kromatikus számmal; ez a kettő más típusú gráfoknál nagyon különböző is lehet.[11]
Bár nem minden karommentes gráf perfekt, a karommentes gráfok teljesítenek egy másik, perfekcióhoz köthető feltételt. Egy gráf akkor perfekt domináló, ha létezik olyan minimális domináló halmaza, ami független, és ez a tulajdonság minden feszített részgráfjára igaz. A karommentes gráfok ilyenek. Hogy ezt belássuk, legyen D egy karommentes gráf domináló halmaza, és tegyük fel, hogy v és w szomszédos csúcsok D-ben; ekkor a v által igen, de w által nem dominált csúcsok halmazának klikknek kell lennie (különben v lenne a karom közepe). Ha ennek a klikknek minden csúcsát már legalább egy D-beli tag dominálja, akkor v eltávolítható, ami egy kisebb független domináló halmazt eredményez, különben pedig v lecserélhető a klikk valamely nem dominált csúcsára, ami egy kevesebb szomszéddal rendelkező domináló halmazt eredményez. Ezt a cserefolyamatot ismételve végül eljutunk egy D-nél nem nagyobb domináló halmazig, így ha a kiindulási D halmaz egy minimális domináló halmaz, akkor a folyamat során egy ugyanolyan kicsi független domináló halmazhoz jutunk.[12]
A perfekt domináló tulajdonság ellenére NP-nehéz feladat egy karommentes gráf minimális domináló halmaza méretének megállapítása.[5] Mindazonáltal az általános gráfokhoz képest a minimális domináló halmaz vagy a minimális összefüggő domináló halmaz megkeresése rögzített paraméter mellett kezelhető (fixed-parameter tractable): a gráf mérete szerinti polinomiális szorozva a domináló halmaz mérete szerint exponenciális függvény szerinti idejű.[13]
(Chudnovsky & Seymour 2005) átfogó cikksorozatukban a karommentes gráfok struktúrájának egy elméletét igazolják, a Robertson és Seymour által minorra zárt gráfosztályokra bizonyított gráfminor-tétellel, illetve a Chudnovsky, Seymour és tsai. perfekt gráfokra vonatkozó, az erős perfektgráf-tétel igazolásához használt struktúraelméletével analóg módon.[9] Az elmélet meglehetősen bonyolult, ehelyütt két fontos eredményét emeljük ki. Az első, a karommentes gráfok egy kvázi-élgráfoknak nevezett speciális osztálya (locally co-bipartite graphs, tehát olyan gráfok, melyekben minden csúcs szomszédsága legfeljebb két klikkre particionálható), mely osztályon belül minden gráf a következő két alak valamelyikének felel meg:
Chudnovsky és Seymour bármely összefüggő karommentes gráfot a következő kategóriák egyikébe sorolnak:
A struktúraelmélet jelentős része az antiprizmaszerű gráfok további analízisét célozza. Az analízis fontos részét képezi a Schläfli-gráf, tehát az srg(27,16,10,8) paraméterű karommentes erősen reguláris gráf. A struktúraelmélet a poliéder-kombinatorika területén új eredményekhez vezetett, segítségével új korlátokat állapítottak meg a karommentes gráfok kromatikus számával kapcsolatban,[4][14] valamint új, rögzített paraméter mellett kezelhető algoritmusokat fedeztek fel a karommentes gráfok domináló halmazainak keresésére.[15]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
