En la teoría de grafos , una rama de las matemáticas, un gráfico de mapa es un gráfico no dirigido formado como el gráfico de intersección de un número finito de regiones simplemente conectadas e internamente disjuntas del plano euclidiano . Los gráficos de mapa incluyen los gráficos planos , pero son más generales. Cualquier número de regiones puede encontrarse en una esquina común (como en las Cuatro Esquinas de los Estados Unidos, donde se encuentran cuatro estados), y cuando lo hagan, el gráfico de mapa contendrá una camarilla que conecta los vértices correspondientes, a diferencia de los gráficos planos en los que el mayor las camarillas tienen sólo cuatro vértices. [1] Otro ejemplo de un gráfico de mapa es elgráfico del rey , un gráfico de mapa de los cuadrados del tablero de ajedrez que conecta pares de cuadrados entre los cuales puede moverse el rey del ajedrez.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/8c/Map_graph.svg/300px-Map_graph.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/f/fd/King%27s_graph.svg/200px-King%27s_graph.svg.png)
Representación combinatoria
Los gráficos de mapa se pueden representar de forma combinatoria como los "medios cuadrados de los gráficos bipartitos planos". Es decir, sea G = ( U , V , E ) un gráfico bipartito plano , con bipartición ( U , V ) . El cuadrado de G es otro gráfico en el mismo conjunto de vértices, en el que dos vértices son adyacentes en la plaza cuando están en la mayoría de los dos pasos separados en G . El medio-cuadrado o medio bipartito es el subgrafo inducido de un lado de la bipartición (digamos V ) en el gráfico cuadrado: su conjunto de vértices es V y tiene un borde entre cada dos vértices en V que son dos pasos de separación, en G . El medio cuadrado es un gráfico de mapa. Se puede representar geométricamente mediante la búsqueda de un planar incrustación de G , y la expansión de cada vértice de V y sus bordes adyacentes en una región en forma de estrella, de modo que estas regiones se tocan en los vértices de U . Por el contrario, cada gráfico de mapa se puede representar como un medio cuadrado de esta manera. [1]
Complejidad computacional
En 1998, Mikkel Thorup afirmó que los gráficos de mapas se pueden reconocer en tiempo polinomial . [2] Sin embargo, el alto exponente del algoritmo que esbozó lo hace poco práctico, y Thorup no ha publicado los detalles de su método y su prueba. [3]
El problema del conjunto independiente máximo tiene un esquema de aproximación de tiempo polinomial para gráficos de mapa, y el número cromático puede aproximarse dentro de un factor de dos en tiempo polinomial. [4] La teoría de la bidimensionalidad conduce a muchos otros algoritmos de aproximación y algoritmos manejables de parámetros fijos para problemas de optimización en gráficos de mapas. [5] [6] [7]
Un gráfico de mapa k es un gráfico de mapa derivado de un conjunto de regiones en las que como máximo k regiones se encuentran en cualquier punto. De manera equivalente, es el medio cuadrado de un gráfico bipartito plano en el que el conjunto de vértices U (el lado de la bipartición no utilizado para inducir el medio cuadrado) tiene un grado máximo k . Un gráfico de 3 mapas es un gráfico plano y cada gráfico plano se puede representar como un gráfico de 3 mapas. Cada gráfico de 4 mapas es un gráfico de 1 plano , un gráfico que se puede dibujar con como máximo un cruce por borde y cada gráfico de 1 plano óptimo (un gráfico formado a partir de una cuadrangulación plana al agregar dos diagonales de cruce a cada cara de cuadrilátero ) es un gráfico de 4 mapas. Sin embargo, algunos otros gráficos de 1 plano no son gráficos de mapa porque (a diferencia de los gráficos de mapa) incluyen bordes cruzados que no forman parte de un subgráfico completo de cuatro vértices. [1]
Referencias
- ^ a b c Chen, Zhi-Zhong; Grigni, Miguel Ángel; Papadimitriou, Christos H. (2002), "Gráficos de mapa", Journal of the ACM , 49 (2): 127-138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819.
- ^ Thorup, Mikkel (1998), "Gráficos de mapas en tiempo polinomial", Actas del 39º Simposio anual sobre los fundamentos de la informática (FOCS 1998) , págs. 396–405, doi : 10.1109 / SFCS.1998.743490 , ISBN 978-0-8186-9172-0.
- ^ Brandenburg, Franz J. (agosto de 2018), "Caracterización y reconocimiento de gráficos de 4 mapas", Algorithmica , doi : 10.1007 / s00453-018-0510-x
- ^ Chen, Zhi-Zhong (2001), "Algoritmos de aproximación para conjuntos independientes en gráficos de mapa", Journal of Algorithms , 41 (1): 20–40, doi : 10.1006 / jagm.2001.1178 , MR 1855346.
- ^ Demaine, Erik D .; Fomin, Fedor V .; Hajiaghayi, Mohammadtaghi ; Thilikos, Dimitrios M. (2005), "Algoritmos de parámetros fijos para ( k , r ) -center en gráficos planos y gráficos de mapa", ACM Transactions on Algorithms , 1 (1): 33–47, CiteSeerX 10.1.1.113.2070 , doi : 10.1145 / 1,077,464.1077468 , MR 2163129.
- ^ Demaine, Erik D .; Hajiaghayi, Mohammadtaghi (2007), "La teoría de la bidimensionalidad y sus aplicaciones algorítmicas", The Computer Journal , 51 (3): 292–302, doi : 10.1093 / comjnl / bxm033 , hdl : 1721.1 / 33090.
- ^ Fomin, Fedor V .; Lokshtanov, Daniel; Saurabh, Saket (2012), "Bidimensionality and geometric graphs", Actas del Vigésimo Tercer Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA 2012) , pp. 1563-1575, arXiv : 1107.2221 , doi : 10.1137 / 1.9781611973099.124 , ISBN 978-1-61197-210-8, MR 3205314.