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

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

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 (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.[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 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.[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).
  • Bandelt, Hans-Jürgen & Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B 41 (2): 182–208, DOI 10.1016/0095-8956(86)90043-2.
  • Brandstädt, Andreas; Le, Van Bang & Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Cogis, O. & Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization 2 (2): 185–188, DOI 10.1016/j.disopt.2005.03.004.
  • Cornelsen, Sabine & Di Stefano, Gabriele (2005), "Treelike comparability graphs: characterization, recognition, and applications", Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004), vol. 3353, Lecture Notes in Computer Science, Springer-Verlag, pp. 46–57, <http://www.springerlink.com/content/79g3m7hn12wt1v14/>[halott link].
  • Courcelle, B.; Makowski, J. A. & Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems 33 (2): 125–150, DOI 10.1007/s002249910009.
  • D'Atri, Alessandro & Moscarini, Marina (1988), "Distance-hereditary graphs, Steiner trees, and connected domination", SIAM Journal on Computing 17 (3): 521–538, DOI 10.1137/0217032.
  • Damiand, Guillaume; Habib, Michel & Paul, Christophe (2001), "A simple paradigm for graph recognition: application to cographs and distance hereditary graphs", Theoretical Computer Science 263 (1–2): 99–111, DOI 10.1016/S0304-3975(00)00234-6.
  • Eppstein, David; Goodrich, Michael T. & Meng, Jeremy Yu (2006), "Delta-confluent drawings", in Healy, Patrick & Nikolov, Nikola S., Proc. 13th Int. Symp. Graph Drawing (GD 2005), vol. 3843, Lecture Notes in Computer Science, Springer-Verlag, pp. 165–176.
  • Espelage, W.; Gurski, F. & Wanke, E. (2001), "How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time", Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001), vol. 2204, Lecture Notes in Computer Science, Springer-Verlag, pp. 117–128.
  • Gioan, Emeric & Paul, Christophe (2012), "Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics 160 (6): 708–733, DOI 10.1016/j.dam.2011.05.007.
  • Golumbic, Martin Charles & Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science 11 (3): 423–443, DOI 10.1142/S0129054100000260.
  • Hammer, Peter Ladislaw & Maffray, Frédéric (1990), "Completely separable graphs", Discrete Applied Mathematics 27 (1–2): 85–99, DOI 10.1016/0166-218X(90)90131-U.
  • Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics. Oxford. Second Series 28 (112): 417–420, doi:10.1093/qmath/28.4.417, <http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417>.
  • Hsieh, Sun-yuan; Ho, Chin-wen & Hsu, Tsan-sheng et al. (2002), "Efficient algorithms for the Hamiltonian problem on distance-hereditary graphs", Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002, Proceedings, vol. 2387, Lecture Notes in Computer Science, Springer-Verlag, pp. 51–75, ISBN 978-3-540-43996-7, DOI 10.1007/3-540-45655-4_10.
  • Hui, Peter; Schaefer, Marcus & Štefankovič, Daniel (2004), "Train tracks and confluent drawings", in Pach, János, Proc. 12th Int. Symp. Graph Drawing (GD 2004), vol. 3383, Lecture Notes in Computer Science, Springer-Verlag, pp. 318–328.
  • Kloks, T. (1996), "Treewidth of circle graphs", International Journal of Foundations of Computer Science 7 (2): 111–120, DOI 10.1142/S0129054196000099.
  • Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics 2 (3): 253–267, DOI 10.1016/0012-365X(72)90006-4.
  • McKee, Terry A. & McMorris, F. R. (1999), Topics in Intersection Graph Theory, vol. 2, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3
  • Müller, Haiko & Nicolai, Falk (1993), "Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs", Information Processing Letters 46 (5): 225–230, DOI 10.1016/0020-0190(93)90100-N.
  • Oum, Sang-il (2005), "Rank-width and vertex-minors", Journal of Combinatorial Theory, Series B 95 (1): 79–100, DOI 10.1016/j.jctb.2005.03.003.
  • Sachs, Horst (1970), "On the Berge conjecture concerning perfect graphs", Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, pp. 377–384.

További információk

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