Mapa de grafo codificat

Archiu:Graph-encoded map.svg

Un mapa de grafo codificat (triànguls grisos i vores coloreados) d'un grafo en el pla (círculs blancs i vores negres)

En teoria de grafos topològica, un mapa de grafo codificat o GEM (per les inicials del seu nom en anglés: Graph Encoded Map) és un método per a codificar un embebidocelular d'un grafo usant un grafo diferent en quatre vèrtiços per víncul a partir del grafo original. És l'anàlec topològic d'una runcinación, una operació geomètrica sobre poliedres. Els mapes codificats en grafos varen ser formulats i nomenats per Lins (1982).

Els sistemes alternatius i equivalents per a representar embebidos celulars inclouen als sistemes de rotació i als grafos de cinta en signe.

El mapa d'un grafo codificat per a un grafo embebido $G$ és un atre grafo cúbic $H$ junt en un 3-coloreado d'arestes de $H$. Cada aresta $e$ de $G$ s'expandix en exactament quatre vèrtiços en $H$, un per a cada opció de costat i el punt final de l'aresta. Una aresta en $H$ conecta cada vèrtiç en el vèrtiç que representa el costat opost i el mateix extrem de $e$. Estes vores són per convenció de color roig. Una atra vora en $H$ conecta cada vèrtiç en el vèrtiç que representa l'extrem opost i el mateix costat de $e$; estes vores són per convenció de color blau. Una aresta en $H$ del tercer color, groc, conecta cada vèrtiç en el vèrtiç que representa una atra aresta $e^{\prime }$ que es troba en $e$ en el mateix costat i punt final.

Una descripció alternativa de $H$ és que té un vèrtiç per a cada bandera de $G$ (una triple incidència mútua d'un vèrtiç, una aresta i una cara). Si $(v,e,f)$ és una bandera, llavors hi ha exactament un vèrtiç $v^{\prime }$, una aresta $e^{\prime }$ i una cara $f^{\prime }$ tals que $(v^{\prime },e,f)$, $(v,e^{\prime },f)$ i $(v,e,f^{\prime })$ també són banderes. Els tres colors de les vores en $H$ representen cada u d'estos tres tipos de banderes que es diferencien per un dels seus tres elements. No obstant, interpretar un mapa codificat en grafos d'esta manera requerix més cuidat. Quan apareix la mateixa cara a abdós costats d'una aresta, com pot ocórrer, per eixemple, en un embebido pla d'un arbre, els dos costats donen lloc a diferents vèrtiços de el GEM. I quan el mateix vèrtiç apareix en abdós extrems d'un bucle, els dos extrems de l'aresta novament donen lloc a diferents vèrtiços de el GEM. D'esta forma, cada tripleta $(v,e,f)$ podrà associar-se en fins a quatre vèrtiços diferents del mapa de grafo codificat.

Sempre que un grafo cúbic $H$ puga tindre 3 colors de vora, de modo que els cicles roig-blau del coloreado tinguen una llongitut de quatre, el grafo coloreado pot interpretar-se com un mapa de grafo codificat i representa un embebido d'un atre grafo $G$.

Per a recuperar $G$ i el seu embebido, es deu interpretar cada cicle de 2 colors de $H$ com la cara d'una incrustación de $H$ en una superfície, contraent cada cicle roig-groc en un sol vèrtiç de $G$, i reemplaçant cada parell de vores blaves paraleles deixats per la contracció en una sola vora de $G$.

El grafo dual d'un mapa de grafo codificat es pot obtindre del mapa canviant-ho de color per a que les vores roges de el GEM es tornen blaus i les vores blaves es tornen rojos.