polinomio tutte

Codificación algebraica de conectividad de gráficos.

El polinomio es el polinomio de Tutte del gráfico alcista . La línea roja muestra la intersección con el plano , que es esencialmente equivalente al polinomio cromático. ${\displaystyle x^{4}+x^{3}+x^{2}y}$ ${\displaystyle y=0}$

El polinomio de Tutte , también llamado dicromato o polinomio de Tutte-Whitney , es un polinomio gráfico . Es un polinomio en dos variables que juega un papel importante en la teoría de grafos . Se define para cada gráfico no dirigido y contiene información sobre cómo está conectado el gráfico. Se denota por . ${\displaystyle G}$ ${\displaystyle T_{G}}$

La importancia de este polinomio surge de la información que contiene sobre . Aunque originalmente se estudió en la teoría algebraica de grafos como una generalización de los problemas de conteo relacionados con la coloración de grafos y el flujo en ninguna parte cero , contiene varias otras especializaciones famosas de otras ciencias, como el polinomio de Jones de la teoría de nudos y las funciones de partición del modelo de Potts de la estadística. física . También es la fuente de varios problemas computacionales centrales en la informática teórica . ${\displaystyle G}$

El polinomio de Tutte tiene varias definiciones equivalentes. Es esencialmente equivalente al polinomio de rango de Whitney, al polinomio dicromático del propio Tutte y al modelo de conglomerado aleatorio de Fortuin-Kasteleyn bajo transformaciones simples. Es esencialmente una función generadora del número de conjuntos de bordes de un tamaño determinado y componentes conectados, con generalizaciones inmediatas a matroides . También es el invariante gráfico más general que se puede definir mediante una recurrencia de eliminación-contracción . Varios libros de texto sobre teoría de grafos y teoría matroide le dedican capítulos enteros. ^{[1] [2] [3]}

Definiciones

Definición. Para un gráfico no dirigido, se puede definir el polinomio de Tutte como ${\displaystyle G=(V,E)}$

${\displaystyle T_{G}(x,y)=\sum \nolimits _{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|},}$

donde denota el número de componentes conectados del gráfico . En esta definición queda claro que está bien definido y es un polinomio en y . ${\displaystyle k(A)}$ ${\displaystyle (V,A)}$ ${\displaystyle T_{G}}$ ${\displaystyle x}$ ${\displaystyle y}$

Se puede dar la misma definición usando una notación ligeramente diferente dejando denotar el rango del gráfico . Entonces la función generadora de rangos de Whitney se define como ${\displaystyle r(A)=|V|-k(A)}$ ${\displaystyle (V,A)}$

${\displaystyle R_{G}(u,v)=\sum \nolimits _{A\subseteq E}u^{r(E)-r(A)}v^{|A|-r(A)}.}$

Las dos funciones son equivalentes bajo un simple cambio de variables:

${\displaystyle T_{G}(x,y)=R_{G}(x-1,y-1).}$

El polinomio dicromático de Tutte es el resultado de otra transformación simple: ${\displaystyle Q_{G}}$

${\displaystyle T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1).}$

La definición original de Tutte es equivalente pero menos fácil de expresar. Para conectados configuramos ${\displaystyle T_{G}}$ ${\displaystyle G}$

${\displaystyle T_{G}(x,y)=\sum \nolimits _{i,j}t_{ij}x^{i}y^{j},}$

donde denota el número de árboles generadores de actividad interna y actividad externa . ${\displaystyle t_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

Una tercera definición utiliza una recurrencia de eliminación-contracción . La contracción de borde del gráfico es el gráfico obtenido al fusionar los vértices y eliminar el borde . Escribimos para el gráfico donde simplemente se elimina el borde. Entonces el polinomio de Tutte está definido por la relación de recurrencia ${\displaystyle G/uv}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle uv}$ ${\displaystyle G-uv}$ ${\displaystyle uv}$

${\displaystyle T_{G}=T_{G-e}+T_{G/e},}$

si no es ni un bucle ni un puente , con caso base ${\displaystyle e}$

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

si contiene puentes y bucles y ningún otro borde. Especialmente si no contiene bordes. ${\displaystyle G}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle T_{G}=1}$ ${\displaystyle G}$

El modelo de conglomerados aleatorios de la mecánica estadística de Fortuin y Kasteleyn (1972) proporciona otra definición equivalente. ^[4] La suma de la partición

${\displaystyle Z_{G}(q,w)=\sum \nolimits _{F\subseteq E}q^{k(F)}w^{|F|}}$

