Pređi na sadržaj

Savršen graf

S Vikipedije, slobodne enciklopedije
Pejlijev graf reda 9, obojen sa tri boje i klike sastavljene od tri čvora. U ovom grafu, a i u svakom od njegovih indukovanih podgrafova, hromatski broj jednak je broju klike, tako da je ovaj graf savršen.

U teoriji grafova, savršen graf je graf, čiji je hromatski broj svakog indukovanog podgrafa jednak veličini najveće klike tog podgrafa. Po jakoj teoremi o savršenom grafu, savršeni grafovi su isto što i Beržovi grafovi. Graf G je Beržov ako ni G ni njegov komplement nemaju indukovani ciklus neparne dužine (5 ili više).

Savršeni grafovi uključuju mnoge važne familije grafova, a služe da se objedine rezultati vezani za bojenje i klike grafova tih familija. Na primer, u svim savršenim grafovima, problem bojenja grafova, problem najveće klike i problem najvećeg nezavisnog skupa mogu se rešiti u polinomijalnom vremenu. Pored toga, nekoliko važnih minimum-maksimum teorema iz kombinatorike, kao što je Dilvortova teorema, mogu se izraziti preko savršenstva određenih grafova.

Teorija savršenih grafova je razvijena iz rezultata rada Tibor Galaja (1958) koja se na savremenom jeziku može tumačiti kao tvrdnja da je komplement bipartitivnog grafa savršen; ovaj rezultat se takođe može posmatrati kao jednostavan ekvivalent Konigove teoreme, mnogo ranijeg rezultata koji se odnosi na poklapanja i pokrivanje čvorova u bipartitivnim grafovima. Prva upotreba termina "savršen graf" se naizgled pojavljuje u članku Kloda Berža iz 1963, nakon koga su i Beržovi grafovi dobili ime. U ovom dokumentu on je objedinio Gallaiev rezultat sa nekoliko sličnih rezultata kroz definisanje savršenih grafova, i pretpostavio je ekvivalentnost definicija savršenog grafa i Beržovog grafa; Beržova pretpostavka je dokazana 2002. godine kao jaka teorema o savršenom grafu.

Familije savršenih grafova[uredi | uredi izvor]

Neki od poznatijih primera savršenih grafova:

  • Bipartitivni grafovi, grafovi koji mogu biti obojeni sa dve boje, uključujući šume, grafove bez ciklusa.
  • Linijski grafovi bipartitivnih grafova (Konigova teorema). Rukovi grafovi (linijski grafovi kompletnih bipartitivnih grafova) su specijalan slučaj.
  • Tetivni grafovi, grafovi kod kojih svaki ciklus od četiri ili više čvora ima tetivu, granu između dva čvora koji nisu susedni u ciklusu. U njih spadaju šume, k-drva, split grafovi (grafovi koji mogu biti isečeni u kliku i nezavisni skup), blok grafovi (grafovi u kojima je svaka dvostruko povezana komponenta klika), interval grafovi (grafovi kod kojih svaki čvor predstavlja interval linije i svaka grana predstavlja neprazan presek dva intervala), trivijalno savršeni grafovi (interval grafovi za ugnježdene intervale), prag grafovi (grafovi kod kojih su dva čvora susedna kada njihova ukupna težina prelazi numerički prag), vetrenjača grafovi (formirani spajanjem jednakih klika na zajedničkom čvoru), i jako tetivni grafovi (tetivni grafovi u kojima svaki parni ciklus dužine šest ili više ima neparnu tetivu).
  • Uporedni grafovi formirani od parcijalno uređenih skupova spajanjem parova elemenata granom kad god su oni u parcijalnom uređenju. Oni uključuju bipartitivne grafove, komplemente interval grafova, trivijalno savršene grafove, prag grafove, vetrenjača grafove, grafove permutacija (grafovi u kojima grane predstavljaju parove elemenata koji su preokrenuti permutacijom), i kografovi (grafovi formirani rekurzivnim operacijama razdvojene unije i komplementacije).
  • Perfektno uredivi grafovi, grafovi koji mogu biti uređeni tako da algoritam pohlepnog bojenja bude optimalan za svaki indukovani podgraf. Oni uključuju bipartitivne grafove, tetivne grafove, uporedne grafove, razdaljina-nasledne grafove (kod kojih je najkraća putanja u povezanom indukovanom podgrafu jednaka onoj u celom grafu), i točak grafove koji imaju neparan broj čvorova.
  • Trapezni grafovi, grafovi preseka trapeza čiji paralelni parovi grana leže na dve paralelne linije. Oni uključuju interval grafove, trivijalno savršene graofve, prag grafove, vetrenjača grafove i grafove permutacija; njihovi komplementi su podskup uporednih grafova.

Veza sa minimum-maksimum teoremama[uredi | uredi izvor]

