polinomio de Tutte

El polinomio de Tutte se factoriza en componentes conexas. Si${\displaystyle G}$es la unión de grafos disjuntos${\displaystyle H}$y${\displaystyle H'}$entonces

${\displaystyle T_{G}=T_{H}\cdot T_{H'}}$

Si${\displaystyle G}$es plano y${\displaystyle G^{*}}$denota su grafo dual entonces

${\displaystyle T_{G}(x,y)=T_{G^{*}}(y,x)}$

En particular, el polinomio cromático de un grafo planar es el polinomio de flujo de su dual. Tutte se refiere a estas funciones como ^funciones V. ^{[ 6} ]

Los grafos isomorfos tienen el mismo polinomio de Tutte, pero lo contrario no es cierto. Por ejemplo, el polinomio de Tutte de cada árbol en${\displaystyle m}$bordes es${\displaystyle x^{m}}$.

Los polinomios de Tutte a menudo se presentan en forma tabular enumerando los coeficientes.${\displaystyle t_{ij}}$de${\displaystyle x^{i}y^{j}}$en fila${\displaystyle i}$y columna${\displaystyle j}$. Por ejemplo, el polinomio de Tutte del gráfico de Petersen ,

${\displaystyle {\begin{aligned}36x&+120x^{2}+180x^{3}+170x^{4}+114x^{5}+56x^{6}+21x^{7}+6x^{8}+x^{9}\\&+36y+84y^{2}+75y^{3}+35y^{4}+9y^{5}+y^{6}\\&+1 68xy+240x^{2}y+170x^{3}y+70x^{4}y+12x^{5}y\\&+171xy^{2}+105x^{2}y^{2}+30x^{3}y^{2}\\&+65xy^{3}+15x^{2}y^{3}\\&+10xy^{4},\end{aligned}}}$

se proporciona en la siguiente tabla.

Otro ejemplo, el polinomio de Tutte del grafo octaédrico viene dado por

${\displaystyle {\begin{alineado}&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2}\\&+25\,{x}^{2}+29\, {y}^{4}+15\,{y}^{5}+5\,{y}^{6}+6\,{y}^{4}x\\&+39\,y{x}^{2}+20\ ,{x}^{3}+{y}^{7}+8\,y{x}^{3}+7\,{x}^{4}+{x}^{5}\end{aligned}}}$

En${\displaystyle y=0}$, el polinomio de Tutte se especializa en el polinomio cromático,

${\displaystyle \chi _{G}(\lambda )=(-1)^{|V|-k(G)}\lambda ^{k(G)}T_{G}(1-\lambda ,0),}$

dónde${\displaystyle k(G)}$denota el número de componentes conexas de G.

Para un entero λ, el valor del polinomio cromático${\displaystyle \chi _{G}(\lambda )}$es igual al número de coloraciones de vértices de G usando un conjunto de λ colores. Es evidente que${\displaystyle \chi _{G}(\lambda )}$no depende del conjunto de colores. Lo que no está tan claro es que se trata de la evaluación en λ de un polinomio con coeficientes enteros. Para ver esto, observamos:

1. Si G tiene n vértices y ninguna arista, entonces${\displaystyle \chi _{G}(\lambda )=\lambda ^{n}}$.
2. Si G contiene un bucle (una sola arista que conecta un vértice consigo mismo), entonces${\displaystyle \chi _{G}(\lambda )=0}$.
3. Si e es una arista que no es un bucle, entonces

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

Las tres condiciones anteriores nos permiten calcular${\displaystyle \chi _{G}(\lambda )}$, aplicando una secuencia de eliminaciones y contracciones de aristas; pero no dan ninguna garantía de que una secuencia diferente de eliminaciones y contracciones conduzca al mismo valor. La garantía proviene del hecho de que${\displaystyle \chi _{G}(\lambda )}$cuenta algo, independientemente de la recurrencia. En particular,

${\displaystyle T_{G}(2,0)=(-1)^{|V|}\chi _{G}(-1)}$

da el número de orientaciones acíclicas.

A lo largo de la hipérbola${\displaystyle xy=1}$, el polinomio de Tutte de un grafo planar se especializa en el polinomio de Jones de un nudo alternante asociado .

Defina la hipérbola en el plano xy :

${\displaystyle H_{2}:\quad (x-1)(y-1)=2,}$

El polinomio de Tutte se especializa en la función de partición,${\displaystyle Z(\cdot ),}$del modelo de Ising estudiado en física estadística . Específicamente, a lo largo de la hipérbola${\displaystyle H_{2}}$Los dos están relacionados por la ecuación: ^{[ 15 ]}

${\displaystyle Z(G)=2\left(e^{-\alpha }\right)^{|E|-r(E)}\left(4\sinh \alpha \right)^{r(E)}T_{G}\left(\coth \alpha ,e^{2\alpha }\right).}$

En particular,

${\displaystyle (\coth \alpha -1)\left(e^{2\alpha }-1\right)=2}$

para todos los complejos α.

De forma más general, si para cualquier entero positivo q , definimos la hipérbola:

${\displaystyle H_{q}:\quad (x-1)(y-1)=q,}$

Entonces, el polinomio de Tutte se especializa en la función de partición del modelo de Potts de q estados . Varias cantidades físicas analizadas en el marco del modelo de Potts se traducen en partes específicas del${\displaystyle H_{q}}$.

En${\displaystyle x=0}$El polinomio de Tutte se especializa en el polinomio de flujo estudiado en combinatoria. Para un grafo conexo y no dirigido G y un entero k , un k -flujo sin ceros en ninguna parte es una asignación de valores de "flujo".${\displaystyle 1,2,\dots ,k-1}$a los bordes de una orientación arbitraria de G tal que el flujo total que entra y sale de cada vértice es congruente módulo k . El polinomio de flujo${\displaystyle C_{G}(k)}$denota el número de k- flujos sin cero en ninguna parte. Este valor está íntimamente relacionado con el polinomio cromático; de hecho, si G es un grafo planar , el polinomio cromático de G es equivalente al polinomio de flujo de su grafo dual.${\displaystyle G^{*}}$en el sentido de que

Teorema (Tutte).

${\displaystyle C_{G}(k)=k^{-1}\chi _{G^{*}}(k).}$

La relación con el polinomio de Tutte viene dada por:

${\displaystyle C_{G}(k)=(-1)^{|E|-|V|+k(G)}T_{G}(0,1-k).}$

En${\displaystyle x=1}$El polinomio de Tutte se especializa en el polinomio de confiabilidad de todos los terminales estudiado en la teoría de redes. Para un grafo conexo G, elimine cada arista con probabilidad p ; esto modela una red sujeta a fallas aleatorias en las aristas. Entonces, el polinomio de confiabilidad es una función${\displaystyle R_{G}(p)}$, un polinomio en p , que da la probabilidad de que cada par de vértices en G permanezca conectado después de que fallen las aristas. La conexión con el polinomio de Tutte viene dada por

${\displaystyle R_{G}(p)=(1-p)^{|V|-k(G)}p^{|E|-|V|+k(G)}T_{G}\left(1,{\tfrac {1}{p}}\right).}$

Tutte también definió una generalización de dos variables más cercana del polinomio cromático, el polinomio dicromático de un grafo. Esto es

${\displaystyle Q_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{k(A)}v^{|A|-|V|+k(A)},}$

dónde${\displaystyle k(A)}$es el número de componentes conexas del subgrafo generador ( V , A ). Esto está relacionado con el polinomio de corango-nulidad por

${\displaystyle Q_{G}(u,v)=u^{k(G)}\,R_{G}(u,v).}$

El polinomio dicromático no se generaliza a los matroides porque k ( A ) no es una propiedad de los matroides: diferentes grafos con el mismo matroide pueden tener diferentes números de componentes conexas.

El polinomio de Martin${\displaystyle m_{\vec {G}}(x)}$de un grafo 4-regular orientado${\displaystyle {\vec {G}}}$fue definido por Pierre Martin en 1977. ^{[ 17 ]} Demostró que si G es un grafo plano y${\displaystyle {\vec {G}}_{m}}$es su grafo medial dirigido , entonces

${\displaystyle T_{G}(x,x)=m_{{\vec {G}}_{m}}(x).}$

La recurrencia de eliminación-contracción para el polinomio de Tutte,

${\displaystyle T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y),\qquad e{\text{ not a loop nor a bridge.}}}$

Esto proporciona inmediatamente un algoritmo recursivo para calcularlo para un grafo dado: siempre que se pueda encontrar una arista e que no sea un bucle ni un puente , se calcula recursivamente el polinomio de Tutte cuando se elimina esa arista y cuando se contrae . Luego, se suman los dos subresultados para obtener el polinomio de Tutte global para el grafo.

El caso base es un monomio.${\displaystyle x^{m}y^{n}}$donde m es el número de puentes y n es el número de bucles.

Dentro de un factor polinomial, el tiempo de ejecución t de este algoritmo se puede expresar en términos del número de vértices n y el número de aristas m del grafo,

${\displaystyle t(n+m)=t(n+m-1)+t(n+m-2),}$

una relación de recurrencia que escala como los números de Fibonacci con solución ^{[ 18 ]}

${\displaystyle t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1.6180^{n+m}\right).}$

