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.

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.

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.

• 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]

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]

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]

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

• "Distance-hereditary graphs", Information System on Graph Classes and their Inclusions, <http://www.graphclasses.org/classes/gc_80.html>.