Fórmula de eliminación-contracción

Fórmula en teoría de grafos

En teoría de grafos , una fórmula/recursión de eliminación-contracción es cualquier fórmula de la siguiente forma recursiva :

${\displaystyle f(G)=f(G\setminus e)+f(G/e).}$

Aquí G es un gráfico, f es una función en gráficos, e es cualquier borde de G , G  \  e denota eliminación de borde y G  /  e denota contracción . Tutte se refiere a dicha función como función W. ^[1] La fórmula a veces se denomina teorema de reducción fundamental . ^[2] En este artículo la abreviamos como DC .

RM Foster ya había observado que el polinomio cromático es una de esas funciones, y Tutte comenzó a descubrir más, incluida una función f  =  t ( G ) que cuenta el número de árboles generadores de un gráfico (ver también el teorema de Kirchhoff ). Más tarde se descubrió que el polinomio de flujo es otro más; y pronto Tutte descubrió toda una clase de funciones llamadas polinomios de Tutte (originalmente denominados dicromatos ) que satisfacen DC. ^[1]

Ejemplos

Árboles de expansión

El número de árboles de expansión satisface DC. ^[3] ${\displaystyle t(G)}$

Prueba. denota el número de árboles de expansión que no incluyen e , mientras que el número que incluye e . Para ver el segundo, si T es un árbol generador de G, entonces al contraer e se produce otro árbol generador de . Por el contrario, si tenemos un árbol de expansión T de , entonces expandir el borde e da dos árboles desconectados; agregar e conecta los dos y da un árbol de expansión de  G . ${\displaystyle t(G\setminus e)}$ ${\displaystyle t(G/e)}$ ${\displaystyle G/e}$ ${\displaystyle G/e}$

Polinomios cromáticos

El polinomio cromático que cuenta el número de k -coloraciones de G no satisface DC, pero sí una fórmula ligeramente modificada (que puede hacerse equivalente): ^[1] ${\displaystyle \chi _{G}(k)}$

${\displaystyle \chi _{G}(k)=\chi _{G-e}(k)-\chi _{G/e}(k).}$

Prueba. Si e = uv , entonces una k -coloración de G es la misma que una k -coloración de G  \  e donde u y v tienen colores diferentes. Hay coloraciones totales G  \  e . Ahora necesitamos restar aquellos en los que u y v tienen colores similares. Pero tales coloraciones corresponden a las k -coloraciones de donde u y v se fusionan. ${\displaystyle \chi _{G\setminus e}(k)}$ ${\displaystyle \chi _{G/e}(k)}$

Esta propiedad anterior se puede utilizar para demostrar que el polinomio cromático es de hecho un polinomio en  k . Podemos hacer esto mediante inducción sobre el número de aristas y observando que en el caso base donde no hay aristas, hay posibles coloraciones (que es un polinomio en  k ). ${\displaystyle \chi _{G}(k)}$ ${\displaystyle k^{|V(G)|}}$

Algoritmo de contracción de eliminación

Ver también

• Principio de inclusión-exclusión
• polinomio tutte
• Polinomio cromático
• Flujo cero en ninguna parte

Citas

1. Tutte, WT (enero de 2004). "Gráficos-polinomios". Avances en Matemática Aplicada . 32 (1–2): 5–9. doi : 10.1016/S0196-8858(03)00041-1 .
2. Dong, Koh y Teo (2005)
3. "Deleción-contracción y polinomios cromáticos" (PDF) . Archivado desde el original (PDF) el 4 de mayo de 2019.

Trabajos citados

• Dong, FM; Koh, KM; Teo, KL (junio de 2005). Polinomios cromáticos y cromaticidad de gráficos . Científico mundial. doi :10.1142/5814. ISBN 978-981-256-317-0.