Távolság-örökletes gráf

A matematika, azon belül a gráfelmélet területén egy távolság-örökletes gráf (distance-hereditary graph), távolságtartó gráf vagy „teljesen szeparábilis gráf” (completely separable graph)^[1] olyan gráf, melynek bármely összefüggő feszített részgráfjában ugyanazok a távolságok, mint az eredeti gráfban. Tehát bármely feszített részgráf örökli a nagyobb gráf távolság-értékeit.

Egy távolság-örökletes gráf.

A távolság-örökletes gráfokat (Howorka 1977) nevezte el és tanulmányozta elsőként, bár egy ekvivalens gráfosztály perfektségét Olaru és Sachs már 1970-ben belátta.^[2]

Egy ideje ismert volt, hogy a távolságtartó gráfok a metszetgráfok alapján meghatározott gráfosztályok közé tartoznak,^[3] de a működő metszetgráf-meghatározással adósak voltak a matematikusok (Gioan & Paul 2012) cikkéig.

Definíciók és jellemzés

A távolság-örökletes gráf eredeti meghatározása szerint a G gráf akkor távolság-örökletes, ha bármely H feszített részgráfjába tartozó u és v csúcsokra igaz, hogy a G gráfban köztük húzódó legrövidebb utak közül valamelyiknek a H feszített részgráfban is benne kell lennie; tehát u és v H-beli távolsága bármely feszített részgráfra ugyanakkora, mint a G-beli távolságuk.

A távolságtartó gráfok számos, az eredetivel ekvivalens módon karakterizálhatók:^[4]

• Azok a gráfok, melyekben minden feszített út egyben legrövidebb út; illetve azok a gráfok, melyekben minden nem legrövidebb út csúcsait vizsgálva található olyan él, ami két nem egymást követő csúcsot köt össze.
• Azok a gráfok, melyekben minden, legalább 5 hosszúságú körben található legalább 2 átló, és minden pontosan 5 hosszúságú körben legalább 1 egymást metsző átló található.
• Azok a gráfok, melyekben minden, legalább 5 hosszúságú körben található legalább egy metsző átló.
• Azok a gráfok, melyekben bármely négy u, v, w és x csúcsra igaz, hogy a három távolságösszeg, d(u,v)+d(w,x), d(u,w)+d(v,x), illetve d(u,x)+d(v,w) közül legalább kettő értéke megegyezik.
• Azok a gráfok, melyek izometrikus (távolságtartó) részgráfjai között nem szerepelnek 5 vagy azt meghaladó hosszúságú körök; vagy, nem szerepel a következő három gráf bármelyike: 5 hosszúságú kör egy húrral, 5 hosszúságú kör két nem metsző húrral, 6 hosszúságú kör szemközti csúcsokat összekötő húrral.

A három művelet, melyek segítségével bármely távolságtartó gráf megkonstruálható.

• Azok a gráfok, melyek az egyetlen csúcsból álló gráfból kiindulva a következő három művelet segítségével felépíthetők (lásd az illusztrációt):
  1. Egy új, „függő csúcs” (pendant vertex) hozzáadása, mely a gráf egy létező csúcsához csatlakozik egyetlen éllel.
  2. Egy létező csúcs kicserélése egy olyan csúcspárral, melyek szomszédsága pontosan megegyezik a lecserélt csúcséval. Az új csúcspárt „hamis ikreknek” nevezik.
  3. Egy létező csúcs kicserélése egy olyan csúcspárral, melyek szomszédsága megegyezik a lecserélt csúcséval, majd a csúcspár közé is behúzunk egy élt. Az új csúcspárt „valódi ikreknek” nevezik.
