Tatta polynom

Tatta -polynomet ( Tatta-Whitney- polynomet ) är ett tvåvariabelt polynom som spelar en stor roll i grafteorin ; definieras för alla oriktade grafer och innehåller information om hur sammankopplad grafen är . Standardnotationen är . $T_{G}$

Ursprungligen studerade i algebraisk grafteori som en konstruktion för att generalisera räkneproblem relaterade till graffärgning och ingenstans nollflöden , senare hittades ett samband med Jones polynom från knutteorin och de statistiska summorna av Potts-modellen från statistisk fysik . Polynomet är ursprunget till vissa beräkningsproblem teoretisk datavetenskap .

Polynomet har flera ekvivalenta definitioner: det är ekvivalent med Whitneys , Tutts dikromatiska polynom och Fortuin-Castelyns slumpmässiga klustermodell (efter en liten transformation) . Ett polynom är i huvudsak en genererande funktion för antalet kanter av uppsättningar av en given storlek och anslutna komponenter, och har en direkt generalisering i matroidteorin . Polynomet är också en invariant av den mest allmänna formen för grafer, som kan definieras av rekursionen av borttagning - kontraktion . Vissa böcker om grafteori och matroider ägnar hela kapitel åt detta koncept [1] [2] [3] .

Definitioner

För en oriktad graf definieras Tatta-polynomet som: $G=(V,E)$

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

där betyder antalet anslutna komponenter i grafen . Det framgår av definitionen att polynomet är väldefinierat och polynomet i och i . $k(A)$ $(V,A)$ $T_{G}$ $x$ $y$

Samma definition kan ges i annan notation, om den anges med grafens rangordning . Då definieras Whitneys genererande funktion för rangen som: $r(A)=|V|-k(A)$ $(V,A)$

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

De två funktionerna är likvärdiga, vilket framgår av en enkel förändring av variabler:

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

Tutts dikromatiska polynom är resultatet av en annan enkel transformation: $Q_{G}$

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

Tutts ursprungliga definition för en sammankopplad graf är likvärdig (men denna ekvivalens är tekniskt svårare att visa): $T_{G}$ $G$

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

där betyder antalet spännande träd för "intern aktivitet och extern aktivitet ". ${\displaystyle t_{ij))$ $i$ $j$

Den tredje definitionen använder deletion-pull-rekursionen . Sammandragning av en kant på en graf är en graf som erhålls genom att slå samman hörn och ta bort en kant , och notation betyder att bara kanten tas bort . Då definieras Tatta-polynomet av rekursion: $g/uv$ $G$ $u$ $v$ $UV$ $G-uv$ $UV$

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

if är varken en slinga eller en brygga , med basfallet: $e$

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

om den innehåller broar och slingor och inga andra kanter. I synnerhet , om inte innehåller kanter. $G$ $i$ $j$ $T_{G}=1$ $G$

Fortuin-Castelyns slumpmässiga klustermodell [4] ger en annan ekvivalent definition [5] :

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

är ekvivalent när den transformeras [6] : $T_{G}$

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

Egenskaper

Tatta-polynomet sönderdelas till sammankopplade komponenter - om det är föreningen av disjunkta grafer och , då: $G$ $H$ $H'$

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

Om är plan och anger dess dubbla graf , då: $G$ $G^{*}$

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

I synnerhet är det kromatiska polynomet i en plan graf flödespolynomet för dess dual.

Exempel

Isomorfa grafer har samma Tutt-polynom, men det omvända är inte sant. Till exempel är Tatta-polynomet för alla träd med kanter . $m$ $x^{m}$

Tutts polynom publiceras ofta som en rad- och kolumnkoefficienttabell med termer . Till exempel, Tatta-polynomet i Petersen-grafen , ${\displaystyle t_{ij))$ ${\displaystyle x^{i}y^{j))$ $i$ $j$

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

Det är skrivet i form av följande tabell:

0	36	84	75	35	9	ett
36	168	171	65	tio
120	240	105	femton
180	170	trettio
170	70
114	12
56
21
6
ett