es equivalente a bajo la transformación ^[5] ${\displaystyle T_{G}}$

${\displaystyle T_{G}(x,y)=(x-1)^{-k(E)}(y-1)^{-|V|}\cdot Z_{G}{\Big (}(x-1)(y-1),\;y-1{\Big )}.}$

Propiedades

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

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

Si es plano y denota su gráfica dual , entonces ${\displaystyle G}$ ${\displaystyle G^{*}}$

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

Especialmente, el polinomio cromático de un gráfico plano es el polinomio de flujo de su dual. Tutte se refiere a funciones como V-funciones . ^[6]

Ejemplos

Los gráficos isomórficos tienen el mismo polinomio de Tutte, pero lo contrario no es cierto. Por ejemplo, el polinomio de Tutte de cada árbol en las aristas es . ${\displaystyle m}$ ${\displaystyle x^{m}}$

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

${\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}\\&+168xy+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}}}$

viene dado por la siguiente tabla.

Otro ejemplo, el polinomio de Tutte del gráfico de octaedro viene dado por

${\displaystyle {\begin{aligned}&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}}}$

Historia

El interés de WT Tutte por la fórmula de deleción-contracción comenzó en su época universitaria en el Trinity College de Cambridge , motivado originalmente por los rectángulos perfectos y los árboles de expansión . A menudo aplicaba la fórmula en su investigación y "se preguntaba si había otras funciones interesantes de gráficos, invariantes bajo isomorfismo , con fórmulas de recursividad similares". ^[6] RM Foster ya había observado que el polinomio cromático es una de esas funciones, y Tutte comenzó a descubrir más. Su terminología original para los invariantes de gráficos que satisfacen la recursividad de eliminación-contracción era función W y función V si es multiplicativa sobre componentes. Tutte escribe: "Jugando con mis funciones W , obtuve un polinomio de dos variables a partir del cual se podía obtener el polinomio cromático o el polinomio de flujo igualando una de las variables a cero y ajustando los signos". ^[6] Tutte llamó a esta función dicromato , ya que la veía como una generalización del polinomio cromático a dos variables, pero generalmente se le conoce como polinomio de Tutte. En palabras de Tutte, "Esto puede ser injusto para Hassler Whitney , quien conocía y usaba coeficientes análogos sin molestarse en asociarlos a dos variables". (Existe una “confusión notable” ^[7] acerca de los términos dicromato y polinomio dicromático , introducidos por Tutte en un artículo diferente, y que difieren sólo ligeramente). La generalización del polinomio de Tutte a las matroides fue publicada por primera vez por Crapo , aunque parece que ya en la tesis de Tutte. ^[8]

Independientemente del trabajo en teoría de grafos algebraicos , Potts comenzó a estudiar la función de partición de ciertos modelos en mecánica estadística en 1952. El trabajo de Fortuin y Kasteleyn ^[9] sobre el modelo de conglomerados aleatorios , una generalización del modelo de Potts , proporcionó una expresión unificadora. que mostró la relación con el polinomio de Tutte. ^[8]

Especializaciones

En varios puntos y líneas del plano, el polinomio de Tutte evalúa cantidades que han sido estudiadas por derecho propio en diversos campos de las matemáticas y la física. Parte del atractivo del polinomio de Tutte proviene del marco unificador que proporciona para analizar estas cantidades. ${\displaystyle (x,y)}$

Polinomio cromático

El polinomio cromático dibujado en el plano de Tutte.

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

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

donde denota el número de componentes conectados de G . ${\displaystyle k(G)}$

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