• Azok a gráfok, melyek feloszthatók klikkekre és csillagokra (K_1,q teljes páros gráfokra) splitfelbontással. Ebben a felbontásban a gráfot két olyan részhalmazra osztjuk fel, hogy a részhalmazokat szétválasztó élek teljes páros gráfot alkossanak, majd a felbontás mindkét oldalát egy-egy csúccsal helyettesítve két kisebb gráf jön létre, a részgráfokon pedig rekurzívan végrehajtjuk ugyanezt a műveletet.^[5]
• Pontosan azok a gráfok, melyek „rangszélessége” (rank-width) egy, ahol egy gráf rangszélességén a gráf hierarchikus felbontásainak szomszédsági mátrixainak bizonyos részmátrixainak maximális rangjai közül a minimálisat értjük.^[6]

Más gráfcsaládokkal való kapcsolata

Minden távolság-örökletes gráf perfekt,^[7] azon belül perfekt rendezhető^[8] és Meyniel-gráf. Ezeken túl minden távolságtartó gráf paritásgráf, tehát a gráfban adott csúcspár között bármely két feszített út párossága megegyezik (tehát vagy mindkét út hossza páros, vagy mindkettő páratlan).^[9] A G távolság-örökletes gráf minden páros hatványa (tehát a G²ⁱ gráf, amit a G-ben legfeljebb 2i távolságra lévő csúcsok összekötésével kapunk) merev körű gráf.^[10]

Minden távolság-örökletes gráf megfeleltethető egy kör húrjainak metszetgráfjaként, ezért húrmetszetgráfok (circle graph). Ez abból is megállapítható, ahogy a gráfot felépítjük függők, hamis, illetve valódi ikrek hozzáadásával, az felfogható húrok hozzáadásaként is, a következő módon: függő csúcsnál már létező húrhoz közel adjuk hozzá az új húrt, úgy, hogy csak azt az egy húrt messe; hamis ikrek esetében egy húrt lecserélünk ugyanazokat a húrokat metsző, egymással párhuzamos két húrra; valódi ikreknél pedig egy húrt lecserélünk két csaknem párhuzamos egymást metsző húrra, melyek egymáson kívül ugyanazokat a húrokat metszik, mint a lecserélt húr.

Egy távolság-örökletes gráf pontosan akkor páros, ha háromszögmentes. A páros távolság-örökletes gráfok felépíthetők egyetlen csúcsból kizárólag „függő” csúcsok és „hamis ikrek” hozzáadásával, hiszen „valódi ikrek” hozzáadása háromszöget hozna létre, míg a másik két művelet megtartja a páros tulajdonságot. Minden páros távolság-örökletes gráf gyengén merev körű páros gráf és moduláris gráf.^[11]

Azok a gráfok, melyek egyetlen csúcsból kizárólag „függő” csúcsok és „valódi ikrek” hozzáadásával építhetők fel, tehát „hamis ikrek” nélkül, a ptolemaioszi gráfok speciális esetei, közéjük tartoznak a blokkgráfok is. Azok a gráfok pedig, melyek egyetlen csúcsból kizárólag „hamis ikrek” és „valódi ikrek” hozzáadásával építhetők fel, éppen a kográfok, melyek ebből kifolyólag szintén távolság-örökletesek: a kográfok pontosan a 2 átmérőjű távolság-örökletes gráfok diszjunkt uniói. Egy távolság-örökletes gráf bármely csúcsának szomszédsága egy kográf. Egy fa éleinek bármely orientációjával kapott irányított gráf tranzitív lezárása távolság-örökletes; az a speciális eset, amikor a fa orientációja konzisztensen az egyik csúcsától elfelé mutat, a távolság-örökletes gráfok egy speciális alfaját adja, amit triviálisan perfekt gráfoknak neveznek – melyek egyben merev körű kográfok.^[12]

Algoritmusok

A távolság-örökletes gráfok lineáris időben felismerhetők és átalakíthatók függő és iker csúcsok hozzáadásának szekvenciájába.^[13]