El análisis se puede mejorar hasta un factor polinómico del número${\displaystyle \tau (G)}$de árboles de expansión del grafo de entrada. ^{[ 19 ]} Para grafos dispersos con${\displaystyle m=O(n)}$este tiempo de ejecución es${\displaystyle \exp(O(n))}$Para grafos regulares de grado k , el número de árboles de expansión puede acotarse por

${\displaystyle \tau (G)=O\left(\nu _{k}^{n}n^{-1}\log n\right),}$

dónde

${\displaystyle \nu _{k}={\frac {(k-1)^{k-1}}{(k^{2}-2k)^{{\frac {k}{2}}-1}}}.}$

por lo que el algoritmo de eliminación-contracción se ejecuta dentro de un factor polinomial de este límite. Por ejemplo: ^{[ 20 ]}

${\displaystyle \nu _{5}\approx 4.4066.}$

En la práctica, se utiliza la prueba de isomorfismo de grafos para evitar algunas llamadas recursivas. Este enfoque funciona bien para grafos que son bastante dispersos y presentan muchas simetrías; el rendimiento del algoritmo depende de la heurística utilizada para seleccionar la arista e . ^{[ 19 ] [ 21 ] [ 22 ]}

En algunos casos restringidos, el polinomio de Tutte puede calcularse en tiempo polinomial, en última instancia porque la eliminación gaussiana calcula eficientemente el determinante y el pfaffiano de las operaciones matriciales . Estos algoritmos son, a su vez, resultados importantes de la teoría algebraica de grafos y la mecánica estadística .

