Térképgráf

A felső térképgráf, ami egyben a K_2,2,2,2 Turán-gráf, definiálható egyrészt a sík nyolc régiójának sarokszomszédságai alapján (balra lent), másrészt egy páros síkgráf, a rombododekaéder gráfjának (jobbra lent) félnégyzeteként

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

Számítási bonyolultság

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 ($n^{1}20$), hogy a gyakorlatban nem praktikus a használata. 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ő. 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.

Változatok és kapcsolódó fogalmak

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.

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.