Ett annat exempel, Tatta-polynomet i oktaedergrafen är:

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

Historik

William Tutts intresse för raderings-sammandragningsformeln uppstod under hans studenttid vid Trinity College (Cambridge) och inspirerades av perfekta rektanglar [7] och spännande träd . Han använde ofta formeln i forskning och "blev förvånad när han upptäckte andra intressanta funktioner på grafer, invarianta under isomorfismer , med liknande rekursiva formler" [8] . Ronald Foster märkte att det kromatiska polynomet var en sådan funktion, och Tutt började upptäcka andra. Den ursprungliga terminologin för grafinvarianter som tillfredsställer deletions-kontraktionsrekursionen var W-funktionen och han använde termen V-funktion för fallet med komponentmultiplikation. Tutt skrev: "När jag leker med W-funktioner fick jag ett polynom i två variabler, från vilka man kunde få ett kromatiskt polynom eller ett flödespolynom genom att tilldela en variabel till noll och korrigera tecknen" [8] . Tutt kallade denna funktion dikromatisk och visade att det är en tvåvariabel generalisering av ett kromatiskt polynom, men detta polynom brukar kallas Tutts polynom. Enligt Tutt, "Det här kan vara frustrerande för Hassler Whitney , som använde liknande koefficienter och inte försökte anpassa dem för de två variablerna." (Det finns förvirring [9] mellan termerna "bikromat" och "bikromatiskt polynom", infört av Tutt i en annan tidning och något annorlunda.) En generalisering av Tutts polynom för matroider publicerades av Crapo, även om den redan förekommit i Tutts avhandlingar [10] .

Självständigt, medan han arbetade med algebraisk grafteori , började Potts studera partitionsfunktioner för vissa modeller av statistisk mekanik 1952. I en artikel från 1972 om den slumpmässiga klustermodellen gav en generalisering av Potts-modellen , Fortuin och Casteleyn [4 ] ett kombinerat uttryck som visade sambandet mellan denna modell och Tatta-polynomet [10] .

Specialiseringar

På olika punkter och linjer i planet ger Tatta-polynomet värden som studeras i sig inom olika områden av matematik och fysik. En del av attraktionen hos Tutts polynom beror på enandet av metoden för att analysera dessa storheter. $(x,y)$

Kromatiskt polynom

Vid förvandlas Tatta-polynomet till ett kromatiskt polynom, $y=0$

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

där anger antalet anslutna komponenter i grafen . $k(G)$ $G$

För ett heltal är värdet på det kromatiska polynomet lika med antalet färgningar av grafens hörn som använder färger. Det är tydligt att det inte beror på uppsättningen av färger. Det är mindre tydligt att funktionen är ett polynom med heltalskoefficienter. För att förstå detta, notera: $\lambda$ $\chi _{G}(\lambda )$ $G$ $\lambda$ $\chi _{G}(\lambda )$ $\lambda$

Om grafen har hörn och inga kanter, då . $G$ $n$ ${\displaystyle \chi _{G}(\lambda )=\lambda ^{n))$
Om grafen innehåller en slinga (en kant som förbinder en vertex med samma vertex), då . $G$ $\chi _{G}(\lambda )=0$
Om är en kant som inte är en slinga, alltså $e$

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

Dessa tre villkor tillåter oss att beräkna genom en sekvens av deletioner och sammandragningar. Dessa operationer garanterar dock inte att en annan sekvens av operationer leder till samma resultat. Unikhet garanteras av det faktum att saker räknas oberoende av rekursion. Särskilt, $\chi _{G}(\lambda )$ $\chi _{G}(\lambda )$

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

anger antalet acykliska orienteringar.

Jones polynom

Längs hyperbeln reduceras Tutt-polynomet i den plana grafen till Jones-polynomet för den associerade alternerande knuten . $xy=1$

Individuella poäng

(2.1)

$T_{G}(2,1)$ räkna antalet träd , det vill säga antalet acykliska delmängder av kanter.

(1.1)

$T_{G}(1,1)$ räknar antalet skelett ( acykliska subgrafer med samma antal anslutna komponenter som grafen ). Om grafen är sammankopplad, räknas antalet spännande träd. $G$ $T_{G}(1,1)$

