Polinomio Tatta

El polinomio de Tatta ( polinomio de Tatta-Whitney ) es un polinomio de dos variables que juega un papel importante en la teoría de grafos ; se define para cualquier gráfico no dirigido y contiene información sobre qué tan conectado está el gráfico . La notación estándar es . $T_{G}$

Inicialmente estudiado en teoría algebraica de grafos como una construcción para generalizar problemas de conteo relacionados con la coloración de gráficos y flujos cero en ninguna parte , más tarde se encontró una conexión con el polinomio de Jones de la teoría de nudos y las sumas estadísticas del modelo de Potts de la física estadística . El polinomio es el origen de algunos problemas computacionales informática teórica .

El polinomio tiene varias definiciones equivalentes: es equivalente al polinomio de rango de Whitney , el polinomio dicromático de Tutt y el modelo de conglomerado aleatorio de Fortuin-Casttelyn (después de una ligera transformación) . Un polinomio es esencialmente una función generadora para el número de aristas de conjuntos de un tamaño dado y componentes conectados, y tiene una generalización directa en la teoría matroide . El polinomio es también una invariante de la forma más general para grafos, que puede definirse por la recursividad de remoción - contracción . Algunos libros sobre teoría de grafos y matroides dedican capítulos enteros a este concepto [1] [2] [3] .

Definiciones

Para un gráfico no dirigido, el polinomio de Tatta se define como: $G=(V,E)$

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

donde significa el número de componentes conectados del gráfico . Se puede ver a partir de la definición que el polinomio está bien definido y es polinomio en y en . ${\ estilo de visualización k (A)}$ ${\ estilo de visualización (V, A)}$ $T_{G}$ $X$ $y$