Mivel a távolság-örökletes gráfok perfektek, egyes optimalizálási problémák polinom időben megoldhatók rájuk annak ellenére, hogy általánosabb gráfosztályokon nehezek. Így például egy távolság-örökletes gráfban polinom időben megtalálható a maximális elemszámú klikk vagy a maximális független csúcshalmaz, vagy egy optimális gráfszínezés.^[14] Mivel a távolság-örökletes gráfok húrmetszetgráfok, ugyanazok a polinom idejű algoritmusok náluk is működnek; például polinom időben megállapítható bármely húrmetszetgráf favastagsága, ezért a távolság-örökletes gráfoké is.^[15] Bármely távolság-örökletes gráf klikkszélessége legfeljebb három.^[16] Ennek következményeként, a Courcelle-tétel alapján hatékony dinamikus programozási algoritmusok léteznek ezen gráfokkal kapcsolatos számos probléma megoldására.^[17]

Néhány másik optimalizálási probléma is hatékonyabban megoldható speciálisan a távolságtartó gráfokra szabott algoritmusokkal. Ahogy (D'Atri & Moscarini 1988) megmutatja, a minimális összefüggő domináló halmaz (vagy ami ezzel egyenértékű, a lehetséges maximális levéllel rendelkező feszítőfa) polinom időben megtalálható távolság-örökletes gráfok esetében. A távolságtartó gráfokban Hamilton-kört vagy Hamilton-utat szintén polinom időben lehet találni.^[18]

Fordítás

• Ez a szócikk részben vagy egészben a Distance-hereditary graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. (Hammer & Maffray 1990).
2. Olaru és Sachs az olyan gráfok α-perfektségét igazolták, melyekben minden 5 vagy nagyobb hosszúságú körben metsző átlók találhatók (Sachs 1970, Theorem 5). (Lovász 1972) bebizonyította, hogy az α-perfektség a perfekt gráfok definíciójával ekvivalens.
3. (McKee & McMorris 1999)
4. (Howorka 1977); (Bandelt & Mulder 1986); (Hammer & Maffray 1990); (Brandstädt, Le & Spinrad 1999), Theorem 10.1.1, p. 147.
5. (Gioan & Paul 2012). Egy hasonló felbontási módszert gráf lerajzolásához használt (Eppstein, Goodrich & Meng 2006), páros távolság-örökletes gráfokhoz pedig (Hui, Schaefer & Štefankovič 2004).
6. (Oum 2005).
7. (Howorka 1977).
8. (Brandstädt, Le & Spinrad 1999) pp. 70–71 and 82.
9. (Brandstädt, Le & Spinrad 1999), p.45.
10. (Brandstädt, Le & Spinrad 1999), Theorem 10.6.14, p.164.
11. Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
12. (Cornelsen & Di Stefano 2005).
13. (Damiand, Habib & Paul 2001); (Gioan & Paul 2012). Már korábban, (Hammer & Maffray 1990) bejelentette a lineáris idejű algoritmust, de később Damiand hibákat talált a cikkben.
14. (Cogis & Thierry 2005) egyszerű, közvetlen algoritmust ad meg a távolság-örökletes gráf maximális súlyú független csúcshalmazainak megtalálására, ami a gráf függők/ikrek alapú reprezentációján alapul, kijavítva (Hammer & Maffray 1990) korábbi algoritmus-próbálkozását. Mivel a távolság-örökletes gráfok perfekt rendezhetők, lineáris időben optimálisan színezhetők, először egy lexikografikus szélességi keresés alkalmazásával, majd mohó színezési algoritmussal.
15. (Kloks 1996); (Brandstädt, Le & Spinrad 1999), p. 170.
16. (Golumbic & Rotics 2000).
17. (Courcelle, Makowski & Rotics 2000); (Espelage, Gurski & Wanke 2001).
18. (Hsieh et al. 2002); (Müller & Nicolai 1993).

• .
• .
• .
• ^{[halott link]}.
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

További információk

• .