(1,2)

$T_{G}(1,2)$ räknar antalet spännande subgrafer med samma antal anslutna komponenter som grafen . $G$

(2.0)

$T_{G}(2,0)$ räknar antalet acykliska orienteringar av grafen [11] . $G$

(0,2)

$T_{G}(0,2)$ räknar antalet starkt sammankopplade orienteringar av grafen [12] . $G$

(0,−2)

Om grafen är en 4-regelbunden graf, då $G$

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

räknar antalet acykliska orienteringar av grafen . Här är antalet anslutna komponenter i grafen [11] . $G$ $k(G)$ $G$

(3,3)

Om grafen är - ett gitter , räknar man antalet sätt att tessellera en rektangel med bredd och höjd med T-tetrominoplattor [ 13] [14] $G$ $m\ gånger n$ $2T_{G}(3,3)$ $4m$ $4n$

Om grafen är plan är den lika med summan av de vägda Euler-orienteringarna i mittengrafen på grafen , där vikten är från 2 till antalet sadelhörn i orienteringen (det vill säga antalet hörn med kanter i cyklisk ordning "in, ut, in ut") [15] . $G$ $2T_{G}(3,3)$ $G$

Potts och Ising-modellerna

För en hyperbel i ett plan : $xy$

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

Tutt-polynomet reducerar till partitionsfunktionen för Ising-modellen , studerad i statistisk fysik . I synnerhet längs hyperbeln är de två relaterade till ekvationen [16] : $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)

Särskilt:

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

för alla komplexa . $\alfa$

Mer generellt, om vi för något positivt definierar en hyperbel: $q$

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

sedan reduceras Tutt-polynomet till partitionsfunktionen för Potts-modellen med tillstånd. Olika fysiska storheter som analyseras med hjälp av Potts-modellen går in i specifika delar . $q$ ${\displaystyle H_{q))$

Överensstämmelse mellan Potts-modellen och Tutt-planet [17] .

Potts modell	Tatta polynom
Ferromagnetisk	positiv gren ${\displaystyle H_{q))$
Antiferromagneter	Negativ gren med ${\displaystyle H_{q))$ $y>0$
Värme	Asymptot till ${\displaystyle H_{q))$ $y=1$
Lågtemperatur ferromagneter	Asymptot för den positiva grenen till ${\displaystyle H_{q))$ $x=1$
Nolltemperatur ferromagneter	Färglägga en graf i q- färger , dvs. $x=1-q,y=0$

Flödespolynom

För Tatta-polynomet förvandlas till ett flödespolynom som studeras i kombinatorik. För en ansluten oriktad graf och ett heltal ingenstans är nollflöde tilldelningen av "flödes"-värden till kanter med godtycklig orientering i grafen , så att summan av in- och utflöden vid varje vertex är kongruenta modulo . Flödespolynomet betyder antalet noll -flöden. Detta värde är direkt relaterat till det kromatiska polynomet. Faktum är att om är en plan graf , är grafens kromatiska polynom ekvivalent med flödespolynomet i dess dubbla graf i den meningen att följande påstående gäller (Tatt): $x=0$ $G$ $k$ $k$ $1,2,\dots ,k-1$ $G$ $k$ $C_{G}(k)$ $k$ $G$ $G$ $G^{*}$

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

Sambandet med Tatta-polynomet ges av likheten:

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

Vitalitetspolynom

Vid förvandlas Tatta-polynomet till överlevnadspolynomet som studerats i nätverksteorin. För en sammankopplad graf tas eventuell kant bort med sannolikhet , vilket simulerar slumpmässiga bortfall av kanten. Sedan är överlevnadspolynomet en funktion av , ett polynom av , vilket ger sannolikheten att något par av hörn i förblir anslutna efter att en kant har tappats. Sambandet med Tatta-polynomet ges av likheten $x=1$ $G$ $sid$ $R_{G}(p)$ $sid$ $G$

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

Dikromatiskt polynom

