Térképgráf
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8c/Map_graph.svg/300px-Map_graph.svg.png)
A matematika, azon velül a gráfelmélet területén egy térképgráf (map graph) az euklideszi sík véges sok darab, egyszerűen összefüggő, belső részüket tekintve diszjunkt régiójának metszetgráfja. A térképgráfok közé tartoznak a síkbarajzolható gráfok, de annál általánosabb fogalom. Akárhány régió találkozhat egyetlen közös pontban (mint az USA Négysarok régiója, ahol négy állam találkozik), és ilyenkor a térképgráf a megfelelő csúcsok alkotta klikket fog tartalmazni, a síkgráfoktól eltérően, ahol a legnagyobb klikkek csak négy csúcsból állhatnak.[1] A térképgráfok egy másik példája a királygráf, a sakktábla mezőinek térképgráfja, ami azokat a mezőknek megfelelő csúcsokat köti össze, melyek között a király mozoghat.
Kombinatorikai reprezentáció
[szerkesztés]A térképgráfok kombinatorikailag kifejezhetők „páros síkbarajzolható gráfok félnégyzeteiként”. Legyen G = (U,V,E) egy síkbarajzolható páros gráf, a bipartíció legyen (U,V). A G négyzete a G csúcshalmazával rendelkező olyan gráf, melyben két csúcs akkor szomszédos, ha legfeljebb két lépés távolságra vannak G-ben. A gráf félnégyzete a gráf négyzetében a bipartíció egyik felének (mondjuk V-nek) a feszített részgráfja: csúcshalmaza a V, és V azon csúcsai között szerepelnek élek, melyek két lépés távolságra vannak G-ben. Ez a félnégyzet egy térképgráf. Mértanilag úgy is ábrázolható, hogy G-nek megkeressük egy síkba rajzolását, majd V minden csúcsát és a velük szomszédos éleket csillag alakú régióvá növesztjük úgy, hogy ezek a régiók U csúcsaiban érintkezzenek. Megfordítva, minden térképgráfnak létezik ilyen félnégyzet-reprezentációja.[1]
Számítási bonyolultság
[szerkesztés]A térképgráfok felismerésére létezik polinom idejű algoritmus, az eddig ismert legjobb ilyen algoritmus azonban olyan magas kitevővel rendelkezik (), hogy a gyakorlatban nem praktikus a használata.[2] A maximális elemszámú független csúcshalmaz problémának térképgráfok esetében van polinomiális approximációs sémája, és a kromatikus számuk is 2 faktorral polinom időben becsülhető.[3] A bidimenzionalitás-elmélet segítségével a térképgráfok optimalizálási problémáinak számos más közelítő algoritmusához és rögzített paraméter mellett kezelhető algoritmusához jutottak el.[4][5][6]
Változatok és kapcsolódó fogalmak
[szerkesztés]Egy k-térképgráf olyan régiók halmazából állítható elő, melyek közül legfeljebb k találkozik egyetlen pontban. Ezzel ekvivalens megfogalmazás szerint egy páros síkbarajzolható gráf félnégyzete, melyben az U csúcshalmaz (a bipartíció azon fele, mely nem vett részt a félnégyzet-műveletben) maximális fokszáma k. A 3-térképgráfok mind síkbarajzolhatók, és minden síkbarajzolható gráfnak van 3-térképgráf reprezentációja. Minden 4-térképgráf 1-síkgráf, azaz élenként legfeljebb egy metszéssel lerajzolható gráf, és minden optimális 1-síkgráf (a sík egy négyszögeléséből minden négyszögű tartományhoz két metsző átló hozzáadásával kapott gráf) pedig 4-térképgráf. A nem optimális 1-síkgráfok azonban nem térképgráfok, mert (a térképgráfoktól eltérően) tartalmaznak olyan metsző éleket, melyek nem egy 4 csúcsú klikk részei.[1]
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Map 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
[szerkesztés]- ↑ a b c Chen, Zhi-Zhong; Grigni, Michelangelo & Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM 49 (2): 127–138, DOI 10.1145/506147.506148.
- ↑ Thorup, Mikkel (1998), "Map graphs in polynomial time", Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 396–405, DOI 10.1109/SFCS.1998.743490.
- ↑ Chen, Zhi-Zhong (2001), "Approximation algorithms for independent sets in map graphs", Journal of Algorithms 41 (1): 20–40, DOI 10.1006/jagm.2001.1178.
- ↑ Demaine, Erik D.; Fomin, Fedor V. & Hajiaghayi, Mohammadtaghi et al. (2005), "Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs", ACM Transactions on Algorithms 1 (1): 33–47, DOI 10.1145/1077464.1077468.
- ↑ Demaine, Erik D. & Hajiaghayi, Mohammadtaghi (2007), "The Bidimensionality Theory and Its Algorithmic Applications", The Computer Journal 51 (3): 292–302, DOI 10.1093/comjnl/bxm033.
- ↑ Fomin, Fedor V.; Lokshtanov, Daniel & Saurabh, Saket (2012), "Bidimensionality and geometric graphs", Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1563–1575, DOI 10.1137/1.9781611973099.124.