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). 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.

A távolság-örökletes gráfokat 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.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 (, Theorem 5). bebizonyította, hogy az α-perfektség a perfekt gráfok definíciójával ekvivalens.

Egy ideje ismert volt, hogy a távolságtartó gráfok a metszetgráfok alapján meghatározott gráfosztályok közé tartoznak, de a működő metszetgráf-meghatározással adósak voltak a matematikusok 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:; ; ; , Theorem 10.1.1, p. 147.

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.

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): Egy új, „függő csúcs” (pendant vertex) hozzáadása, mely a gráf egy létező csúcsához csatlakozik egyetlen éllel. 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. 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 (K1,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.. Egy hasonló felbontási módszert gráf lerajzolásához használt , páros távolság-örökletes gráfokhoz pedig . 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..

Más gráfcsaládokkal való kapcsolata Minden távolság-örökletes gráf perfekt,. azon belül perfekt rendezhető pp. 70–71 and 82. é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)., p.45. A G távolság-örökletes gráf minden páros hatványa (tehát a G2i 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., Theorem 10.6.14, p.164.

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.Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

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..

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.; . Már korábban, bejelentette a lineáris idejű algoritmust, de később Damiand hibákat talált a cikkben.

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. 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 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 lexikográfiai szélességi keresés alkalmazásával, majd mohó színezési algoritmussal. 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.; , p. 170. Bármely távolság-örökletes gráf klikkszélessége legfeljebb három.. 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.; .

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 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.; .

Fordítás

Jegyzetek

Források . . . . . . . . . . . . . . . . .

. . .

További információk .

Kategória:Gráfcsaládok Kategória:Perfekt gráfok Kategória:Metszetgráfok alapján meghatározott gráfosztályok