Tutt definierade också en nära 2-variabel generalisering av det kromatiska polynomet, grafens dikromatiska polynom:

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

där är antalet anslutna komponenter i den spännande subgrafen . Det är relaterat till Whitneys rangpolynom genom likheten: $k(A)$ $(V,A)$

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

Det dikromatiska polynomet är inte generaliserat till matroider eftersom det inte är en egenskap hos matroider – olika grafer med samma matroid kan ha olika antal sammankopplade komponenter. $k(A)$

Relaterade polynom

Martins polynom

Martin-polynomet för en riktad 4-regelbunden graf definierades av Pierre Martin 1977 [18] . Han visade att if är en plan graf och är dess riktade mediangraf , alltså $m_{\vec {G}}(x)$ ${\vec {G}}$ $G$ ${\vec {G}}_{m}$

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

Algoritmer

Borttagningsformel - sammandragningar

Tillämpning av deletions-kontraktionsformeln för Tatta-polynomet:

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

där varken är en loop eller en brygga, ger en rekursiv algoritm för att beräkna ett polynom - valfri lämplig kant väljs och formeln tillämpas tills endast loopar och bryggor återstår. De resulterande monomierna är lätta att beräkna. $e$ $e$

Upp till en polynomfaktor kan exekveringstiden för denna algoritm uttryckas i termer av antalet hörn och antalet kanter på grafen: $t$ $n$ $m$

t(n+m)=t(n+m-1)+t(n+m-2)

rekursiv relation som definierar Fibonacci-tal med lösning [19] .

t(n+m)=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O\left(1,6180^{ n+ m}\höger).

Analysen kan förbättras i värdet av polynomfaktorn för antalet spännande träd i ingångsgrafen [20] . För glesa grafer är algoritmens gångtid . För vanliga gradgrafer kan antalet spännträd begränsas av värdet $\tau (G)$ $m=O(n)$ $O(\exp(n))$ $k$

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

var

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

Till exempel [21] [22] :

\nu _{5}\approx 4{,}4066

I praktiken används isomorfismkontroll för att undvika vissa rekursiva anrop . Detta tillvägagångssätt fungerar bra för mycket glesa grafer och grafer med många symmetrier, medan hastigheten på algoritmen beror på kantvalsmetoden [20] [23] [24] . $e$

Gaussiskt undantag

I vissa begränsade fall kan Tutt-polynomet beräknas i polynomtid på grund av att Gaussisk eliminering beräknar determinanten och Pfaffian effektivt . Dessa algoritmer är i sig ett viktigt resultat av algebraisk grafteori och statistisk mekanik .

$T_{G}(1,1)$ är lika med antalet spännande träd i den anslutna grafen. Den kan beräknas i polynomtid som bestämningsfaktorn för den maximala huvudsakliga submatrisen för en grafs Kirchhoff-matris , ett tidigt resultat från algebraisk grafteori som kallas matristrädsatsen . På liknande sätt kan cykelutrymmets dimension beräknas i polynomtid med den Gaussiska elimineringsmetoden . $\tau (G)$ $G$ $T_{G}(-1,-1)$

För plana grafer kan fördelningsfunktionen för Ising-modellen, det vill säga Tutt-polynomet på en hyperbel , uttryckas som en Pfaffian och beräknas effektivt med FKT-algoritmen . Denna idé utvecklades av Fischer , Castelein och Temperley för att beräkna antalet dominobrickor som täcker en plan gittermodell . $H_2$

Monte Carlo-metoden för Markov-kedjor

Genom att använda Monte Carlo-metoden för Markov-kedjor , kan man godtyckligt approximera Tutt-polynomet längs grenen , ekvivalent, av fördelningsfunktionen för den ferromagnetiska Ising-modellen. Detta tillvägagångssätt utnyttjar det nära sambandet mellan Ising-modellen och problemet med att räkna matchningar i en graf. Tanken med detta tillvägagångssätt, på grund av Jerram och Sinclair [25] , är att bilda en Markov-kedja vars tillstånd motsvarar matchningar av ingångsgrafen. Övergångar bestäms genom att slumpmässigt välja kanter och matchningar ändras därefter. Den resulterande Markov-kedjan blandas snabbt och leder till "rimligt slumpmässiga" matchningar som kan användas för att upptäcka distributionsfunktionen med hjälp av slumpmässigt urval. Den resulterande algoritmen är Approximate Polynomial Time Scheme (FPRAS). $H_2$