Kod svih grafova, broj klike obezbeđuje donju granicu hromatskog broja, jer svim čvorovima u kliki moraju biti dodeljene različite boje. Savršen graf je onaj kod koga je ova donja granica mala, ne samo za graf nego i za sve njegove indukovane podgrafove. Za graf koji nije savršen, hromatski broj i broj klike se mogu razlikovati; na primer, ciklus dužine pet zahteva tri boje za svako pravo bojenje ali njegova najveća klika je veličine dva.

Dokaz da je klasa grafova savršena se može posmatrati kao minimum-maksimum teorema; minimalni broj boja potreban za ove grafove jednak je maksimalnoj veličini klike. Mnoge važne minimum-maksimum teoreme u kombinatorici mogu biti izražene na ovaj način. Na primer, Dilvortova teorema tvrdi da je minimalni broj lanaca u particiji parcijalno uređenog skupa u lancima jednak maksimalnoj veličini antilanca, a tvrđenje se može izraziti i ovako: komplementi uporednih grafova su savršeni. Mirskijeva teorema tvrdi da je minimalni broj antilanaca u particiji jednak najvećoj veličini lanca, i odnosi se na isti način sa savršenošću uporednih grafova.

Konigova teorema u teoriji grafova tvrdi da minimalno pokrivanje čvorova u bipartitivnom grafu odgovara maksimalnom poklapanju i obratno; može biti posmatrano kao savršenost komplemenata bipartitivnih grafova. Druga teorama o bipartitivnim grafovima, gde njihov hromatski indeks odgovara maksimalnom stepenu, jeste ekvivalent savršenosti linijskih grafova bipartitivnih grafova. 

Karakterizacije i teoreme savršenih grafova[uredi | uredi izvor]

U svom početnom radu nad savršenim grafovima, Berž je izneo dve važne pretpostavke o njihovoj strukturi koje su tek kasnije dokazane.

Prva od dve teoreme bila je teorema savršenog grafa Lovasa (1972), koja tvrdi da je graf savršen ako i samo ako je njegov komplement savršen. Stoga, savršenost (definisana kao jednakost veličine najveće klike i hromatskog broja u svakom indukovanom podgrafu) jeste ekvivalent jednakosti veličine maksimalnog nezavisnog skupa i broja pokrivanja klike.

Ciklus od sedam čvorova i njegov komplement, u oba slučaja je prikazano optimalno bojenje i maksimalna klika (prikaz podebljanim granama). Ni jedan od grafova nema jednake veličine klike i bojenja, stoga ni jedan nije savršen.

Druga teorema, koja je izneta kao Beržova pretpostavka, omogućila je zabranjenu karakterizaciju grafa savršenih grafova. Indukovani ciklus neparne dužine (minimum 5) naziva se neparna rupa. Indukovani podgraf koji je komplement neparne rupe naziva se neparna antirupa. Neparni ciklus dužine veće od 3 ne može biti savršen, jer je njegov hromatski broj tri a broj njegove klike je dva. Slično, komplement neparnog ciklusa dužine 2k + 1 ne može biti savršen, jer je njegov hromatski broj k + 1, a broj njegove klike je k. (Alternativno, nesavršenost ovog grafa sledi iz teorije savršenog grafa i nesavršenosti komplementarnog neparnog ciklusa). Kako ovi grafovi nisu savršeni, svaki savršen graf mora biti Beržov graf, graf bez neparnih rupa i bez neparnih antirupa. Berž je pretpostavio suprotno, da je svaki Beržov graf savršen. Ovo je konačno dokazano kao jaka teorema o savršenim grafovima Čudnovske, Robertsona, Simora i Tomasa (2006).

Teorema savršenog grafa ima kratak dokaz, ali dokaz jake teoreme o savršenim grafovima je duga i tehnička, zasnovana na dubokoj strukturalnoj dekompoziciji Beržovih grafova. Slične tehnike dekompozicije su takođe urodile plodom u studijama o drugim klasama grafova, naročito grafovima bez klešta.

Algoritmi nad savršenim rafovima[uredi | uredi izvor]

Kod svih savršenih grafova, problem bojenja grafa, problem maksimalne klike i problem maksimalnog nezavisnog skupa mogu biti rešeni u polinomijalnom vremenu (Grotšel, Lovas i Šriver 1988). Algoritam u opštem slučaju podrazumeva upotrebu elipsoidnog metoda linearnog programiranja, ali efikasniji kombinatorni elementi su poznati za mnoge specijalne slučajeve.

Mnogo godina kompleksnost prepoznavanja Beržovih grafova i savršenih grafova je bila otvorena. Iz definicije Beržovih grafova, sledi njihovo prepoznavanje u co-NP (Lovas 1983). Konačno, nakon dokaza jake teoreme savršenih grafova, otkriven je algoritam polinomijalnog vremena (Čudnovski, Kornuejols, Liu, Simor i Vušković).

Reference[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Савршен_граф&oldid=27823981”