1. Si G tiene n vértices y no tiene aristas, entonces . ${\displaystyle \chi _{G}(\lambda )=\lambda ^{n}}$
2. Si G contiene un bucle (un solo borde 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 , aplicando una secuencia de eliminaciones y contracciones de bordes; pero no ofrecen garantía de que una secuencia diferente de eliminaciones y contracciones conduzca al mismo valor. La garantía proviene del hecho de que cuenta algo, independientemente de la recurrencia. En particular, ${\displaystyle \chi _{G}(\lambda )}$ ${\displaystyle \chi _{G}(\lambda )}$

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

da el número de orientaciones acíclicas.

polinomio de Jones

El polinomio de Jones dibujado en el plano de Tutte

A lo largo de la hipérbola , el polinomio de Tutte de un gráfico plano se especializa en el polinomio de Jones de un nudo alterno asociado . ${\displaystyle xy=1}$

Puntos individuales

(2,1)

${\displaystyle T_{G}(2,1)}$cuenta el número de bosques , es decir, el número de subconjuntos de bordes acíclicos.

(1,1)

${\displaystyle T_{G}(1,1)}$cuenta el número de bosques que se extienden (subconjuntos de bordes sin ciclos y el mismo número de componentes conectados que G ). Si el gráfico es conexo, cuenta el número de árboles generadores. ${\displaystyle T_{G}(1,1)}$

(1,2)

${\displaystyle T_{G}(1,2)}$cuenta el número de subgrafos que se extienden (subconjuntos de bordes con el mismo número de componentes conectados que G ).

(2,0)

${\displaystyle T_{G}(2,0)}$cuenta el número de orientaciones acíclicas de G . ^[10]

(0,2)

${\displaystyle T_{G}(0,2)}$cuenta el número de orientaciones fuertemente conectadas de G . ^[11]

(2,2)

${\displaystyle T_{G}(2,2)}$es el número donde está el número de aristas del gráfico G . ${\displaystyle 2^{|E|}}$ ${\displaystyle |E|}$

(0,-2)

Si G es un gráfico de 4 regulares, entonces

${\displaystyle (-1)^{|V|+k(G)}T_{G}(0,-2)}$

cuenta el número de orientaciones eulerianas de G . Aquí está el número de componentes conectados de G. ^[10] ${\displaystyle k(G)}$

(3,3)

Si G es el gráfico de cuadrícula m  ×  n , entonces cuenta el número de formas de mosaico de un rectángulo de 4 m de ancho y 4 n de alto con T-tetrominós . ^{[12] [13]} ${\displaystyle 2T_{G}(3,3)}$

Si G es un gráfico plano , entonces es igual a la suma de las orientaciones eulerianas ponderadas en un gráfico medial de G , donde el peso de una orientación es 2 elevado al número de vértices de silla de montar de la orientación (es decir, el número de vértices con aristas incidentes ordenado cíclicamente "dentro, fuera, dentro fuera"). ^[14] ${\displaystyle 2T_{G}(3,3)}$

Modelos de Potts e Ising

Las funciones de partición para el modelo de Ising y los modelos de Potts de 3 y 4 estados dibujados en el plano de Tutte.

Defina la hipérbola en el plano xy :

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

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

${\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 todo complejo α.

De manera 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 estado q . Varias cantidades físicas analizadas en el marco del modelo de Potts se traducen en partes específicas del . ${\displaystyle H_{q}}$

Polinomio de flujo

El polinomio de flujo dibujado en el plano de Tutte.

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

Teorema (Tutte).

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

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

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

Polinomio de confiabilidad

El polinomio de confiabilidad dibujado en el plano de Tutte.

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

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

Polinomio dicromático

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

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

donde es el número de componentes conectados del subgrafo de expansión ( V , A ). Esto está relacionado con el polinomio corank-nulidad por ${\displaystyle k(A)}$

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

El polinomio dicromático no se generaliza a matroides porque k ( A ) no es una propiedad de matroid: diferentes gráficos con la misma matroide pueden tener diferentes números de componentes conectados.

Polinomios relacionados

polinomio de martin

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

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

Algoritmos

Deleción-contracción

"El algoritmo de eliminación-contracción aplicado al gráfico de diamantes ". Los bordes rojos se eliminan en el hijo izquierdo y se contraen en el hijo derecho. El polinomio resultante es la suma de los monomios en las hojas, . Basado en Welsh & Merino (2000). ${\displaystyle x^{3}+2x^{2}+y^{2}+2xy+x+y}$

La recurrencia de deleción-contracción del 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.}}}$

produce inmediatamente un algoritmo recursivo para calcularlo para un gráfico dado: siempre que pueda encontrar una arista e que no sea un bucle o puente , calcule recursivamente el polinomio de Tutte para cuando se elimine esa arista y cuando se contraiga . Luego suma los dos subresultados para obtener el polinomio de Tutte general para el gráfico.

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

Dentro de un factor polinómico, 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 gráfico,