${\displaystyle T_{G}(1,1)}$es igual al número${\displaystyle \tau (G)}$de árboles de expansión de un grafo conexo. Esto se puede calcular en tiempo polinomial como el determinante de una submatriz principal máxima de la matriz laplaciana de G , un resultado temprano en la teoría algebraica de grafos conocido como el teorema matriz-árbol de Kirchhoff . Asimismo, la dimensión del espacio de bicicletas en${\displaystyle T_{G}(-1,-1)}$se puede calcular en tiempo polinomial mediante eliminación gaussiana.

Para grafos planares, la función de partición del modelo de Ising, es decir, el polinomio de Tutte en la hipérbola${\displaystyle H_{2}}$, puede expresarse como un pfaffiano y calcularse eficientemente mediante el algoritmo FKT . Esta idea fue desarrollada por Fisher , Kasteleyn y Temperley para calcular el número de recubrimientos de dímeros de un modelo de red planar .

Utilizando un método de Monte Carlo de cadena de Markov , el polinomio de Tutte puede aproximarse arbitrariamente bien a lo largo de la rama positiva de${\displaystyle H_{2}}$De forma equivalente, la función de partición del modelo de Ising ferromagnético. Esto aprovecha la estrecha conexión entre el modelo de Ising y el problema de contar emparejamientos en un grafo. La idea detrás de este célebre resultado de Jerrum y Sinclair ^{[ 23 ]} es establecer una cadena de Markov cuyos estados son los emparejamientos del grafo de entrada. Las transiciones se definen eligiendo aristas al azar y modificando el emparejamiento en consecuencia. La cadena de Markov resultante se mezcla rápidamente y conduce a emparejamientos "suficientemente aleatorios", que pueden usarse para recuperar la función de partición mediante muestreo aleatorio. El algoritmo resultante es un esquema de aproximación aleatoria totalmente polinomial (fpras).

