Az USA Négysarok régiója. Bár a négy állam egyetlen pontban találkozik, tehát nincs nullánál nagyobb hosszúságú közös határuk, mégis szomszédos csúcsokat alkotnak a hozzájuk tartozó térképgráfban.
A sakktábla mezőinek térképgráfja, a királygráf. A sakkban a király a gráf szomszédos csúcsainak megfelelő mezők között tud mozogni.
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ó
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 Gné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]
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ámak. 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
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.
↑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.
↑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.