Intervallumgrafikon dimenzió

A gráfelméletben a gráf intervallumdimenziója  egy gráfinvariáns , amelyet Fred S. Roberts vezetett be 1969-ben.

A gráf intervallumdimenziója az a minimális méret , amelyben egy adott gráf a tengelyekkel párhuzamos élekkel rendelkező hipertéglalapok (azaz többdimenziós téglalap alakú paralelepipedonok) metszéspontjainak gráfjaként ábrázolható. Azaz egy az egyhez megfelelőnek kell lennie a gráf csúcsai és a hipertéglalapok halmaza között úgy, hogy a téglalapok akkor és csak akkor metszik egymást, ha van egy él, amely összeköti a megfelelő csúcsokat.

Példák

Az ábrán egy hat csúcsú gráf látható, és ennek a gráfnak a (közönséges kétdimenziós) téglalapok metszésgráfjaként való ábrázolása. Ez a gráf nem ábrázolható kisebb méretű téglalapok (jelen esetben szegmensek) metszéspontjainak gráfjaként, ezért a gráf intervallumdimenziója kettő.

Roberts [1] kimutatta, hogy egy teljes 2n csúcsú gráf tökéletes illeszkedésének törlésével kialakított 2n csúcsú gráf intervallumdimenziója pontosan n – minden  össze nem kapcsolt csúcspárt hipertéglalapként kell ábrázolni, amelyeket más módon kell elválasztani, mint egy másik méretpár. Ennek a pontosan n méretű gráfnak a hipertéglalap-ábrázolását úgy találhatjuk meg, hogy az n - dimenziós hiperkocka mindegyik 2n lapját hipertéglalappá vastagítjuk. Ennek az eredménynek köszönhetően az ilyen gráfokat Roberts-gráfoknak [2] kezdték el nevezni , bár ismertebb nevén „party” gráfok , és T (2 n , n ) Turan -gráfként is kezelhetők .

Más gráfosztályokhoz való viszony

Egy gráfnak legfeljebb egy intervallumdimenziója van akkor és csak akkor, ha intervallumgráf . Egy tetszőleges G gráf  intervallumdimenziója azoknak az intervallumgráfoknak a minimális száma, amelyeknek ugyanaz a csúcskészlete (mint G ) úgy, hogy az intervallumgráfok élhalmazainak metszéspontja adja G -t . Bármely síkbeli gráf intervallumdimenziója legfeljebb kettő [3] , és minden síkbeli gráf legfeljebb három [4] .

Ha egy kétrészes gráf intervallumdimenziója kettő, akkor a sík tengelyeivel párhuzamos szakaszok metszéspontjainak grafikonjaként ábrázolható [5] .

Algoritmikus eredmények

Számos gráfprobléma hatékonyabban megoldható vagy közelíthető korlátozott intervallumdimenziójú gráfokon. Például korlátozott intervallumdimenziójú gráfok esetén a legnagyobb klikkprobléma megoldható polinomiális időben [6] . Néhány más gráfproblémára akkor lehet hatékony megoldást vagy közelítést találni, ha az ábrázolás kisdimenziós hipermogoéderek metszéspontja [7] .

Az ilyen reprezentációk megtalálása azonban nehéz lehet – annak ellenőrzése, hogy egy adott gráf intervallumdimenziója meghaladja-e az előre meghatározott K értéket , NP-teljes probléma még K = 2 esetén is [8] . Chandran, Francis és Sivadasan [9] algoritmusokat írt le tetszőleges gráfok hipertéglalap metszéspontos gráf reprezentációinak megtalálására, amelyek mérete a gráf legnagyobb hatványának logaritmikus tényezőjén belül van. Ez az eredmény felső korlátot ad a gráf intervallumdimenziójára.

A természetes paraméterek nehézségei ellenére egy gráf intervallumdimenziója fix paraméterekkel megoldható probléma , ha a paraméterezést a bemeneti gráf csúcslefedettségének száma szerint hajtjuk végre [10] .

Jegyzetek

  1. ↑ Roberts, 1969 .
  2. ↑ Lásd például Chandran, Francis és Sivadasan (2010 ), Chandran és Sivadasan Chandran, Sivadasan (2007 ) cikkeit.
  3. ↑ Scheinerman, 1984 .
  4. ↑ Thomassen, 1986 .
  5. ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993 .
  6. ↑ Chandran, Francis és Sivadasan (2010 ) megjegyezte, hogy ez abból a tényből következik, hogy ezeknek a gráfoknak polinomiális számú maximális klikkje van . A hipertéglalapok metszéspontjaként való explicit ábrázoláshoz nem szükséges az összes maximális klikk számbavétele.
  7. ↑ Lásd például Agarwal, van Kreveld, Suri (1998 ) és Berman, DasGupta, Muthukrishnan, Ramaswami (2001 ) a téglalap metszés gráfok legnagyobb független halmazközelítését, illetve Chlebík, Chlebíková (2005 ) a nehézségek tárgyalását. közelítve ezeket a problémákat nagy méretekre
  8. ↑ Cozzens (1981 ) kimutatta, hogy egy gráf intervallumdimenziójának kiszámítása NP-teljes probléma. Yanakakis (1982 ) kimutatta, hogy még annak ellenőrzése is, hogy az intervallumdimenzió nem haladja meg a 3-at, NP-nehéz. Végül Kratochvíl (1994 ) kimutatta, hogy egy intervallumdimenzió = 2 felismerése NP-nehéz probléma.
  9. ↑ Chandran, Francis, Sivadasan, 2010 .
  10. ↑ Adiga, Chitnis, Saurabh, 2010 .

Irodalom