Si tanto x como y son enteros no negativos, el problema${\displaystyle T_{G}(x,y)}$pertenece a #P . Para pares enteros generales, el polinomio de Tutte contiene términos negativos, lo que sitúa el problema en la clase de complejidad GapP , el cierre de #P bajo la resta. Para acomodar coordenadas racionales${\displaystyle (x,y)}$, se puede definir un análogo racional de #P . ^{[ 24 ]}

La complejidad computacional de calcular exactamente${\displaystyle T_{G}(x,y)}$cae en una de dos clases para cualquier${\displaystyle x,y\in \mathbb {C} }$El problema es #P-difícil a menos que${\displaystyle (x,y)}$se encuentra en la hipérbola${\displaystyle H_{1}}$o es uno de los puntos

${\displaystyle \left\{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),\left(j,j^{2}\right),\left(j^{2},j\right)\right\},\qquad j=e^{\frac {2\pi i}{3}}.}$

en los cuales es computable en tiempo polinomial. ^{[ 25 ]} Si el problema se restringe a la clase de grafos planares, los puntos en la hipérbola${\displaystyle H_{2}}$también se vuelven computables en tiempo polinomial. Todos los demás puntos siguen siendo #P-difíciles, incluso para grafos planares bipartitos. ^{[ 26 ]} En su artículo sobre la dicotomía para grafos planares, Vertigan afirma (en su conclusión) que el mismo resultado se mantiene cuando se restringe aún más a grafos con grado de vértice como máximo tres, excepto por el punto${\displaystyle T_{G}(0,-2)}$, que cuenta los flujos Z ₃ que no son cero en ninguna parte y es computable en tiempo polinomial. ^{[ 27 ]}

Estos resultados contienen varios casos especiales notables. Por ejemplo, el problema de calcular la función de partición del modelo de Ising es #P-difícil en general, aunque los célebres algoritmos de Onsager y Fisher lo resuelven para retículos planares. Además, el polinomio de Jones es #P-difícil de calcular. Finalmente, calcular el número de cuatro coloraciones de un grafo planar es #P-completo, aunque el problema de decisión es trivial por el teorema de los cuatro colores . En contraste, es fácil ver que contar el número de tres coloraciones para grafos planares es #P-completo porque se sabe que el problema de decisión es NP-completo mediante una reducción parsimoniosa .

La cuestión de qué puntos admiten un buen algoritmo de aproximación ha sido muy bien estudiada. Aparte de los puntos que se pueden calcular exactamente en tiempo polinomial, el único algoritmo de aproximación conocido para${\displaystyle T_{G}(x,y)}$es el FPRAS de Jerrum y Sinclair, que funciona para puntos en la hipérbola de "Ising".${\displaystyle H_{2}}$para y > 0. Si los grafos de entrada están restringidos a instancias densas, con grado${\displaystyle \Omega (n)}$, existe un FPRAS si x ≥ 1, y ≥ 1. ^{[ 28 ]}

Aunque la situación no se comprende tan bien como para el cálculo exacto, se sabe que grandes áreas del plano son difíciles de aproximar. ^{[ 24 ]}