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 egy síkbarajzolható páros gráf, a bipartíció legyen . A négyzete a 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 -ben. A gráf félnégyzete a gráf négyzetében a bipartíció egyik felének (mondjuk -nek) a feszített részgráfja: csúcshalmaza a , és azon csúcsai között szerepelnek élek, melyek két lépés távolságra vannak -ben. Ez a félnégyzet egy térképgráf. Mértanilag úgy is ábrázolható, hogy -nek megkeressük egy síkba rajzolását, majd 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 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 (), 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 -térképgráf olyan régiók halmazából állítható elő, melyek közül legfeljebb találkozik egyetlen pontban. Ezzel ekvivalens megfogalmazás szerint egy páros síkbarajzolható gráf félnégyzete, melyben az csúcshalmaz (a bipartíció azon fele, mely nem vett részt a félnégyzet-műveletben) maximális fokszáma . 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
Jegyzetek
Kategória:Síkgráfok Kategória:Gráfcsaládok