Beräkningskomplexitet

Det finns några beräkningsproblem förknippade med Tatta-polynomet. Den mest enkla algoritmen

Inmatning Graf

G

Produktion Odds

T_{G}

I synnerhet tillåter härledningen beräkning , vilket motsvarar att räkna 3-färgningar av grafen . Detta problem är #P-komplett , även om det är begränsat till familjen plana grafer , så problemet med att beräkna koefficienterna för Tutt-polynomet för en given graf är #P-hårt även för plana grafer . $T_{G}(-2,0)$ $G$

Mycket mer uppmärksamhet har ägnats åt en familj av problem som kallas Tutte definierade för alla komplexa par : $(x,y)$ $(x,y)$

Inmatning Graf

G

Produktion Menande

T_{G}(x,y)

Svårigheten för denna uppgift varierar beroende på koordinaterna . $(x,y)$

Exakt beräkning

Om och är icke-negativa heltal, tillhör problemet klass #P . I det allmänna fallet, för heltalspar, innehåller Tatta-polynomet negativa termer, vilket placerar problemet i komplexitetsklassen GapP , stängningen av klassen #P genom subtraktion. För rationella koordinater kan man definiera en rationell analog av klassen #P [26] . $x$ $y$ $T_{G}(x,y)$ $(x,y)$

Beräkningskomplexiteten för en exakt beräkning delas in i två klasser för . Problemet är #P-svårt om det inte ligger på en hyperbel eller är en av punkterna $T_{G}(x,y)$ $x,y\in \mathbb {C}$ $(x,y)$ $H_1$

\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))

I dessa fall är problemet lösbart i polynomtid [27] . Om problemet är begränsat till klassen av plana grafer, vid punkterna i hyperbeln blir problemet beräkningsbart i polynomtid. Alla andra punkter förblir #P-hårda även för tvådelade plana grafer [28] . I sin artikel om dikotomi av plana grafer, hävdar Vertigan att samma resultat är sant om ytterligare begränsningar åläggs graferna (graden på vertexet överstiger inte tre), förutom punkten , som räknar ingenstans-noll- flöden och där problemet är lösbart i polynomtid [29] . $H_2$ $T_{G}(0,-2)$ $\mathbb{Z } _{3}$

Dessa resultat innehåller några viktiga specialfall. Till exempel är problemet med att beräkna fördelningsfunktionen för Ising-modellen #P-hårt i det allmänna fallet, även om Onzangers och Fishers algoritmer löser det för platta gitter. Att beräkna Jones-polynomet är #P-svårt. Slutligen, att beräkna antalet fyrfärgningar i en plan graf är #P-komplett, även om problemet med lösbarhet är trivialt på grund av fyrfärgssatsen . Däremot är det lätt att se att räkningen av antalet trefärgningar i en plan graf är #P-komplett, eftersom upplösningsproblemet är känt för att vara NP-komplett enligt ekonomisk reduktion .

Approximation

Frågan om vilka punkter som tillåter approximationsalgoritmer har studerats väl. Förutom punkter, som kan beräknas exakt i polynomtid, är den enda approximationsalgoritmen känd för Jerram och Sinclair (FPRAS) algoritmen, som fungerar för punkter på Ising-hyperbolen för . Om ingångsgrafen är begränsad till täta grafer med grad , så finns det en FPRAS-algoritm om [30] . $T_{G}(x,y)$ $H_2$ $y>0$ $\omega(n)$ $x\geqslant 1,y\geqslant 1$

Även om situationen i fallet med approximation inte är lika väl förstådd som för exakta beräkningar, är det känt att stora ytor av planet är svåra att approximera [26] .

Se även

Bolobash-Riordan polynom

Anteckningar

