Recuento medio

Un gráfico mediano es un gráfico que representa los bordes de adyacencia dentro de las caras de un gráfico plano dado .

Formal definición

Dado un gráfico plano conexo , su gráfico central contiene: $GRAMO$ ${\ estilo de visualización M (G)}$

vértice para cada borde , $GRAMO$
un borde entre dos vértices para cada cara si los bordes del gráfico están en una fila en él. $GRAMO$ $GRAMO$

El gráfico mediano de un gráfico inconexo es una unión inconexa de los gráficos medianos de componentes conectados.

Propiedades

Dado que el gráfico de mediana depende del método de incrustación, el gráfico de mediana no es único en el sentido de que el mismo gráfico plano puede tener varios gráficos de mediana no isomorfos . Por el contrario, los gráficos no isomorfos pueden tener el mismo gráfico central. En particular, un gráfico plano y su gráfico dual tienen un gráfico central.

Los gráficos medianos son gráficos regulares de 4 . Además, cualquier gráfico plano regular de 4 es un gráfico medio de algún gráfico plano. Para un grafo planar conexo de 4 regulares , el grafo planar para el cual es un grafo medio se puede construir de la siguiente manera: las caras están coloreadas en dos colores (lo cual es posible, ya que es Euler, y dado que el dual del gráfico es bipartito ); los vértices en corresponden a caras del mismo color en . Estos vértices están conectados por una arista para cada vértice común (para dos caras) en . Nótese que haciendo esta construcción con caras de diferente color, obtenemos un grafo dual. $H$ $GRAMO$ $H$ $GRAMO$ $H$ $H$ $GRAMO$ $H$ $H$ $GRAMO$

Si dos gráficos tienen el mismo gráfico central, son duales [1] .

Gráfico de mediana dirigida

Se puede introducir una orientación en el grafo del medio : para ello, se colorea el grafo del medio con dos colores, dependiendo de si la cara del grafo del medio contiene los vértices del grafo original o no, y se introduce la orientación de tal forma que las caras de cualquiera de los colores queden a la izquierda de las aristas.

El gráfico plano y su dual tienen gráficos medianos dirigidos diferentes que son inversos entre sí.

El polinomio de Tatta

Para un gráfico plano , el valor doble del polinomio de Tatta en el punto (3,3) es igual a la suma de las orientaciones de Euler ponderadas en el gráfico central , donde el peso de la orientación es ( es el número de silla de vértices de la orientación, es decir, el número de vértices cuyos arcos incidentes están ordenados por ciclo "entrante - saliente - entrante - saliente") [2] . Dado que el polinomio de Tutta es un invariante de incrustación, el resultado muestra que para un gráfico dado, cualquier gráfico mediano tiene la misma suma ponderada de orientaciones de Euler. $GRAMO$ $GRAMO$ ${\ estilo de visualización 2 ^ {s}}$ $s$

Usando un gráfico de mediana dirigida, uno puede generalizar efectivamente el resultado de calcular el polinomio de Tatta en el punto (3,3). Para un gráfico plano , multiplicado por el valor del polinomio de Tutt en el punto es igual a la suma ponderada de todas las coloraciones de los arcos en colores en el gráfico mediano orientado del gráfico , de modo que cada conjunto (posiblemente vacío) de arcos del mismo color forma un gráfico de Euler orientado, donde el peso de la orientación de Euler es ( es el número de vértices monocromáticos, es decir, vértices, los cuatro bordes incidentes a los cuales tienen el mismo color) [3] [4] . $GRAMO$ $norte$ ${\ estilo de visualización (n + 1, n + 1)}$ $norte$ $GRAMO$ ${\ estilo de visualización 2 ^ {s}}$ $s$

Notas

↑ Manual de teoría de grafos / Jonathan L. Gross, Jay Yellen. - CRC Press, 2003. - Pág. 724. - ISBN 978-1584880905 .
↑ Michel Las Vergnas. Sobre la evaluación en (3, 3) del polinomio de Tutte de un grafo // Journal of Combinatorial Theory, Serie B. - 1988. - Vol. 35 , no. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
↑ Joanna A. Ellis-Monaghan. Identidades para polinomios de partición de circuitos, con aplicaciones al polinomio de Tutte // Avances en Matemáticas Aplicadas. - 2004. - T. 32 , núm. 1-2 . - S. 188-197 . — ISSN 0196-8858 . - doi : 10.1016/S0196-8858(03)00079-4 .
↑ Michael Korn, Igor Pak. Evaluaciones combinatorias del polino de Tutte. — 2003, preimpresión. — P. 4, Coloreando los bordes del gráfico medial .

Literatura

Thomas Brylawski, James Oxley. Aplicaciones Matriod / Neil White. - Cambridge University Press, 1992. - S. 123-225.