En teoría de grafos , una fórmula de contracción-eliminación/recursión es cualquier fórmula de la siguiente forma recursiva :
Aquí G es un grafo, f es una función en grafos, e es cualquier arista de G , G \ e denota eliminación de arista y G / e denota contracción . Tutte se refiere a dicha función como una 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 de expansión de un grafo (véase también el teorema de Kirchhoff ). Más tarde se descubrió que el polinomio de flujo es otro más; y pronto Tutte descubrió una clase completa de funciones llamadas polinomios de Tutte (originalmente denominados dicromatos ) que satisfacen DC. [1]
El número de árboles de expansión satisface DC. [3]
Demostración. 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 de expansión de G , entonces contraer e produce otro árbol de expansión de . Por el contrario, si tenemos un árbol de expansión T de , entonces expandir la arista e da dos árboles desconectados; agregar e conecta los dos y da un árbol de expansión de G .
Según el teorema de Kirchhoff, la cantidad de árboles de expansión en un grafo se cuenta por un cofactor de la matriz laplaciana . Sin embargo, el polinomio característico laplaciano no satisface la DC. Al estudiar los laplacianos con pesos de vértice, se puede encontrar una relación de contracción-eliminación entre los polinomios característicos laplacianos ponderados por vértice escalados. [4]
El polinomio cromático que cuenta el número de k -coloraciones de G no satisface DC, sino una fórmula ligeramente modificada (que puede hacerse equivalente): [1]
Demostración. Si e = uv , entonces una coloración k de G es la misma que una coloración k de G \ e donde u y v tienen colores diferentes. Hay coloraciones totales de G \ e . Ahora necesitamos restar aquellas donde u y v tienen colores similares. Pero tales coloraciones corresponden a las coloraciones k de donde u y v están fusionadas.
Esta propiedad anterior se puede utilizar para demostrar que el polinomio cromático es, de hecho, un polinomio en k . Podemos hacerlo mediante inducción sobre el número de aristas y observando que en el caso base donde no hay aristas, hay coloraciones posibles (que es un polinomio en k ).