↑ Bollobás, 1998 , sid. kapitel 10.
↑ Biggs, 1993 , sid. kapitel 13.
↑ Godsil, Royle, 2004 , kap. femton.
↑ 1 2 Fortuin, Kasteleyn, 1972 .
↑ Sokal, 2005 .
↑ Sokal, 2005 , sid. ekv. (2,26).
↑ En perfekt rektangel är en rektangel som kan delas upp i rutor och alla rutor har olika storlek
↑ 12 Tutte , 2004 .
↑ Welch.
↑ 12 Farr , 2007 .
↑ 12 Welsh , 1999 .
↑ Las Vergnas, 1980 .
↑ Korn, Pak, 2004 .
↑ Se Korn och Pak ( 2003 ) för en kombinatorisk tolkning av många andra punkter.
↑ Las Vergnas, 1988 .
↑ Welsh, 1993 , sid. 62.
↑ 12 Welsh, Merino, 2000 .
↑ Martin, 1977 .
↑ Wilf, 1986 , sid. 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, walesiska, 1990 .
↑ Vertigan, walesiska, 1992 .
↑ Vertigan, 2005 .
↑ För fallet ≥ 1 och = 1, se Annan ( Annan 1994 ). För fall ≥ 1 och > 1, se artikel. Alon, Frieze och Welsh ( Alon, Frieze, Welsh 1995 ). $x$ $y$ $x$ $y$

Litteratur

