Körgrafikon

A gráfelméletben a körgráf egy kör húrhalmazának metszéspontjainak grafikonja . Vagyis ez egy irányítatlan gráf , amelynek csúcsai azonosíthatók a kör húrjaival, és ezek a csúcsok akkor és csak akkor szomszédosak, ha a megfelelő akkordok metszik egymást.

Algoritmikus összetettség

Spinrad [1] bemutatott egy O( n 2 ) idő alatt futó algoritmust, amely megvizsgálja, hogy egy adott n csúcsú irányítatlan gráf körkörös-e, és ha körkörös, akkor összeállít egy akkordhalmazt, amely körgráfot eredményez.

Sok más olyan probléma, amely általános gráfokon NP-teljes , rendelkezik polinomiális idejű algoritmusokkal, ha csak körgráfokra korlátozódik. Például Klox [2] megmutatta, hogy egy körgráf faszélessége meghatározható és az optimális dekompozíciós fa O( n 3 ) idő alatt megszerkeszthető. Ezen kívül a legkisebb helyettesítés (vagyis az adott körgráfot részgráfként tartalmazó, minél kevesebb élű akkordgráf) O( n 3 ) időben található [3] . Tiskin [4] kimutatta, hogy a körgráf legnagyobb klikkje O( n log 2 n ) idő alatt, Nash és Gregg [5] pedig azt, hogy egy súlyozatlan körgráf legnagyobb független halmaza O( n min{ d , α }), ahol d a sűrűségként ismert gráfparaméter , α pedig a körgráf függetlenségi száma .

Ennek ellenére vannak olyan problémák, amelyek NP-teljesek maradnak , még akkor is, ha kördiagramokra korlátozódnak. Ezek a feladatok közé tartozik a domináns halmaz , a legkisebb összefüggő domináns halmaz és a legkisebb teljes domináns halmaz [6] keresése .

Kromatikus szám

A körgráf kromatikus száma az a legkisebb számú szín, amellyel az akkordokat úgy színezhetjük, hogy ne legyen két egymást metsző akkord egyforma színű. Mivel lehetséges olyan körgráfot alkotni, amelyben tetszőleges számú húr metszi egymást, ezért a körgráf kromatikus száma tetszőlegesen nagy lehet, és a körgráf kromatikus számának meghatározása NP-teljes feladat [8 ] . Egy NP-teljes probléma annak ellenőrzése is, hogy lehetséges-e egy körgráfot négy színnel színezni [9] . Unger [10] azzal érvelt, hogy a három színnel való színezés keresése elvégezhető polinomiális időben is , de sok részlet hiányzik az eredményeinek leírásából [10] .

Egyes szerzők a körgráfok korlátozott alosztályainak kis számú színnel történő színezésének problémáit tanulmányozták. Különösen azok a körgráfok, amelyekben nincsenek k vagy több akkordból álló halmazok, amelyekben az összes akkord metszi egymást, színezhetők a színek túllépése nélkül [11] . Különösen k  = 3 esetén (azaz háromszög nélküli körgrafikonoknál ) a kromatikus szám nem haladja meg az ötöt, és ez a korlát éles – minden háromszög nélküli körgrafikon öt színnel színezhető, és vannak háromszögek. -szabad körgrafikonok, amelyek színezéséhez öt szín szükséges [12] . Ha egy körgráfnak legalább öt kerülete van (azaz nem tartalmaz háromszögeket és négy csúcsú ciklusokat), akkor három színnel színezhető [ 13] . A dobozgráfok háromszög nélküli színezésének problémája megegyezik azzal a problémával, amikor a dobozgráfokat a fák közvetlen szorzatára izometrikus gráfként ábrázoljuk . Ebben a feladatmegfelelésben a színezésben szereplő színek száma megfelel a termékben lévő fák számának [14] .

Alkalmazások

A körgrafikonok a VLSI -tervezésben a PCB-útválasztás egy speciális esetének absztrakciójaként jelennek meg, amely a "bipoláris csatorna keresztezési útválasztása" néven ismert. Ebben az esetben a nyomkövetési terület egy téglalap, minden hálózat bipoláris, és a vezetékek a téglalap kerülete mentén helyezkednek el. Könnyen belátható, hogy ennek a hálózatnak a metszésponti gráfja egy körgráf [15] . Az útválasztás egyik célja, hogy a különböző hálózatok között ne legyen elektromos érintkezés, és az esetleges átfedő részek különböző rétegeken feküdjenek. Így a kördiagramok rögzítik a nyomkövetési feladatok egy részét.

A körgráfok színezésével tetszőleges gráfok könyvbeágyazását is megtalálhatjuk - ha egy adott G gráf csúcsai egy körön helyezkednek el, és a G gráf élei alkotják a kör húrjait, akkor a gráf Ezeknek az akkordoknak a metszéspontja egy körgrafikon, és ennek a körgráfnak a színezése egyenértékű egy könyvbeágyazással, amely megőrzi a kör elrendezését . Ebben az egyenértékűségben a színek száma megfelel a könyvbetét oldalszámának [16] .

Kapcsolódó gráfosztályok

Egy egyenes intervallumhalmazának metszésponti gráfját intervallumgráfnak nevezzük .

Egy gráf akkor és csak akkor kör alakú, ha szabályos intervallumgráf . Ezek olyan gráfok, amelyek csúcsai (nyitott) szakaszoknak felelnek meg, és két csúcsot egy él köt össze, ha két intervallumnak van egy nem üres metszéspontja. Azonban egyetlen intervallum sem szerepel teljesen egy másik intervallumban.

A sztringgráfok , a görbék síkbeli metszéspontjai , speciális esetként körgráfokat tartalmaznak.

Bármely távolság-örökölt gráf kör gráf, akárcsak minden permutáció vagy közömbös gráf . Bármely külső síkbeli gráf körkörös is [17] [16] .

Jegyzetek

  1. ↑ Spinrad, 1994 .
  2. ↑ Kloks, 1996 .
  3. ↑ Kloks, Kratsch, Wong, 1998 .
  4. ↑ Tiskin, 2010 .
  5. ↑ Nash, Gregg, 2010 .
  6. ↑ Keil, 1993 .
  7. ↑ Ageev, 1996 .
  8. ↑ Garey, Johnson, Miller, Papadimitriou, 1980 .
  9. ↑ Unger (1988) .
  10. ↑ 12 Unger , 1992 .
  11. ↑ Černý, 2007 . A korábbi határokat lásd Gyárfás, 1985 , Kostochka, 1988 és Kostochka, Kratochvíl, 1997 .
  12. ↑ Lásd Kostochka, 1988 a felső korlátot és Ageev, 1996 az alsó korlátot elérő gráfokat. Karapetyan ( Karapetyan 1984 ) és ( Gyárfás, Lehel 1985 ) korábban gyengébb határokat jelölt meg ugyanennek a problémának.
  13. ↑ Ageev, 1999 .
  14. ↑ Bandelt, Chepoi, Eppstein, 2010 .
  15. ↑ Sherwani, 2000 .
  16. ↑ 12 Unger , 1988 .
  17. ↑ Wessel, Poschel, 1985 .

Irodalom

Linkek