La misma definición se puede dar en otra notación, si se denota por el rango del gráfico . Entonces la función generadora de Whitney para el rango se define como: $r(A)=|V|-k(A)$ ${\ estilo de visualización (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, como lo muestra un simple cambio de variables:

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

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

T_{G}(x,y)=(x-1)^{-k(G)}Q_{G}(x-1,y-1)

La definición original de Tutt para un gráfico conectado es equivalente (pero esta equivalencia es técnicamente más difícil de mostrar): $T_{G}$ $GRAMO$

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

donde significa el número de árboles de expansión de "actividad interna y actividad externa ". ${\ Displaystyle t_ {ij}}$ $i$ $j$

La tercera definición utiliza la recursividad de extracción de eliminación . La contracción de una arista de un gráfico es una gráfica que se obtiene fusionando los vértices y eliminando una arista , y la notación significa eliminar sólo la arista . Entonces el polinomio de Tatta se define por recursividad: $jefe$ $GRAMO$ $tu$ $v$ $ultravioleta$ $G-uv$ $ultravioleta$

T_{G}=T_{Ge}+T_{G/e}

si no es ni un bucle ni un puente , con el caso base: $mi$

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

si contiene puentes y bucles y ningún otro borde. En particular , si no contiene bordes. $GRAMO$ $i$ $j$ ${\ estilo de visualización T_ {G} = 1}$ $GRAMO$

El modelo de conglomerados aleatorios de Fortuin-Casttelyn [4] da otra definición equivalente [5] :

Z_{G}(q,w)=\sum \nolimits_{F\subseteq E}q^{k(F)}w^{|F|}

es equivalente cuando se transforma [6] : $T_{G}$

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

Propiedades

El polinomio de Tatta se descompone en componentes conexas - si es la unión de gráficas disjuntas y , entonces: $GRAMO$ $H$ $H'$

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

Si es plana y denota su gráfico dual , entonces: $GRAMO$ $G^{*}$

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

En particular, el polinomio cromático de un gráfico plano es el polinomio de flujo de su dual.

Ejemplos

Los gráficos isomorfos tienen los mismos polinomios de Tutt, pero lo contrario no es cierto. Por ejemplo, el polinomio Tatta de cualquier árbol con aristas es . $metro$ $x^{m}$

Los polinomios de Tutt a menudo se publican como una tabla de términos de coeficientes de fila y columna . Por ejemplo, el polinomio de Tatta del gráfico de Petersen , ${\ Displaystyle t_ {ij}}$ ${\ estilo de visualización x^{i}y^{j))$ $i$ $j$

{\begin{alineado}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{alineado}}

Está escrito en la forma de la siguiente tabla:

0	36	84	75	35	9	una
36	168	171	sesenta y cinco	diez
120	240	105	quince
180	170	treinta
170	70
114	12
56
21
6
una

Otro ejemplo, el polinomio de Tatta del gráfico del octaedro es:

{\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{alineado}}

Historia

El interés de William Tutt por la fórmula deleción-contracción surgió durante su época de estudiante en el Trinity College (Cambridge) y se inspiró en los rectángulos perfectos [7] y los árboles de expansión . Usó a menudo la fórmula en la investigación y "se sorprendió cuando descubrió otras funciones interesantes en gráficos, invariantes bajo isomorfismos , con fórmulas recursivas similares" [8] . Ronald Foster notó que el polinomio cromático era una de esas funciones y Tutt comenzó a descubrir otras. La terminología original para los gráficos invariantes que satisfacían la recursividad de eliminación-contracción era la función W , y usó el término función V para el caso de la multiplicación de componentes. Tutt escribió: "Jugando con funciones W , obtuve un polinomio en dos variables, del cual se podía obtener un polinomio cromático o un polinomio de flujo asignando una variable a cero y corrigiendo los signos" [8] . Tutt llamó a esta función dicromática y demostró que es una generalización de dos variables de un polinomio cromático, pero este polinomio generalmente se conoce como polinomio de Tutt. Según Tutt, "esto podría ser frustrante para Hassler Whitney , quien usó coeficientes similares y no trató de ajustarlos para las dos variables". (Existe confusión [9] entre los términos "bicromatado" y "polinomio bicromático", introducido por Tutt en otro artículo y ligeramente diferente). Crapo publicó una generalización del polinomio de Tutt para matroides, aunque ya había aparecido en las tesis de Tutt. [10] .

Independientemente, mientras trabajaba con la teoría de grafos algebraicos , Potts comenzó a estudiar las funciones de partición de algunos modelos de mecánica estadística en 1952. En un artículo de 1972 sobre el modelo de conglomerados aleatorios, una generalización del modelo de Potts , Fortuin y Casteleyn [4] dieron una expresión combinada que mostró la relación de este modelo con el polinomio de Tatta [10] .

Especializaciones

En varios puntos y líneas del plano , el polinomio de Tatta da valores que se estudian por derecho propio en varios campos de las matemáticas y la física. Parte del atractivo del polinomio de Tutt se debe a la unificación del método de análisis de estas cantidades. $(x, y)$

Polinomio cromático

En , el polinomio de Tatta se convierte en un polinomio cromático, $y=0$

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

donde denota el número de componentes conectados del gráfico . ${\ estilo de visualización k (G)}$ $GRAMO$

Para un número entero , el valor del polinomio cromático es igual al número de coloraciones de los vértices del gráfico usando colores. Está claro que no depende del juego de colores. Es menos claro que la función es un polinomio de con coeficientes enteros. Para entender esto, tenga en cuenta: $\lambda$ ${\ estilo de visualización \ chi _ {G} (\ lambda)}$ $GRAMO$ $\lambda$ ${\ estilo de visualización \ chi _ {G} (\ lambda)}$ $\lambda$

Si el gráfico tiene vértices y no tiene aristas, entonces . $GRAMO$ $norte$ ${\ estilo de visualización \ chi _ {G} (\ lambda) = \ lambda ^ {n})$
Si el gráfico contiene un bucle (una arista que conecta un vértice con el mismo vértice), entonces . $GRAMO$ ${\ estilo de visualización \ chi _ {G} (\ lambda) = 0}$
Si es una arista que no es un bucle, entonces $mi$

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

Estas tres condiciones nos permiten calcular mediante una secuencia de eliminaciones y contracciones. Sin embargo, estas operaciones no garantizan que una secuencia diferente de operaciones conduzca al mismo resultado. La unicidad está garantizada por el hecho de que cuenta las cosas independientemente de la recursividad. En particular, ${\ estilo de visualización \ chi _ {G} (\ lambda)}$ ${\ estilo de visualización \ chi _ {G} (\ lambda)}$

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

da el número de orientaciones acíclicas.

Polinomio de Jones

A lo largo de la hipérbola , el polinomio de Tutt del gráfico plano se reduce al polinomio de Jones del nudo alterno asociado . ${\ estilo de visualización xy = 1}$

Puntos individuales

(2.1)

$T_{G}(2,1)$ contar el número de árboles , es decir, el número de subconjuntos acíclicos de aristas.

(1.1)

$T_{G}(1,1)$ cuenta el número de esqueletos ( subgrafos acíclicos con el mismo número de componentes conectados que el gráfico ). Si el gráfico está conectado, se cuenta el número de árboles de expansión. $GRAMO$ $T_{G}(1,1)$

(1,2)

$T_{G}(1,2)$ cuenta el número de subgrafos que se expanden con el mismo número de componentes conectados que el gráfico . $GRAMO$

(2.0)

$T_{G}(2,0)$ cuenta el número de orientaciones acíclicas del gráfico [11] . $GRAMO$

(0,2)

$T_{G}(0,2)$ cuenta el número de orientaciones fuertemente conectadas del gráfico [12] . $GRAMO$

(0,−2)

Si el gráfico es un gráfico de 4 regulares, entonces $GRAMO$

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

cuenta el número de orientaciones acíclicas del gráfico . Aquí está el número de componentes conectados del gráfico [11] . $GRAMO$ ${\ estilo de visualización k (G)}$ $GRAMO$

(3,3)

Si el gráfico es - una red , entonces cuenta el número de formas de teselar un rectángulo con ancho y alto con mosaicos T-tetromino [13] [14] $GRAMO$ $m\veces n$ ${\ estilo de visualización 2T_ {G} (3,3)}$ ${\ estilo de visualización 4m}$ ${\ estilo de visualización 4n}$

Si el gráfico es plano , entonces es igual a la suma de las orientaciones de Euler ponderadas en el gráfico central del gráfico , donde el peso es de 2 al número de vértices de silla de montar de la orientación (es decir, el número de vértices con aristas en el orden cíclico "adentro, afuera, adentro afuera") [15] . $GRAMO$ ${\ estilo de visualización 2T_ {G} (3,3)}$ $GRAMO$

Los modelos Potts e Ising

Para una hipérbola en un plano : $xy$

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

el polinomio de Tutt se reduce a la función de partición del modelo de Ising , estudiado en física estadística . En particular, a lo largo de la hipérbola, el dos está relacionado con la ecuación [16] : ${\ estilo de visualización Z (\ cdot)}$ $H_2$

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:

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

para todo complejo . $\alfa$

De manera más general, si para cualquier positivo definimos una hipérbola: $q$

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

entonces el polinomio de Tutt se reduce a la función de partición del modelo de Potts con estados. Varias cantidades físicas analizadas utilizando el modelo de Potts se dividen en partes específicas . $q$ ${\ Displaystyle H_ {q}}$

Correspondencias entre el modelo de Potts y el plano de Tutt [17] .

Modelo Potts	Polinomio Tatta
Ferromagnético	rama positiva ${\ Displaystyle H_ {q}}$
Antiferroimanes	rama negativa con ${\ Displaystyle H_ {q}}$ $y>0$
Calor	Asíntota a ${\ Displaystyle H_ {q}}$ $y=1$
Ferroimanes de baja temperatura	Asíntota de la rama positiva a ${\ Displaystyle H_ {q}}$ $x=1$
Ferroimanes de temperatura cero	Colorear un gráfico en q colores , es decir, ${\ estilo de visualización x = 1-q, y = 0}$

Polinomio de flujo

Para , el polinomio de Tatta se convierte en un polinomio de flujo estudiado en combinatoria. Para un gráfico no dirigido conectado y un número entero en ninguna parte, el flujo cero es la asignación de valores de "flujo" a los bordes de orientación arbitraria en el gráfico , de modo que la suma de los flujos de entrada y salida en cada vértice es módulo congruente . El polinomio de flujo significa el número de flujos cero en ninguna parte. Este valor está directamente relacionado con el polinomio cromático. De hecho, si es un grafo plano , el polinomio cromático del grafo es equivalente al polinomio de flujo de su grafo dual en el sentido de que se cumple la siguiente afirmación (Tatt): $x=0$ $GRAMO$ $k$ $k$ ${\ estilo de visualización 1,2, \ puntos, k-1}$ $GRAMO$ $k$ ${\ Displaystyle C_ {G} (k)}$ $k$ $GRAMO$ $GRAMO$ $G^{*}$

C_{G}(k)=k^{-1}\chi_{G^{*}}(k)

La conexión con el polinomio de Tatta viene dada por la igualdad:

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

Polinomio de vitalidad

En , el polinomio de Tatta se convierte en el polinomio de supervivencia estudiado en la teoría de redes. Para un gráfico conectado , cualquier borde se elimina con probabilidad , lo que simula pérdidas aleatorias del borde. Luego, el polinomio de supervivencia es una función de , un polinomio de , que da la probabilidad de que cualquier par de vértices permanezca conectado después de que se elimine un borde. La conexión con el polinomio de Tatta viene dada por la igualdad $x=1$ $GRAMO$ $pags$ ${\ Displaystyle R_ {G} (p)}$ $pags$ $GRAMO$

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

Polinomio dicromático

Tutt definió también una generalización cercana de 2 variables del polinomio cromático, el polinomio dicromático gráfico:

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

donde es el número de componentes conexas del subgrafo generador . Está relacionado con el polinomio de rango de Whitney por la igualdad: ${\ estilo de visualización k (A)}$ ${\ estilo de visualización (V, A)}$

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

El polinomio dicromático no se generaliza a las matroides porque no es una propiedad de las matroides: diferentes gráficos con la misma matroid pueden tener diferentes números de componentes conectados. ${\ estilo de visualización k (A)}$

Polinomios relacionados

Polinomio de Martin

El polinomio de Martin de un gráfico de 4 regulares dirigido fue definido por Pierre Martin en 1977 [18] . Demostró que si es una gráfica plana y es su gráfica mediana dirigida , entonces $m_{\vec{G}}(x)$ ${\ estilo de visualización {\ vec {G}}}$ $GRAMO$ ${\vec{G}}_{m}$

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

Algoritmos

Fórmula de eliminación - contracciones

Aplicación de la fórmula de deleción - contracción para el polinomio de Tatta:

T_{G}(x,y)=T_{G\setminus e}(x,y)+T_{G/e}(x,y)

donde no hay bucle ni puente, da un algoritmo recursivo para calcular un polinomio: se selecciona cualquier borde adecuado y se aplica la fórmula hasta que solo queden bucles y puentes. Los monomios resultantes son fáciles de calcular. $mi$ $mi$

Hasta un factor polinomial, el tiempo de ejecución de este algoritmo se puede expresar en términos del número de vértices y el número de aristas del gráfico: $t$ $norte$ $metro$

{\ estilo de visualización t (n + m) = t (n + m-1) + t (n + m-2)}

relación recursiva que define números de Fibonacci con solución [19] .

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

El análisis se puede mejorar en el valor del factor polinomial del número de árboles de expansión del gráfico de entrada [20] . Para gráficos dispersos con el tiempo de ejecución del algoritmo es . Para gráficos de grados regulares, el número de árboles de expansión puede estar limitado por el valor ${\ estilo de visualización \ tau (G)}$ ${\ estilo de visualización m = O (n)}$ ${\ estilo de visualización O (\ exp (n))}$ $k$

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

dónde

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

Por ejemplo [21] [22] :

{\ estilo de visualización \ nu _ {5} \ aproximadamente 4 {,} 4066}

En la práctica, la comprobación de isomorfismos se utiliza para evitar algunas llamadas recursivas . Este enfoque funciona bien para gráficos muy dispersos y gráficos con muchas simetrías, mientras que la velocidad del algoritmo depende del método de selección de bordes [20] [23] [24] . $mi$

Excepción gaussiana

En algunos casos limitados, el polinomio de Tutt se puede calcular en tiempo polinomial debido al hecho de que la eliminación de Gauss calcula el determinante y Pfaffian de manera eficiente . Estos algoritmos son en sí mismos un resultado importante de la teoría de grafos algebraicos y la mecánica estadística .

$T_{G}(1,1)$ es igual al número de árboles de expansión del grafo conectado. Se puede calcular en tiempo polinomial como el determinante de la submatriz principal máxima de la matriz de Kirchhoff de un gráfico , un resultado inicial de la teoría algebraica de gráficos conocida como el teorema del árbol de matrices . De manera similar, la dimensión del espacio para bicicletas se puede calcular en tiempo polinomial utilizando el método de eliminación de Gauss . ${\ estilo de visualización \ tau (G)}$ $GRAMO$ $T_{G}(-1,-1)$

Para gráficos planos, la función de distribución del modelo de Ising, es decir, el polinomio de Tutt en una hipérbola , puede expresarse como Pfaffian y calcularse eficientemente con el algoritmo FKT . Esta idea fue desarrollada por Fischer , Castelein y Temperley para calcular el número de fichas de dominó que cubren un modelo de celosía plana . $H_2$

Método Monte Carlo para cadenas de Markov

Usando el método de Monte Carlo para cadenas de Markov , uno puede aproximar arbitrariamente el polinomio de Tutt a lo largo de la rama , de manera equivalente, de la función de distribución del modelo ferromagnético de Ising. Este enfoque explota la estrecha relación entre el modelo de Ising y el problema de contar coincidencias en un gráfico. La idea de este enfoque, debido a Jerram y Sinclair [25] , es formar una cadena de Markov cuyos estados correspondan a coincidencias del gráfico de entrada. Las transiciones se determinan seleccionando bordes aleatoriamente y las coincidencias se modifican en consecuencia. La cadena de Markov resultante se mezcla rápidamente y conduce a coincidencias "razonablemente aleatorias" que se pueden usar para descubrir la función de distribución mediante muestreo aleatorio. El algoritmo resultante es el esquema de tiempo polinomial aproximado (FPRAS). $H_2$

Complejidad computacional

Hay algunos problemas de cálculo asociados con el polinomio de Tatta. El algoritmo más sencillo

Aporte Grafico

GRAMO

Producción Posibilidades

T_{G}

En particular, la derivación permite calcular , lo que equivale a contar 3 colores del gráfico . Este problema es #P-completo , incluso si está restringido a la familia de grafos planos , por lo que el problema de calcular los coeficientes del polinomio de Tutt para un gráfico dado es #P-difícil incluso para gráficos planos . $T_{G}(-2,0)$ $GRAMO$

Se ha prestado mucha más atención a una familia de problemas llamada Tutte definida para cualquier par complejo : $(x, y)$ $(x, y)$

Aporte Grafico

GRAMO

Producción Sentido

{\ Displaystyle T_ {G} (x, y)}

La dificultad de esta tarea varía según las coordenadas . $(x, y)$

Cálculo exacto

Si y son enteros no negativos, el problema pertenece a la clase #P . En el caso general, para pares de enteros, el polinomio de Tatta contiene términos negativos, lo que sitúa el problema en la clase de complejidad class GapP , el cierre de la clase #P por sustracción. Para coordenadas racionales , se puede definir un análogo racional de la clase #P [26] . $X$ $y$ ${\ Displaystyle T_ {G} (x, y)}$ $(x, y)$

La complejidad computacional de un cálculo exacto se divide en dos clases para . El problema es #P-difícil a menos que se encuentre en una hipérbola o sea uno de los puntos ${\ Displaystyle T_ {G} (x, y)}$ ${\ estilo de visualización x, y \ en \ mathbb {C}}$ $(x, y)$ $H_1$

\left\{(1,1),(-1,-1),(0,-1),(-1,0),(i,-i),(-i,i),\ izquierda(j,j^{2}\derecha),\izquierda(j^{2},j\derecha)\derecha\},\qquad j=e^{\frac {2\pi i}{3))

En estos casos, el problema es solucionable en tiempo polinomial [27] . Si el problema se restringe a la clase de grafos planos, en los puntos de la hipérbola el problema se vuelve computable en tiempo polinomial. Todos los demás puntos siguen siendo #P-hard incluso para gráficos planos bipartitos [28] . En su artículo sobre la dicotomía de los gráficos planos, Vertigan argumenta que el mismo resultado es cierto si se imponen restricciones adicionales a los gráficos (el grado del vértice no excede de tres), a excepción del punto , que no cuenta en ninguna parte-cero- flujos y en el que el problema es resoluble en tiempo polinomial [29] . $H_2$ $T_{G}(0,-2)$ $\mathbb{Z} _{3}$

Estos resultados contienen algunos casos especiales importantes. Por ejemplo, el problema de calcular la función de distribución del modelo de Ising es #P-difícil en el caso general, aunque los algoritmos de Onzanger y Fisher lo resuelven para redes planas. También computar el polinomio de Jones es #P-hard. Finalmente, calcular el número de cuatro colores de un gráfico plano es #P-completo, aunque el problema de la resolución es trivial debido al teorema de los cuatro colores . Por el contrario, es fácil ver que contar el número de tres colores de un gráfico plano es #P-completo, ya que se sabe que el problema de resolubilidad es NP-completo de acuerdo con la reducción económica .

Aproximación

La cuestión de qué puntos permiten algoritmos de aproximación ha sido bien estudiada. Además de los puntos, que se pueden calcular exactamente en tiempo polinomial, el único algoritmo de aproximación conocido es el algoritmo de Jerram y Sinclair (FPRAS), que funciona para puntos en la hipérbola de Ising para . Si el gráfico de entrada está restringido a gráficos densos con grado , entonces hay un algoritmo FPRAS si [30] . ${\ Displaystyle T_ {G} (x, y)}$ $H_2$ $y>0$ $\ omega (n)$ ${\ estilo de visualización x \ geqslant 1, y \ geqslant 1}$

Aunque la situación en el caso de la aproximación no se comprende tan bien como para los cálculos exactos, se sabe que grandes áreas del plano son difíciles de aproximar [26] .

Véase también

Polinomio de Bolobash-Riordan

Notas

↑ Bollobas, 1998 , p. Capítulo 10.
↑ Biggs, 1993 , pág. capítulo 13.
↑ Godsil, Royle, 2004 , cap. quince.
↑ 1 2 Fortuin, Kasteleyn, 1972 .
↑ Sokal, 2005 .
↑ Sokal, 2005 , pág. ec. (2.26).
↑ Un rectángulo perfecto es un rectángulo que se puede dividir en cuadrados y todos los cuadrados tienen diferentes tamaños
↑ 12 Tutte , 2004 .
↑ Welch.
↑ 12 Farr , 2007 .
↑ 12 galés , 1999 .
↑ Las Vergnas, 1980 .
↑ Korn, Pak, 2004 .
↑ Ver Korn y Pak ( 2003 ) para una interpretación combinatoria de muchos otros puntos.
↑ Las Vergnas, 1988 .
↑ Galés, 1993 , p. 62.
↑ 12 Galés, Merino, 2000 .
↑ Martín, 1977 .
↑ Wilf, 1986 , pág. 46.
↑ 1 2 Sekine, Imai, Tani, 1995 .
↑ Chung, Yau, 1999 .
↑ Björklund, Husfeldt, Kaski, Koivisto, 2008 .
↑ Haggard, Pearce, Royle, 2010 .
↑ Pearce, Haggard, Royle, 2010 .
↑ Jerrum, Sinclair, 1993 .
↑ 1 2 Goldberg, Jerrum, 2008 .
↑ Jaeger, Vertigan, galés, 1990 .
↑ Vertigan, galés, 1992 .
↑ Vértigan, 2005 .
↑ Para el caso ≥ 1 y = 1, ver Annan ( Annan 1994 ). Para el caso ≥ 1 y > 1, ver artículo. Alon, Frieze y Welsh ( Alon, Frieze, Welsh 1995 ). $X$ $y$ $X$ $y$

Literatura

Alon N., Frieze A., Welsh DJA Esquemas de aproximación aleatoria de tiempo polinomial para invariantes de Tutte-Gröthendieck: El caso denso // Estructuras y algoritmos aleatorios. - 1995. - T. 6 , núm. 4 . — S. 459–478 . -doi : 10.1002/ rsa.3240060409 .
Annan JD Un algoritmo de aproximación aleatoria para contar el número de bosques en gráficos densos // Combinatoria, probabilidad y computación . - 1994. - T. 3 , nº. 3 . — S. 273–283 . -doi : 10.1017/ S0963548300001188 .
Norman Biggs. Teoría algebraica de grafos. — 2do. - Prensa de la Universidad de Cambridge , 1993. - ISBN 0-521-45897-8 .
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. proc. del 47º Simposio anual de IEEE sobre Fundamentos de Ciencias de la Computación (FOCS 2008). - 2008. - S. 677-686. — ISBN 978-0-7695-3436-7 . -doi : 10.1109/ FOCS.2008.40 .
Bella Bollobas. Teoría de grafos moderna. - Springer , 1998. - ISBN 978-0-387-98491-9 .
Fan Chung, S.-T. Yau. Coberturas, núcleos de calor y árboles de expansión // Electronic Journal of Combinatorics . - 1999. - T. 6 . - S. R12 .
Henry H. Crapo. El polinomio de Tutte // Aequationes Mathematicae. - 1969. - T. 3 , nº. 3 . — S. 211–229 . -doi : 10.1007/ bf01817442 .
Graham E. Farr. Combinatoria, complejidad y azar. Un tributo a Dominic Welsh / Geoffrey Grimmett, Colin McDiarmid. - Oxford University Press , 2007. - T. 34. - S. 28-52. - (Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones). — ISBN 0-19-857127-5 .
Cees M. Fortuin, Pieter W. Kasteleyn. Sobre el modelo de conglomerados aleatorios: I. Introducción y relación con otros modelos. — Física . - Elsevier , 1972. - T. 57. - S. 536-564. - doi : 10.1016/0031-8914(72)90045-6 .
Chris Godsil, Gordon Royle. Teoría algebraica de grafos. - Springer , 2004. - ISBN 978-0-387-95220-8 .
Leslie Ann Goldberg, Mark Jerrum. Inaproximabilidad del polinomio de Tutte // Información y Computación . - 2008. - T. 206 , núm. 7 . — S. 908–929 . -doi : 10.1016/ j.ic.2008.04.003 .
Gary Haggard, David J. Pearce, Gordon Royle. Computación de polinomios Tutte // Transacciones ACM en software matemático . - 2010. - T. 37 , núm. 3 . - C.Art. 24, 17 . -doi : 10.1145/ 1824801.1824802 .
F. Jaeger, DL Vertigan, DJA Welsh. Sobre la complejidad computacional de los polinomios de Jones y Tutte // Procedimientos matemáticos de la Sociedad Filosófica de Cambridge . - 1990. - T. 108 . — págs. 35–53 . -doi : 10.1017/ S0305004100068936 .
Mark Jerrum, Alistair Sinclair. Algoritmos de aproximación de tiempo polinomial para el modelo Ising // SIAM Journal on Computing . - 1993. - T. 22 , núm. 5 . — S. 1087–1116 . -doi : 10.1137/ 0222066 .
Michael Korn, Igor Pak. Evaluaciones combinatorias del polinomio de Tutte . — 2003.
Michael Korn, Igor Pak. Teselaciones de rectángulos con T-tetrominós // Informática Teórica . - 2004. - T. 319 , núm. 1–3 . — Pág. 3–27 . -doi : 10.1016/ j.tcs.2004.02.023 .
Michel Las Vergnas. Convexidad en matroides orientados // Revista de Teoría Combinatoria . - 1980. - T. 29 , núm. 2 . — S. 231–243 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(80)90082-9 .
Michel Las Vergnas. Sobre la evaluación en (3, 3) del polinomio Tutte de un gráfico // Journal of Combinatorial Theory . - 1988. - T. 45 , núm. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
Pedro Martín. Eulérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck (francés) . - Universidad Joseph Fourier , 1977. - (Tesis doctoral).
David J. Pearce, Gary Haggard, Gordon Royle. Heurística de selección de bordes para calcular polinomios de Tutte // Chicago Journal of Theoretical Computer Science. - 2010. - S. Artículo 6, 14 .
Kyoko Sekine, Hiroshi Imai, Seiichiro Tani. Algoritmos y cálculos (Cairns, 1995). - Springer , 1995. - T. 1004. - S. 224-233. — ( Apuntes de clase en informática ). -doi : 10.1007/ BFb0015427 .
Alan D. Sokal. Encuestas en combinatoria / Bridget S. Webb. - Cambridge University Press , 2005. - T. 327. - S. 173-226. - (Serie de notas de conferencias de la Sociedad Matemática de Londres). -doi : 10.1017 / CBO9780511734885.009 .
WT Tutte . teoría de grafos . - Prensa de la Universidad de Cambridge , 2001. - ISBN 978-0521794893 .
WT Tutte. Grafo-polinomios // Avances en Matemática Aplicada . - 2004. - T. 32 , núm. 1–2 . — pág. 5–9 . - doi : 10.1016/S0196-8858(03)00041-1 .
DL Vertigan, DJA Galés. La complejidad computacional del plano de Tutte: el caso bipartito // Combinatoria, probabilidad y computación . - 1992. - Vol. 1 , número. 2 . — S. 181–187 . -doi : 10.1017/ S0963548300000195 .
Dirk Vertigan. La complejidad computacional de los invariantes de Tutte para gráficos planos // SIAM Journal on Computing . - 2005. - T. 35 , núm. 3 . — S. 690–712 . -doi : 10.1137/ S0097539704446797 .
DJA galés. teoría matroide . - Prensa académica , 1976. - ISBN 012744050X .
Dominic Welsh. Complejidad: Nudos, Coloraciones y Conteo. - Cambridge University Press , 1993. - (Serie de notas de conferencias de la London Mathematical Society). — ISBN 978-0521457408 .
Dominic Welsh. El polinomio de Tutte . — Estructuras aleatorias y algoritmos. - Wiley , 1999. - T. 15. - S. 210-228. - doi : 10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R .
Welsh DJA, Merino C. El modelo de Potts y el polinomio de Tutte // Journal of Mathematical Physics . - 2000. - T. 41 , núm. 3 . -doi : 10.1063/ 1.533181 .
Herbert S. Wilf. Algoritmos y complejidad . - Prentice Hall , 1986. - ISBN 0-13-021973-8 .

Enlaces

Hazewinkel, Michiel, ed. (2001), polinomio de Tutte , Enciclopedia de Matemáticas , Springer , ISBN 978-1-55608-010-4
Weisstein, polinomio de Eric W. Tutte (inglés) en el sitio web de Wolfram MathWorld .
Polinomio cromático de PlanetMath
Steven R. Pagano: Matroides y grafos firmados
Sandra Kingan: Teoría matroide . Muchos enlaces.
Código para calcular polinomios Tutte, Chromatic y Flow de Gary Haggard, David J. Pearce y Gordon Royle: [1] (enlace no disponible)