Alon N., Frieze A., Welsh DJA Polynomisk tid randomiserade approximationsscheman för Tutte-Gröthendieck invarianter: The dense case // Random Structures and Algorithms. - 1995. - T. 6 , nr. 4 . — S. 459–478 . - doi : 10.1002/rsa.3240060409 .
Annan JD En randomiserad approximationsalgoritm för att räkna antalet skogar i täta grafer // Combinatorics, Probability and Computing . - 1994. - T. 3 , nummer. 3 . — S. 273–283 . - doi : 10.1017/S0963548300001188 .
Norman Biggs. Algebraisk grafteori. — 2:a. - Cambridge University Press , 1993. - ISBN 0-521-45897-8 .
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Proc. av det 47:e årliga IEEE Symposium on Foundations of Computer Science (FOCS 2008). - 2008. - S. 677-686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 .
Bela Bollobas. Modern grafteori. - Springer , 1998. - ISBN 978-0-387-98491-9 .
Fan Chung, S.-T. Yau. Beläggningar, värmekärnor och spännträd // Electronic Journal of Combinatorics . - 1999. - T. 6 . - S. R12 .
Henry H. Crapo. Tuttepolynomet // Aequationes Mathematicae. - 1969. - T. 3 , nummer. 3 . — S. 211–229 . - doi : 10.1007/bf01817442 .
Graham E. Farr. Kombinatorik, komplexitet och slump. En hyllning till Dominic Welsh / Geoffrey Grimmett, Colin McDiarmid. - Oxford University Press , 2007. - T. 34. - S. 28-52. — (Oxford Lecture Series in Mathematics and its Applications). — ISBN 0-19-857127-5 .
Cees M. Fortuin, Pieter W. Kasteleyn. Om random-cluster-modellen: I. Introduktion och relation till andra modeller. — Fysik . - Elsevier , 1972. - T. 57. - S. 536-564. - doi : 10.1016/0031-8914(72)90045-6 .
Chris Godsil, Gordon Royle. Algebraisk grafteori. - Springer , 2004. - ISBN 978-0-387-95220-8 .
Leslie Ann Goldberg, Mark Jerrum. Inapproximability av Tutte polynomet // Information och beräkning . - 2008. - T. 206 , nr. 7 . — S. 908–929 . - doi : 10.1016/j.ic.2008.04.003 .
Gary Haggard, David J. Pearce, Gordon Royle. Beräkning av Tutte-polynom // ACM-transaktioner på matematisk programvara . - 2010. - T. 37 , nr. 3 . - C. Art. 24, 17 . - doi : 10.1145/1824801.1824802 .
F. Jaeger, DL Vertigan, DJA Welsh. Om beräkningskomplexiteten hos Jones och Tutte-polynomen // Mathematical Proceedings of the Cambridge Philosophical Society . - 1990. - T. 108 . — s. 35–53 . - doi : 10.1017/S0305004100068936 .
Mark Jerrum, Alistair Sinclair. Polynom-tidsapproximationsalgoritmer för Ising-modellen // SIAM Journal on Computing . - 1993. - T. 22 , nr. 5 . — S. 1087–1116 . - doi : 10.1137/0222066 .
Michael Korn, Igor Pak. Kombinatoriska utvärderingar av Tutte-polynomet . – 2003.
Michael Korn, Igor Pak. Plattläggning av rektanglar med T-tetrominoer // Teoretisk datavetenskap . - 2004. - T. 319 , nr. 1–3 . — S. 3–27 . - doi : 10.1016/j.tcs.2004.02.023 .
Michel Las Vergnas. Konvexitet i orienterade matroider // Journal of Combinatorial Theory . - 1980. - T. 29 , nr. 2 . — S. 231–243 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(80)90082-9 .
Michel Las Vergnas. Om utvärderingen vid (3, 3) av Tutte-polynomet av en graf // Journal of Combinatorial Theory . - 1988. - T. 45 , nr. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
Pierre Martin. Uppräkningar Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck (franska) . - Joseph Fourier University , 1977. - (Ph.D.-avhandling).
David J. Pearce, Gary Haggard, Gordon Royle. Kantvalsheuristik för beräkning av Tutte-polynom // Chicago Journal of Theoretical Computer Science. - 2010. - S. Artikel 6, 14 .
Kyoko Sekine, Hiroshi Imai, Seiichiro Tani. Algoritmer och beräkningar (Cairns, 1995). - Springer , 1995. - T. 1004. - S. 224-233. — ( Lecture Notes in Computer Science ). - doi : 10.1007/BFb0015427 .
Alan D. Sokal. Undersökningar i kombinatorik / Bridget S. Webb. - Cambridge University Press , 2005. - T. 327. - S. 173-226. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9780511734885.009 .
WT Tutte . grafteori . - Cambridge University Press , 2001. - ISBN 978-0521794893 .
WT Tutte. Graf-polynom // Framsteg inom tillämpad matematik . - 2004. - T. 32 , nr. 1–2 . — S. 5–9 . - doi : 10.1016/S0196-8858(03)00041-1 .
DL Vertigan, DJA Welsh. Tutteplanets beräkningskomplexitet: det tvådelade fallet // Combinatorics, Probability and Computing . - 1992. - Vol. 1 , nummer. 2 . — S. 181–187 . - doi : 10.1017/S0963548300000195 .
Dirk Vertigan. The Computational Complexity of Tutte Invariants for Planar Graphs // SIAM Journal on Computing . - 2005. - T. 35 , nr. 3 . — S. 690–712 . - doi : 10.1137/S0097539704446797 .
DJ walesiska. matroid teori . - Academic Press , 1976. - ISBN 012744050X .
Dominic Welsh. Komplexitet: Knutar, färger och räkning. - Cambridge University Press , 1993. - (London Mathematical Society Lecture Note Series). — ISBN 978-0521457408 .
Dominic Welsh. Tutte-polynomet . — Slumpmässiga strukturer och algoritmer. - 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. Potts-modellen och Tutte-polynomet // Journal of Mathematical Physics . - 2000. - T. 41 , nr. 3 . - doi : 10.1063/1.533181 .
Herbert S. Wilf. Algoritmer och komplexitet . - Prentice Hall , 1986. - ISBN 0-13-021973-8 .

Länkar

Hazewinkel, Michiel, red. (2001), Tutte polynom , Encyclopedia of Mathematics , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Tutte-polynom (engelska) på Wolfram MathWorld- webbplatsen .
PlanetMath Kromatiskt polynom
Steven R. Pagano: Matroider och signerade grafer
Sandra Kingan: Matroidteori . Många länkar.
Kod för beräkning av Tutte, Chromatic and Flow Polynomials av Gary Haggard, David J. Pearce och Gordon Royle: [1] (inte tillgänglig länk)