Mapový graf - Map graph

Mapový graf (nahoře), koktejlový večírek graf K.2,2,2,2, definovaný rohovou sousedností osmi oblastí v rovině (vlevo dole), nebo jako půlčtverec rovinného bipartitního grafu (vpravo dole, graf kosočtverečný dvanáctistěn )
The Čtyři rohy USA. I když se tyto čtyři stavy setkávají v určitém bodě, místo sdílení hranice nenulové délky tvoří sousední vrcholy v odpovídajícím mapovém grafu.
The králův graf, mapový graf čtverců šachovnice. Šachový král se může pohybovat mezi dvěma sousedními vrcholy tohoto grafu.

v teorie grafů, obor matematiky, a mapový graf je neorientovaný graf vytvořen jako průsečíkový graf konečně mnoha jednoduše propojených a vnitřně disjunktních oblastí Euklidovské letadlo. Mapové grafy obsahují rovinné grafy, ale jsou obecnější. Na společném rohu se může setkat libovolný počet regionů (jako v EU) Čtyři rohy Spojených států, kde se setkávají čtyři státy), a když tak učiní, graf mapy bude obsahovat a klika spojování odpovídajících vrcholů, na rozdíl od rovinných grafů, ve kterých největší kliky mají pouze čtyři vrcholy.[1] Dalším příkladem mapového grafu je králův graf, mapový graf čtverců šachovnice spojující páry čtverců, mezi kterými se může šachový král pohybovat.

Kombinatorické znázornění

Mapové grafy lze kombinatoricky reprezentovat jako „poloviční čtverce rovinných bipartitních grafů“. To je, pojďme G = (U,PROTI,E) být rovinný bipartitní graf, s biparticí (U,PROTI). The náměstí z G je další graf na stejné množině vrcholů, ve kterém dva vrcholy sousedí ve čtverci, když jsou od sebe nejvýše dva kroky G. Půl čtverec nebo bipartitní polovina je indukovaný podgraf jedné strany bipartice (řekněme PROTI) ve čtvercovém grafu: jeho sada vrcholů je PROTI a má hranu mezi každým dvěma vrcholy dovnitř PROTI to jsou dva kroky od sebe G. Poločtverec je mapový graf. To může být reprezentováno geometricky nalezením a rovinné vkládání z Ga rozšiřování každého vrcholu PROTI a jeho přilehlé okraje do oblasti ve tvaru hvězdy, takže se tyto oblasti dotýkají vrcholů U. Naopak, každý mapový graf lze tímto způsobem reprezentovat jako půlčtverec.[1]

Výpočetní složitost

V roce 1998 Mikkel Thorup tvrdil, že mapové grafy lze rozpoznat v polynomiální čas.[2] Vysoký exponent algoritmu, který nakreslil, je však nepraktický a Thorup nezveřejnil podrobnosti o své metodě a její důkaz.[3]

The maximální nezávislá sada problém má schéma aproximace v polynomiálním čase pro mapové grafy a chromatické číslo lze v polynomiálním čase aproximovat s faktorem dva.[4] Teorie dvojrozměrnost vede k mnoha dalším aproximačním algoritmům a fixovatelný parametr algoritmy pro optimalizaci problémů na mapových grafech.[5][6][7]

Variace a související pojmy

A k-mapový graf je mapový graf odvozený od množiny oblastí, ve kterých nanejvýš k regiony se setkávají kdykoli. Ekvivalentně je to poloviční čtverec rovinného bipartitního grafu, ve kterém se vrchol nastavil U (strana bipartice, která se nepoužívá k vyvolání polovičního čtverce) má maximum stupeň k. 3mapový graf je a rovinný graf a každý rovinný graf lze reprezentovat jako 3mapový graf. Každý 4mapový graf je a 1-rovinný graf, graf, který lze nakreslit maximálně jedním křížením na hranu, a každý optimální 1-rovinný graf (graf vytvořený z rovinné kvadrangulace přidáním dvou úhlopříček křížení ke každé čtyřúhelníkové ploše) je graf se 4 mapami. Některé další 1-rovinné grafy však nejsou mapovými grafy, protože (na rozdíl od mapových grafů) obsahují hraniční přechody, které nejsou součástí úplného podgrafu se čtyřmi vrcholy.[1]

Reference

  1. ^ A b C Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Mapové grafy", Deník ACM, 49 (2): 127–138, arXiv:cs / 9910013, doi:10.1145/506147.506148, PAN  2147819.
  2. ^ Thorup, Mikkel (1998), „Mapovat grafy v polynomiálním čase“, Sborník 39. výroční sympozia o základech informatiky (FOCS 1998), str. 396–405, doi:10.1109 / SFCS.1998.743490, ISBN  978-0-8186-9172-0.
  3. ^ Brandenburg, Franz J. (srpen 2018), „Charakterizace a rozpoznávání 4-mapových grafů“, Algorithmica, doi:10.1007 / s00453-018-0510-x
  4. ^ Chen, Zhi-Zhong (2001), „Aproximační algoritmy pro nezávislé množiny v mapových grafech“, Journal of Algorithms, 41 (1): 20–40, doi:10.1006 / jagm.2001.1178, PAN  1855346.
  5. ^ Demaine, Erik D.; Fomin, Fedor V .; Hajiaghayi, Mohammadtaghi; Thilikos, Dimitrios M. (2005), „Algoritmy s pevnými parametry pro (k,r)-centrum v rovinných a mapových grafech ", Transakce ACM na algoritmech, 1 (1): 33–47, CiteSeerX  10.1.1.113.2070, doi:10.1145/1077464.1077468, PAN  2163129.
  6. ^ Demaine, Erik D.; Hajiaghayi, Mohammadtaghi (2007), „The Bidimensionality Theory and its Algorithmic Applications“, Počítačový deník, 51 (3): 292–302, doi:10.1093 / comjnl / bxm033, hdl:1721.1/33090.
  7. ^ Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket (2012), „Bimenzionalita a geometrické grafy“, Sborník dvacátého třetího ročníku sympozia ACM-SIAM o diskrétních algoritmech (SODA 2012), str. 1563–1575, arXiv:1107.2221, doi:10.1137/1.9781611973099.124, ISBN  978-1-61197-210-8, PAN  3205314.