Gráfico medial

En la disciplina matemática de la teoría de grafos , el grafo medial de un 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 fundamental de nudos y enlaces . ^{[ 2 ] [ 3 ]}

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

• un vértice por cada arista de G y
• una arista entre dos vértices para cada cara de G en la que sus aristas correspondientes aparecen consecutivamente.

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

• La gráfica medial de cualquier gráfica plana es una gráfica plana regular de orden 4.
• Para cualquier grafo plano conexo G , el grafo medial de G y el grafo medial del grafo dual de G son isomorfos. Recíprocamente, 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; un 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 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 , se puede construir un grafo planar G con H como su grafo medial de la siguiente manera. Coloreamos 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 compartido 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 3-regular coincide con su grafo de líneas . Sin embargo, esto no es cierto para los grafos mediales de grafos planos que tienen vértices de grado mayor que tres.

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 sobre las orientaciones eulerianas ponderadas en el grafo medial de G , donde el peso de una orientación es 2 elevado al número de vértices de silla de la orientación (es decir, el número de vértices con aristas incidentes ordenadas cíclicamente "entrada, salida, entrada salida"). ^{[ 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.

La definición del grafo medial puede ampliarse para incluir una orientación. Primero, las caras del grafo medial se colorean de negro si contienen un vértice del grafo original y de blanco en caso contrario. Esta coloración hace que cada arista del grafo medial esté delimitada por una cara negra y una cara blanca. Luego, cada arista se orienta de manera que la cara negra quede a su izquierda.

Un grafo plano y su dual no tienen el mismo grafo medial dirigido; sus grafos mediales dirigidos son la transposición uno del otro.

Utilizando el grafo medial dirigido, se puede generalizar eficazmente el resultado sobre 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 sobre todas las coloraciones de aristas usando 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 elevado al número de vértices monocromáticos. ^{[ 6 ]}

• Rectificación (geometría) : la operación equivalente en poliedros.

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