${\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 polinomial del número de árboles de expansión del gráfico de entrada. ^[19] Para gráficos dispersos con este tiempo de ejecución es . Para gráficos regulares de grado k , el número de árboles de expansión puede estar limitado por ${\displaystyle \tau (G)}$ ${\displaystyle m=O(n)}$ ${\displaystyle \exp(O(n))}$

${\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 polinómico de este límite. Por ejemplo: ^[20]

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

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

eliminación gaussiana

En algunos casos restringidos, el polinomio de Tutte se puede calcular en tiempo polinómico, en última instancia porque la eliminación gaussiana calcula eficientemente las operaciones matriciales determinante y pfaffiana . Estos algoritmos son en sí mismos resultados importantes de la teoría de grafos algebraicos y la mecánica estadística .

${\displaystyle T_{G}(1,1)}$es igual al número de árboles de expansión de un gráfico conectado. Esto es computable 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 de grafos algebraicos conocido como teorema de matriz-árbol de Kirchhoff . Asimismo, la dimensión del espacio de la bicicleta en se puede calcular en tiempo polinómico mediante eliminación gaussiana. ${\displaystyle \tau (G)}$ ${\displaystyle T_{G}(-1,-1)}$

Para gráficos planos, la función de partición del modelo de Ising, es decir, el polinomio de Tutte en la hipérbola , se puede expresar como Pfaff y calcularse de manera eficiente mediante el algoritmo FKT . Esta idea fue desarrollada por Fisher , Kasteleyn y Temperley para calcular el número de cubiertas de dímeros de un modelo de red plana . ${\displaystyle H_{2}}$

Cadena de Markov Montecarlo

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

Complejidad computacional

Varios problemas computacionales están asociados con el polinomio de Tutte. El más sencillo es

Entrada: un gráfico ${\displaystyle G}$

Salida: Los coeficientes de ${\displaystyle T_{G}}$

En particular, la salida permite evaluar cuál es equivalente a contar el número de 3 colores de G. Esta última pregunta es #P-completa , incluso cuando se restringe a la familia de gráficas planas , por lo que el problema de calcular los coeficientes del polinomio de Tutte para una gráfica dada es #P-difícil incluso para gráficas planas. ${\displaystyle T_{G}(-2,0)}$

Se ha prestado mucha más atención a la familia de problemas denominada Tutte definida para cada par complejo : ${\displaystyle (x,y)}$ ${\displaystyle (x,y)}$

Entrada: un gráfico ${\displaystyle G}$

Salida: El valor de ${\displaystyle T_{G}(x,y)}$

La dureza de estos problemas varía con las coordenadas . ${\displaystyle (x,y)}$

Cálculo exacto

El avión Tutte. Cada punto del plano real corresponde a un problema computacional . En cualquier punto rojo, el problema es computable en tiempo polinomial; en cualquier punto azul, el problema es #P-difícil en general, pero computable en tiempo polinomial para gráficos planos; y en cualquier punto de las regiones blancas, el problema es #P-difícil incluso para gráficos planos bipartitos. ${\displaystyle (x,y)}$ ${\displaystyle T_{G}(x,y)}$

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

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

${\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 cuyos casos es computable en tiempo polinomial. ^[25] Si el problema se restringe a la clase de gráficos planos, los puntos de la hipérbola también se vuelven computables en tiempo polinomial. Todos los demás puntos siguen siendo #P-hard, incluso para gráficos planos bipartitos. ^[26] En su artículo sobre la dicotomía de gráficos planos, Vertigan afirma (en su conclusión) que el mismo resultado se cumple cuando se restringe aún más a gráficos con grados de vértice como máximo tres, salvo el punto , que no cuenta en ninguna parte -cero Z ₃ - fluye y es computable en tiempo polinomial. ^[27] ${\displaystyle H_{2}}$ ${\displaystyle T_{G}(0,-2)}$

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 redes planas. Además, el polinomio de Jones es #P-difícil de calcular. Finalmente, calcular el número de cuatro colores de un gráfico plano es #P-completo, aunque el problema de decisión es trivial según el teorema de los cuatro colores . Por el contrario, es fácil ver que contar el número de tres colores para gráficos planos es #P-completo porque se sabe que el problema de decisión es NP-completo mediante una reducción parsimoniosa .

Aproximación

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 es el FPRAS de Jerrum y Sinclair, que funciona para puntos en la hipérbola "Ising" para y > 0. Si los gráficos de entrada están restringidos a instancias densas, con grado , existe un FPRAS si x ≥ 1, y ≥ 1. ^[28] ${\displaystyle T_{G}(x,y)}$ ${\displaystyle H_{2}}$ ${\displaystyle \Omega (n)}$

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

Ver también

• Polinomio de Bollobás-Riordan
• Un invariante de Tutte-Grothendieck es cualquier evaluación del polinomio de Tutte

Notas

1. Bollobás 1998, capítulo 10.
2. Biggs 1993, capítulo 13.
3. Godsil y Royle 2004, cap. 15.
4. Sokal 2005.
5. Sokal 2005, ecuación. (2.26).
6. Tutte 2004.
7. galés.
8. Farr 2007.
9. Fortuin y Kasteleyn 1972.
10. galés 1999.
11. Las Vergnas 1980.
12. Korn y Pak 2004.
13. Véase Korn & Pak 2003 para interpretaciones combinatorias de muchos otros puntos.
14. Las Vergnas 1988.
15. Galés 1993, pag. 62.
16. Galés y Merino 2000.
17. Martín 1977.
18. Wilf 1986, pág. 46.
19. Sekine, Imai y Tani 1995.
20. Chung y Yau 1999, siguiendo a Björklund et al. 2008.
21. Demacrado, Pearce y Royle 2010.
22. Pearce, Haggard y Royle 2010.
23. Jerrum y Sinclair 1993.
24. Goldberg y Jerrum 2008.
25. Jaeger, Vertigan y Gales 1990.
26. Vertigan y galés 1992.
27. Vértigan 2005.
28. Para el caso x ≥ 1 e y = 1, consulte Annan 1994. Para el caso x ≥ 1 e y > 1, consulte Alon, Frieze & Welsh 1995.

Referencias

• Alón, N.; Friso, A.; Welsh, DJA (1995), "Esquemas de aproximación aleatoria de tiempo polinomial para invariantes de Tutte-Gröthendieck: el caso denso", Estructuras y algoritmos aleatorios , 6 (4): 459–478, doi :10.1002/rsa.3240060409.
• Annan, JD (1994), "Un algoritmo de aproximación aleatoria para contar el número de bosques en gráficos densos", Combinatoria, probabilidad y computación , 3 (3): 273–283, doi :10.1017/S0963548300001188.
• Biggs, Norman (1993), Teoría de grafos algebraicos (2ª ed.), Cambridge University Press , ISBN 0-521-45897-8.
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Cálculo del polinomio de Tutte en tiempo exponencial de vértice", Proc. del 47º Simposio anual del IEEE sobre fundamentos de la informática (FOCS 2008) , págs. 677–686, arXiv : 0711.2585 , doi : 10.1109/FOCS.2008.40, ISBN 978-0-7695-3436-7.
• Bollobás, Béla (1998), Teoría de grafos moderna , Springer , ISBN 978-0-387-98491-9.
• Chung, Fan ; Yau, S.-T. (1999), "Revestimientos, núcleos de calor y árboles de expansión", Electronic Journal of Combinatorics , 6 : R12, MR  1667452.
• Crapo, Henry H. (1969), "El polinomio de Tutte", Aequationes Mathematicae , 3 (3): 211–229, doi :10.1007/bf01817442.
• Farr, Graham E. (2007), "Polinomios de Tutte-Whitney: algo de historia y generalizaciones", en Grimmett, Geoffrey ; McDiarmid, Colin (eds.), Combinatoria, complejidad y azar. Un homenaje a Dominic Welsh , Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones, vol. 34, Oxford University Press , págs. 28–52, ISBN 978-0-19-857127-8, Zbl  1124.05020.
• Fortuin, Cees M.; Kasteleyn, Pieter W. (1972), "Sobre el modelo de conglomerados aleatorios: I. Introducción y relación con otros modelos", Physica , Elsevier , 57 (4): 536–564, Bibcode :1972Phy....57.. 536F, dirección :10.1016/0031-8914(72)90045-6, ISSN  0031-8914.
• Godsil, Chris ; Royle, Gordon (2004), Teoría de grafos algebraicos , Springer , ISBN 978-0-387-95220-8.
• Goldberg, Leslie Ann ; Jerrum, Mark (2008), "Inaproximabilidad del polinomio de Tutte", Información y Computación , 206 (7): 908–929, arXiv : cs/0605140 , doi :10.1016/j.ic.2008.04.003.
• Demacrado, Gary; Pearce, David J.; Royle, Gordon (2010), "Computación de polinomios de Tutte", Transacciones ACM en software matemático , 37 (3): art. 24, 17, doi :10.1145/1824801.1824802, SEÑOR  2738228.
• Jaeger, F.; Vértigan, DL; Welsh, DJA (1990), "Sobre la complejidad computacional de los polinomios de Jones y Tutte", Actas matemáticas de la Sociedad Filosófica de Cambridge , 108 (1): 35–53, Bibcode :1990MPCPS.108...35J, doi :10.1017 /S0305004100068936.
• Jerrum, Marcos ; Sinclair, Alistair (1993), "Algoritmos de aproximación en tiempo polinómico para el modelo de Ising" (PDF) , SIAM Journal on Computing , 22 (5): 1087–1116, doi :10.1137/0222066.
• Korn, Michael; Pak, Igor (2003), Evaluaciones combinatorias del polinomio de Tutte (PDF) (preimpresión).
• Korn, Michael; Pak, Igor (2004), "Azulejos de rectángulos con T-tetrominós", Informática teórica , 319 (1–3): 3–27, doi : 10.1016/j.tcs.2004.02.023.
• Las Vergnas, Michel (1980), "Convexidad en matroides orientadas", Journal of Combinatorial Theory , Serie B, 29 (2): 231–243, doi : 10.1016/0095-8956(80)90082-9 , ISSN  0095-8956 , SEÑOR  0586435.
• Las Vergnas, Michel (1988), "Sobre la evaluación en (3, 3) del polinomio de Tutte de un grafo", Journal of Combinatorial Theory , Serie B, 45 (3): 367–372, doi : 10.1016/0095- 8956(88)90079-2 , ISSN  0095-8956.
• Martin, Pierre (1977), Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck [ Enumeraciones eulerianas en multigrafías e invariantes de Tutte-Grothendieck ] (tesis doctoral) (en francés), Universidad Joseph Fourier.
• Pearce, David J.; Demacrado, Gary; Royle, Gordon (2010), "Heurística de selección de bordes para calcular polinomios de Tutte" (PDF) , Chicago Journal of Theoretical Computer Science : artículo 6, 14, MR  2659710.
• Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Cálculo del polinomio de Tutte de un gráfico de tamaño moderado", Algoritmos y cálculos (Cairns, 1995) , Lecture Notes in Computer Science , vol. 1004, Springer , págs. 224–233, doi :10.1007/BFb0015427, SEÑOR  1400247.
• Sokal, Alan D. (2005), "El polinomio multivariado de Tutte (alias modelo de Potts) para gráficos y matroides", en Webb, Bridget S. (ed.), Surveys in Combinatorics , London Mathematical Society Lecture Note Series, vol. 327, Cambridge University Press , págs. 173–226, arXiv : math/0503607 , doi :10.1017/CBO9780511734885.009.
• Tutte, WT (2001), Teoría de grafos , Cambridge University Press , ISBN 978-0521794893.
• Tutte, WT (2004), "Gráficos polinomios", Avances en matemáticas aplicadas , 32 (1–2): 5–9, doi : 10.1016/S0196-8858(03)00041-1.
• Vértigan, DL; Welsh, DJA (1992), "La complejidad computacional del plano de Tutte: el caso bipartito", Combinatoria, probabilidad y computación , 1 (2): 181–187, doi :10.1017/S0963548300000195.
• Vertigan, Dirk (2005), "La complejidad computacional de las invariantes de Tutte para gráficos planos", SIAM Journal on Computing , 35 (3): 690–712, doi :10.1137/S0097539704446797.
• Welsh, DJA (1976), Teoría matroide , Academic Press , ISBN 012744050X.
• Welsh, Dominic (1993), Complejidad: nudos, colorear y contar , Serie de notas de conferencias de la London Mathematical Society, Cambridge University Press , ISBN 978-0521457408.
• Welsh, Dominic (1999), "El polinomio de Tutte", Algoritmos y estructuras aleatorias , Wiley , 15 (3–4): 210–228, doi :10.1002/(SICI)1098-2418(199910/12)15:3/ 4<210::AID-RSA2>3.0.CO;2-R, ISSN  1042-9832.
• galés, DJA ; Merino, C. (2000), "El modelo de Potts y el polinomio de Tutte", Journal of Mathematical Physics , 41 (3): 1127–1152, Bibcode :2000JMP....41.1127W, doi :10.1063/1.533181.
• Wilf, Herbert S. (1986), Algoritmos y complejidad (PDF) , Prentice Hall , ISBN 0-13-021973-8, señor  0897317.

enlaces externos

• "Polinomio de Tutte", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Polinomio de Tutte". MundoMatemático .
• Polinomio cromático PlanetMath
• Steven R. Pagano: matroides y gráficos firmados
• Sandra Kingan: teoría matroide. Muchos enlaces.
• Código para calcular polinomios Tutte, cromáticos y de flujo por Gary Haggard, David J. Pearce y Gordon Royle: [1]