Gráfica medial

En la disciplina matemática de la teoría de grafos , el grafo medial del grafo plano G es otro grafo M(G) que representa las adyacencias entre aristas en las caras de G. Los grafos mediales fueron introducidos en 1922 por Ernst Steinitz para estudiar las propiedades combinatorias de los poliedros convexos , ^[1] aunque la construcción inversa ya fue utilizada por Peter Tait en 1877 en su estudio fundacional de los nudos y enlaces . ^[2]^[3]

Definición formal

Dado un grafo plano conexo G , su grafo medial M(G) tiene

un vértice para cada arista de G y
un borde entre dos vértices para cada cara de G en el que sus bordes correspondientes ocurren consecutivamente.

El grafo medial de un grafo desconectado es la unión disjunta de los grafos mediales de cada componente conectado. La definición de grafo medial también se extiende sin modificaciones a las incrustaciones de grafos en superficies de género superior.

Propiedades

El gráfico medial de cualquier gráfico plano es un gráfico plano regular de 4 ejes .
Para cualquier grafo plano G , el grafo medial de G y el grafo medial del grafo dual de G son isomorfos. Por el contrario, para cualquier grafo plano 4-regular H , los únicos dos grafos planos con grafo medial H son duales entre sí. ^[4]
Dado que el grafo medial depende de una incrustación particular, el grafo medial de un grafo planar no es único; el mismo grafo planar puede tener grafos mediales no isomorfos . En la imagen, los grafos rojos no son isomorfos porque los dos vértices con bucles propios comparten una arista en un grafo pero no en el otro.
Todo grafo plano 4-regular es el grafo medial de algún grafo plano. Para un grafo plano 4-regular conexo H , un grafo planar G con H como su grafo 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 el grafo dual de H es bipartito). Los vértices en G corresponden a las caras de un solo color en H . Estos vértices están conectados por una arista para cada vértice compartida por sus caras correspondientes en H . Nótese que realizar esta construcción usando las caras del otro color como vértices produce el grafo dual de G .
El grafo medial de un grafo plano regular 3 coincide con su grafo lineal . Sin embargo, esto no es cierto para los grafos mediales de grafos planos que tienen vértices de grado mayor que tres.

Aplicaciones

Para un grafo plano G , el doble de la evaluación del polinomio de Tutte en el punto (3,3) es igual a la suma de las orientaciones eulerianas ponderadas en el grafo 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 aristas incidentes ordenadas cíclicamente "dentro, afuera, adentro afuera"). ^[5] Dado que el polinomio de Tutte es invariante bajo incrustaciones, este resultado muestra que cada grafo medial tiene la misma suma de estas orientaciones eulerianas ponderadas.

Grafo medial dirigido

La definición del gráfico medial se puede ampliar para incluir una orientación. En primer lugar, 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. Esta coloración 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 esté a su izquierda.

Un grafo plano y su dual no tienen el mismo grafo medial dirigido; sus grafos mediales dirigidos son la transpuesta entre sí.

Utilizando el grafo medial dirigido, se puede generalizar efectivamente el resultado de las evaluaciones del polinomio de Tutte en (3,3). Para un grafo 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 todas las coloraciones de aristas utilizando n colores en el grafo medial dirigido de G, de modo que cada conjunto (posiblemente vacío) 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]

Véase también

Nudos y gráficos
Rectificación (geometría) - La operación equivalente en poliedros

Referencias

^ Steinitz, Ernst (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometrías) , págs.
^ Tait, Peter G. (1876–1877). "Sobre los nudos I". Transacciones de la Royal Society de Edimburgo . 28 : 145–190. doi :10.1017/S0080456800090633. S2CID 171186257. Revisado el 11 de mayo de 1877.
^ Tait, Peter G. (1876–1877). "Sobre vínculos (resumen)". Actas de la Royal Society de Edimburgo . 9 (98): 321–332. doi :10.1017/S0370164600032363.
^ Gross, Jonathan L.; Yellen, Jay, eds. (2003). Manual de teoría de grafos. CRC Press. pág. 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áticas Aplicadas . 32 (1–2): 188–197. doi :10.1016/S0196-8858(03)00079-4. ISSN 0196-8858.

Lectura adicional

Brylawski, Thomas ; Oxley, James (1992). "El polinomio de Tutte y sus aplicaciones" (PDF) . En White, Neil (ed.). Aplicaciones de Matriod . Cambridge University Press. págs. 123–225.