En la matemática disciplina de la teoría de grafos , el gráfico medial de gráfico plano G es otro gráfico M (G) que representa las adyacencias entre los bordes de las caras de G . Los gráficos mediales fueron introducidos en 1922 por Ernst Steinitz para estudiar las propiedades combinatorias de los poliedros convexos , [1] aunque Peter Tait ya utilizó la construcción inversa en 1877 en su estudio fundamental de nudos y eslabones . [2] [3]
Definicion formal
Dado un gráfico plano conectado G , su gráfico medial M (G) tiene
- un vértice para cada arista de G y
- una arista entre dos vértices para cada cara de G en la que sus aristas correspondientes ocurren consecutivamente.
La gráfica medial de una gráfica desconectada es la unión disjunta de las gráficas medial de cada componente conectado. La definición de gráfico medial también se extiende sin modificaciones a las incrustaciones de gráficos en superficies de un género superior.
Propiedades
- La gráfica medial de cualquier gráfica plana es una gráfica de 4 planos regulares .
- Para cualquier gráfico plano G , el gráfico medial de G y el gráfico medial del gráfico dual de G son isomorfos. Por el contrario, para cualquier gráfico H de 4 planos regulares , los únicos dos gráficos planos con gráfico H medial son duales entre sí. [4]
- Dado que el gráfico medial depende de una incrustación particular, el gráfico medial de un gráfico plano no es único; la misma gráfica plana puede tener gráficas mediales no isomórficas . En la imagen, los gráficos rojos no son isomórficos porque los dos vértices con bucles propios comparten un borde en un gráfico pero no en el otro.
- Cada gráfico de 4 planos regulares es el gráfico medial de algún gráfico plano. Para una gráfica H de 4 planos regulares conectados , una gráfica plana G con H como su gráfica medial se puede construir de la siguiente manera. Colorea las caras de H con solo dos colores, lo cual es posible ya que H es euleriano (y, por lo tanto, la gráfica dual de H es bipartita). Los vértices en G corresponden a las caras de un solo color en H . Estos vértices están conectados por un borde para cada vértice compartido por sus correspondientes caras en H . Tenga en cuenta que la realización de esta construcción usando las caras del otro color como los vértices produce la doble gráfica de G .
- La gráfica medial de una gráfica de 3 planos regulares coincide con su gráfica lineal . Sin embargo, esto no es cierto para las gráficas mediales de las gráficas planas que tienen vértices de grado mayor que tres.
Aplicaciones
Para un gráfico plano G , el doble de la evaluación del polinomio de Tutte en el punto (3,3) es igual a la suma sobre las orientaciones eulerianas ponderadas en el gráfico medial de G , donde el peso de una orientación es 2 al número de vértices de silla de montar de la orientación (es decir, el número de vértices con bordes incidentes ordenados cíclicamente "adentro, afuera, adentro afuera"). [5] Dado que el polinomio de Tutte es invariante bajo incrustaciones, este resultado muestra que cada gráfico medio tiene la misma suma de estas orientaciones eulerianas ponderadas.
Gráfico medial dirigido
La definición del gráfico medial se puede ampliar para incluir una orientación. Primero, las caras del gráfico medial se colorean de negro si contienen un vértice del gráfico original y de blanco en caso contrario. Este color hace que cada borde del gráfico medial esté delimitado por una cara negra y una cara blanca. Luego, cada borde se orienta de modo que la cara negra quede a su izquierda.
Un gráfico plano y su gráfico dual no tienen el mismo gráfico medial dirigido; sus gráficos mediales dirigidos son la transposición entre sí.
Utilizando el gráfico medial dirigido, se puede generalizar eficazmente el resultado de las evaluaciones del polinomio de Tutte en (3,3). Para un gráfico plano G , n veces la evaluación del polinomio de Tutte en el punto ( n +1, n +1) es igual a la suma ponderada de todos los colores de los bordes usando n colores en el gráfico medial dirigido de G de modo que cada uno (posiblemente vacío ) conjunto de aristas monocromáticas forma un grafo euleriano dirigido, donde el peso de una orientación euleriana dirigida es 2 al número de vértices monocromáticos. [6]
Ver también
- Nudos y gráficos
- Gráfico de Tait
- Rectificación (geometría) : la operación equivalente en poliedros
Referencias
- ^ Steinitz, Ernst (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathischen Wissenschaften, Band 3 (Geometrías) , págs. 1-139
- ^ Tait, Peter G. (1876–1877). "En Nudos I" . Transacciones de la Royal Society de Edimburgo . 28 : 145-190. doi : 10.1017 / S0080456800090633 .
Revisado el 11 de mayo de 1877.
- ^ Tait, Peter G. (1876–1877). "Sobre enlaces (resumen)" . Actas de la Royal Society of Edinburgh . 9 (98): 321–332. doi : 10.1017 / S0370164600032363 .
- ^ Gross, Jonathan L .; Yellen, Jay, eds. (2003). Manual de teoría de grafos . Prensa CRC. pag. 724. ISBN 978-1584880905.
- ^ Las Vergnas, Michel (1988), "Sobre la evaluación en (3, 3) del polinomio de Tutte de un grafo", Journal of Combinatorial Theory, Serie B , 35 (3): 367–372, doi : 10.1016 / 0095- 8956 (88) 90079-2 , ISSN 0095-8956
- ^ Ellis-Monaghan, Joanna A. (2004). "Identidades para polinomios de partición de circuitos, con aplicaciones al polinomio de Tutte" . Avances en Matemática Aplicada . 32 (1-2): 188-197. doi : 10.1016 / S0196-8858 (03) 00079-4 . ISSN 0196-8858 .
Otras lecturas
- Brylawski, Thomas ; Oxley, James (1992). "El polinomio de Tutte y sus aplicaciones" (PDF) . En blanco, Neil (ed.). Aplicaciones Matriod . Prensa de la Universidad de Cambridge. págs. 123–225.