Tatta polynomium

Tatta -polynomiet ( Tatta-Whitney- polynomiet ) er et to-variabelt polynomium, der spiller en stor rolle i grafteori ; er defineret for enhver urettet graf og indeholder information om, hvor forbundet grafen er . Standardnotationen er . $T_{G}$

Oprindeligt studeret i algebraisk grafteori som en konstruktion til generalisering af tælleproblemer relateret til graffarvning og ingen steder nul flows , senere blev der fundet en forbindelse med Jones polynomiet fra knudeteori og de statistiske summer af Potts-modellen fra statistisk fysik . Polynomiet er oprindelsen til nogle beregningsmæssige problemer teoretisk datalogi .

Polynomiet har flere ækvivalente definitioner: det svarer til Whitney -rangpolynomiet , Tutt-dikromatisk polynomium og Fortuin-Castelyn tilfældige klyngemodellen (efter en lille transformation) . Et polynomium er i det væsentlige en genererende funktion for antallet af kanter af sæt af en given størrelse og forbundne komponenter og har en direkte generalisering i matroidteori . Polynomiet er også en invariant af den mest generelle form for grafer, som kan defineres ved rekursionen af fjernelse - kontraktion . Nogle bøger om grafteori og matroider afsætter hele kapitler til dette koncept [1] [2] [3] .

Definitioner

For en urettet graf er Tatta-polynomiet defineret som: $G=(V,E)$

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

hvor betyder antallet af forbundne komponenter i grafen . Det kan ses af definitionen, at polynomiet er veldefineret og polynomiet i og i . $k(A)$ $(V,A)$ $T_{G}$ $x$ $y$

Den samme definition kan gives i anden notation, hvis den er angivet med grafens rangering . Så er Whitney-genereringsfunktionen for rangen defineret som: $r(A)=|V|-k(A)$ $(V,A)$

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

De to funktioner er ækvivalente, som vist ved en simpel ændring af variable:

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

Tutts dikromatiske polynomium er resultatet af en anden simpel transformation: $Q_{G}$

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

Tutts oprindelige definition for en forbundet graf er ækvivalent (men denne ækvivalens er teknisk vanskeligere at vise): $T_{G}$ $G$

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

hvor betyder antallet af spændende træer af "intern aktivitet og ekstern aktivitet ". ${\displaystyle t_{ij))$ $jeg$ $j$

Den tredje definition bruger deletion-pull rekursion . Sammentrækning af en kant af en graf er en graf, der opnås ved at flette hjørner og slette en kant , og notation betyder, at kun kanten slettes . Så er Tatta-polynomiet defineret ved rekursion: $g/uv$ $G$ $u$ $v$ $UV$ $G-uv$ $UV$

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

hvis er hverken en løkke eller en bro , med basistilfældet: $e$

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

hvis den indeholder broer og sløjfer og ingen andre kanter. Især hvis ikke indeholder kanter. $G$ $jeg$ $j$ $T_{G}=1$ $G$

Fortuin-Castelyn tilfældige klyngemodellen [4] giver en anden tilsvarende definition [5] :

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

er ækvivalent ved transformation [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 )}.

Egenskaber

Tatta-polynomiet dekomponerer i forbundne komponenter - hvis det er foreningen af usammenhængende grafer og , så: $G$ $H$ $H'$

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

Hvis er plan og angiver dens dobbelte graf , så: $G$ $G^{*}$

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

Især er det kromatiske polynomium i en plan graf strømningspolynomiet af dets dual.

Eksempler

Isomorfe grafer har de samme Tutt-polynomier, men det modsatte er ikke sandt. For eksempel er Tatta-polynomiet for ethvert træ med kanter . $m$ $x^{m}$

Tutts polynomier udgives ofte som en række- og kolonnekoefficienttabel med termer . For eksempel Tatta-polynomiet af Petersen-grafen , ${\displaystyle t_{ij))$ ${\displaystyle x^{i}y^{j))$ $jeg$ $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 er skrevet i form af følgende tabel:

0	36	84	75	35	9	en
36	168	171	65	ti
120	240	105	femten
180	170	tredive
170	70
114	12
56
21
6
en

Et andet eksempel, Tatta-polynomiet på oktaedergrafen er:

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

Historie

William Tutts interesse for sletnings-sammentrækningsformlen opstod under hans studietid på Trinity College (Cambridge) og var inspireret af perfekte rektangler [7] og spændende træer . Han brugte ofte formlen i forskning og "blev overrasket, da han opdagede andre interessante funktioner på grafer, invariante under isomorfismer , med lignende rekursive formler" [8] . Ronald Foster bemærkede, at det kromatiske polynomium var en sådan funktion, og Tutt begyndte at opdage andre. Den oprindelige terminologi for grafinvarianter, der tilfredsstiller deletions-kontraktionsrekursionen, var W-funktionen , og han brugte udtrykket V-funktion til tilfældet med komponentmultiplikation. Tutt skrev: "Leg med W-funktioner fik jeg et polynomium i to variable, hvorfra man kunne få et kromatisk polynomium eller et flowpolynomium ved at tildele en variabel til nul og korrigere fortegnene" [8] . Tutt kaldte denne funktion dikromatisk og viste, at det er en to-variabel generalisering af et kromatisk polynomium, men dette polynomium omtales normalt som Tutts polynomium. Ifølge Tutt, "Dette kunne være frustrerende for Hassler Whitney , som brugte lignende koefficienter og ikke forsøgte at tilpasse dem til de to variable." (Der er forvirring [9] mellem udtrykkene "bikromat" og "bikromatisk polynomium", introduceret af Tutt i et andet papir og lidt anderledes.) En generalisering af Tutts polynomium for matroider blev udgivet af Crapo, selvom det allerede var optrådt i Tutts afhandlinger [10] .

Uafhængigt, mens han arbejdede med algebraisk grafteori , begyndte Potts at studere partitionsfunktioner af nogle modeller af statistisk mekanik i 1952. I et papir fra 1972 om den tilfældige klyngemodel gav en generalisering af Potts-modellen , Fortuin og Casteleyn [4] et kombineret udtryk, der viste forholdet mellem denne model og Tatta-polynomiet [10] .

Specialiseringer

På forskellige punkter og linjer i planet giver Tatta-polynomiet værdier, der studeres i sig selv inden for forskellige felter af matematik og fysik. En del af tiltrækningen ved Tutts polynomium skyldes foreningen af metoden til at analysere disse størrelser. $(x,y)$

Kromatisk polynomium

Ved bliver Tatta-polynomiet til et kromatisk polynomium, $y=0$

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

hvor angiver antallet af forbundne komponenter i grafen . $k(G)$ $G$

For et heltal er værdien af det kromatiske polynomium lig med antallet af farvelægninger af grafens hjørner ved hjælp af farver. Det er klart, at det ikke afhænger af sæt af farver. Det er mindre tydeligt, at funktionen er et polynomium med heltalskoefficienter. For at forstå dette, bemærk: $\lambda$ $\chi _{G}(\lambda )$ $G$ $\lambda$ $\chi _{G}(\lambda )$ $\lambda$

Hvis grafen har spidser og ingen kanter, så . $G$ $n$ ${\displaystyle \chi _{G}(\lambda )=\lambda ^{n))$
Hvis grafen indeholder en løkke (en kant, der forbinder et toppunkt med det samme toppunkt), så . $G$ $\chi _{G}(\lambda )=0$
Hvis er en kant, der ikke er en løkke, så $e$

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

Disse tre betingelser tillader os at beregne ved hjælp af en sekvens af deletioner og sammentrækninger. Disse operationer garanterer dog ikke, at en anden rækkefølge af operationer vil føre til det samme resultat. Unikitet er garanteret af det faktum, at tæller ting uafhængigt af rekursion. I særdeleshed, $\chi _{G}(\lambda )$ $\chi _{G}(\lambda )$

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

angiver antallet af acykliske orienteringer.

Jones polynomium

Langs hyperbelen reduceres Tutt-polynomiet i den plane graf til Jones-polynomiet for den tilhørende alternerende knude . $xy=1$

Individuelle point

(2.1)

$T_{G}(2,1)$ tæl antallet af træer , det vil sige antallet af acykliske delmængder af kanter.

(1.1)

$T_{G}(1,1)$ tæller antallet af skeletter ( acykliske undergrafer med samme antal forbundne komponenter som grafen ). Hvis grafen er forbundet, tælles antallet af spændende træer. $G$ $T_{G}(1,1)$

(1,2)

$T_{G}(1,2)$ tæller antallet af spændende subgrafer med det samme antal forbundne komponenter som grafen . $G$

(2.0)

$T_{G}(2,0)$ tæller antallet af acykliske orienteringer af grafen [11] . $G$

(0,2)

$T_{G}(0,2)$ tæller antallet af stærkt forbundne orienteringer af grafen [12] . $G$

(0,−2)

Hvis grafen er en 4-regulær graf, så $G$

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

tæller antallet af acykliske orienteringer af grafen . Her er antallet af forbundne komponenter i grafen [11] . $G$ $k(G)$ $G$

(3,3)

Hvis grafen er - et gitter , så tæller antallet af måder at tesselere et rektangel med bredde og højde med T-tetromino- fliser [13] [14] $G$ $m\ gange n$ $2T_{G}(3,3)$ $4m$ $4n$

Hvis grafen er plan , så er den lig med summen af de vægtede Euler-orienteringer i den midterste graf af grafen , hvor vægten er fra 2 til antallet af saddelspidser i orienteringen (det vil sige antallet af hjørner med kanter i den cykliske rækkefølge "ind, ud, ind ud") [15] . $G$ $2T_{G}(3,3)$ $G$

Potts og Ising modellerne

For en hyperbel i et fly : $xy$

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

Tutt-polynomiet reducerer til partitionsfunktionen i Ising-modellen , studeret i statistisk fysik . Især langs hyperbelen er de to relateret til ligningen [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)

I særdeleshed:

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

for alle komplekse . $\alfa$

Mere generelt, hvis vi for nogen positiv definerer en hyperbel: $q$

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

derefter reducerer Tutt-polynomiet til partitionsfunktionen af Potts-modellen med tilstande. Forskellige fysiske mængder analyseret ved hjælp af Potts-modellen går i specifikke dele . $q$ ${\displaystyle H_{q))$

Korrespondancer mellem Potts-modellen og Tutt-flyet [17] .

Potts model	Tatta polynomium
Ferromagnetisk	positiv gren ${\displaystyle H_{q))$
Antiferromagneter	Negativ gren med ${\displaystyle H_{q))$ $y>0$
Varme	Asymptote til ${\displaystyle H_{q))$ $y=1$
Lavtemperatur ferromagneter	Asymptote af den positive gren til ${\displaystyle H_{q))$ $x=1$
Nul temperatur ferromagneter	Farvelægning af en graf i q- farver , dvs. $x=1-q,y=0$

Flowpolynomium

For , Tatta-polynomiet bliver til et flow-polynomium studeret i kombinatorik. For en forbundet urettet graf og et heltal ingen steder er nul -flow tildelingen af "flow" værdier til kanter af vilkårlig orientering i grafen , sådan at summen af input og output flows ved hvert toppunkt er kongruent modulo . Strømningspolynomiet betyder antallet af ingensteds nul -strømme. Denne værdi er direkte relateret til det kromatiske polynomium. Faktisk, hvis det er en plan graf , er grafens kromatiske polynomium ækvivalent med flowpolynomiet for dens dobbelte graf i den forstand, at følgende udsagn gælder (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)

Forbindelsen med Tatta-polynomiet er givet ved ligheden:

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

Vitalitetspolynomium

Ved bliver Tatta-polynomiet til overlevelsespolynomiet studeret i netværksteori. For en forbundet graf fjernes enhver kant med sandsynlighed , hvilket simulerer tilfældige udfald af kanten. Så er overlevelsespolynomiet en funktion af , et polynomium af , hvilket giver sandsynligheden for, at ethvert par af hjørner i forbliver forbundet efter at en kant er faldet. Forbindelsen med Tatta-polynomiet er givet af ligheden $x=1$ $G$ $s$ $R_{G}(p)$ $s$ $G$

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

Dikromatisk polynomium

Tutt definerede også en tæt 2-variabel generalisering af det kromatiske polynomium, grafens dikromatiske polynomium:

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

hvor er antallet af forbundne komponenter i spændingsundergrafen . Det er relateret til Whitney rang polynomiet ved ligheden: $k(A)$ $(V,A)$

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

Det dikromatiske polynomium er ikke generaliseret til matroider, fordi det ikke er en egenskab ved matroider - forskellige grafer med samme matroide kan have forskelligt antal forbundne komponenter. $k(A)$

Relaterede polynomier

Martins polynomium

Martin-polynomiet af en rettet 4-regulær graf blev defineret af Pierre Martin i 1977 [18] . Han viste, at hvis er en plan graf og er dens rettede mediangraf , så $m_{\vec {G}}(x)$ ${\vec {G}}$ $G$ ${\vec {G}}_{m}$

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

Algoritmer

Formel til fjernelse - sammentrækninger

Anvendelse af sletnings-kontraktionsformlen for Tatta-polynomiet:

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

hvor er hverken en løkke eller en bro, giver en rekursiv algoritme til beregning af et polynomium - en hvilken som helst passende kant vælges , og formlen anvendes, indtil der kun er løkker og broer tilbage. De resulterende monomialer er nemme at beregne. $e$ $e$

Op til en polynomiel faktor kan udførelsestiden for denne algoritme udtrykkes i form af antallet af hjørner og antallet af kanter på grafen: $t$ $n$ $m$

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

rekursiv relation, der definerer Fibonacci-tal med løsning [19] .

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

Analysen kan forbedres i værdien af polynomialfaktoren for antallet af spændingstræer i inputgrafen [20] . For sparsomme grafer er algoritmens køretid . For almindelige gradgrafer kan antallet af spændende træer begrænses af værdien $\tau (G)$ $m=O(n)$ $O(\exp(n))$ $k$

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

hvor

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

For eksempel [21] [22] :

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

I praksis bruges isomorfikontrol for at undgå nogle rekursive opkald . Denne tilgang fungerer godt for meget sparsomme grafer og grafer med mange symmetrier, mens hastigheden af algoritmen afhænger af kantvalgsmetoden [20] [23] [24] . $e$

Gaussisk undtagelse

I nogle begrænsede tilfælde kan Tutt-polynomiet beregnes i polynomiel tid på grund af det faktum, at Gauss-eliminering beregner determinanten og Pfaffian effektivt . Disse algoritmer er i sig selv et vigtigt resultat af algebraisk grafteori og statistisk mekanik .

$T_{G}(1,1)$ er lig med antallet af spændingstræer i den forbundne graf. Den kan beregnes i polynomiel tid som determinanten af den maksimale hovedsubmatrix af en grafs Kirchhoff-matrix , et tidligt resultat fra algebraisk grafteori kendt som matrixtræsætningen . På samme måde kan dimensionen af cykelrummet beregnes i polynomiel tid ved hjælp af Gauss-elimineringsmetoden . $\tau (G)$ $G$ $T_{G}(-1,-1)$

For plane grafer kan fordelingsfunktionen af Ising-modellen, dvs. Tutt-polynomiet på en hyperbel , udtrykkes som en Pfaffian og beregnes effektivt med FKT-algoritmen . Denne idé blev udviklet af Fischer , Castelein og Temperley for at beregne antallet af dominobrikker , der dækker en plan gittermodel . $H_2$

Monte Carlo metode til Markov kæder

Ved at bruge Monte Carlo-metoden for Markov-kæder , kan man vilkårligt godt tilnærme Tutt-polynomiet langs grenen af fordelingsfunktionen af den ferromagnetiske Ising-model. Denne tilgang udnytter det tætte forhold mellem Ising-modellen og problemet med at tælle matchninger i en graf. Ideen med denne tilgang, på grund af Jerram og Sinclair [25] , er at danne en Markov-kæde, hvis tilstande svarer til matchninger af inputgrafen. Overgange bestemmes ved tilfældigt at vælge kanter, og matchninger ændres i overensstemmelse hermed. Den resulterende Markov-kæde blander sig hurtigt og fører til "rimelig tilfældige" matchninger, der kan bruges til at opdage distributionsfunktionen ved hjælp af tilfældig stikprøve. Den resulterende algoritme er Approximate Polynomial Time Scheme (FPRAS). $H_2$

Beregningsmæssig kompleksitet

Der er nogle beregningsmæssige problemer forbundet med Tatta-polynomiet. Den mest ligetil algoritme

Input Kurve

G

Produktion Odds

T_{G}

Især tillader udledningen beregning , hvilket svarer til at tælle 3-farvninger af grafen . Dette problem er #P-complete , selvom det er begrænset til familien af plane grafer , så problemet med at beregne koefficienterne for Tutt-polynomiet for en given graf er #P-hard selv for plane grafer . $T_{G}(-2,0)$ $G$

Meget mere opmærksomhed er blevet givet til en familie af problemer kaldet Tutte defineret for ethvert komplekst par : $(x,y)$ $(x,y)$

Input Kurve

G

Produktion Betyder

T_{G}(x,y)

Sværhedsgraden af denne opgave varierer afhængigt af koordinaterne . $(x,y)$

Præcis beregning

Hvis og er ikke-negative heltal, hører problemet til klasse #P . I det generelle tilfælde, for heltalspar, indeholder Tatta-polynomiet negative termer, hvilket placerer problemet i kompleksitetsklassen GapP , lukningen af klassen #P ved subtraktion. For rationelle koordinater kan man definere en rationel analog af klassen #P [26] . $x$ $y$ $T_{G}(x,y)$ $(x,y)$

Den beregningsmæssige kompleksitet af en nøjagtig beregning falder i to klasser for . Problemet er #P-svært, medmindre det ligger på en hyperbel eller er et af punkterne $T_{G}(x,y)$ $x,y\in \mathbb {C}$ $(x,y)$ $H_1$

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

I disse tilfælde kan problemet løses i polynomisk tid [27] . Hvis problemet er begrænset til klassen af plane grafer, bliver problemet ved hyperbelens punkter beregnet i polynomisk tid. Alle andre punkter forbliver #P-hårde selv for todelte plane grafer [28] . I sit papir om dikotomien af plane grafer hævder Vertigan, at det samme resultat er sandt, hvis der pålægges yderligere begrænsninger på graferne (graden af toppunktet overstiger ikke tre), bortset fra punktet , som tæller ingen steder-nul- flows og hvor problemet kan løses i polynomisk tid [29] . $H_2$ $T_{G}(0,-2)$ $\mathbb{Z } _{3}$

Disse resultater indeholder nogle vigtige specialtilfælde. For eksempel er problemet med at beregne fordelingsfunktionen af Ising-modellen #P-hårdt i det generelle tilfælde, selvom Onzangers og Fishers algoritmer løser det for flade gitter. Det er også #P-hårdt at beregne Jones-polynomiet. Endelig er beregningen af antallet af fire-farvninger af en plan graf #P-komplet, selvom problemet med løselighed er trivielt på grund af fire-farvesætningen . I modsætning hertil er det let at se, at det er #P-komplet at tælle antallet af tre-farvninger af en plan graf, da løselighedsproblemet er kendt for at være NP-komplet ifølge økonomisk reduktion .

Tilnærmelse

Spørgsmålet om, hvilke punkter der tillader tilnærmelsesalgoritmer, er blevet grundigt undersøgt. Bortset fra punkter, som kan beregnes nøjagtigt i polynomisk tid, er den eneste tilnærmelsesalgoritme kendt for Jerram og Sinclair (FPRAS) algoritmen, som virker for punkter på Ising hyperbelen for . Hvis inputgrafen er begrænset til tætte grafer med grad , så er der en FPRAS-algoritme, hvis [30] . $T_{G}(x,y)$ $H_2$ $y>0$ $\omega(n)$ $x\geqslant 1,y\geqslant 1$

Selvom situationen i tilfælde af tilnærmelse ikke er så godt forstået som for nøjagtige beregninger, er det kendt, at store områder af flyet er vanskelige at tilnærme [26] .

Se også

Bolobash-Riordan polynomium

Noter

↑ Bollobás, 1998 , s. kapitel 10.
↑ Biggs, 1993 , s. kapitel 13.
↑ Godsil, Royle, 2004 , kap. femten.
↑ 1 2 Fortuin, Kasteleyn, 1972 .
↑ Sokal, 2005 .
↑ Sokal, 2005 , s. lign. (2,26).
↑ Et perfekt rektangel er et rektangel, der kan opdeles i kvadrater og alle kvadrater har forskellige størrelser
↑ 12 Tutte , 2004 .
↑ Welch.
↑ 12 Farr , 2007 .
↑ 12 Welsh , 1999 .
↑ Las Vergnas, 1980 .
↑ Korn, Pak, 2004 .
↑ Se Korn og Pak ( 2003 ) for en kombinatorisk fortolkning af mange andre punkter.
↑ Las Vergnas, 1988 .
↑ Welsh, 1993 , s. 62.
↑ 12 Welsh, Merino, 2000 .
↑ Martin, 1977 .
↑ Wilf, 1986 , s. 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, walisisk, 1990 .
↑ Vertigan, walisisk, 1992 .
↑ Vertigan, 2005 .
↑ For tilfældet ≥ 1 og = 1, se Annan ( Annan 1994 ). For tilfældet ≥ 1 og > 1, se artiklen. Alon, Frieze og Welsh ( Alon, Frieze, Welsh 1995 ). $x$ $y$ $x$ $y$

Litteratur

Alon N., Frieze A., Welsh DJA Polynomiske tidsrandomiserede tilnærmelsesskemaer for Tutte-Gröthendieck-invarianter: Det tætte tilfælde // Random Structures and Algorithms. - 1995. - T. 6 , no. 4 . — S. 459–478 . - doi : 10.1002/rsa.3240060409 .
Annan JD En randomiseret approksimationsalgoritme til at tælle antallet af skove i tætte grafer // Combinatorics, Probability and Computing . - 1994. - T. 3 , udg. 3 . — S. 273–283 . - doi : 10.1017/S0963548300001188 .
Norman Biggs. Algebraisk grafteori. — 2. - Cambridge University Press , 1993. - ISBN 0-521-45897-8 .
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Proc. af det 47. årlige 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. Moderne grafteori. - Springer , 1998. - ISBN 978-0-387-98491-9 .
Fan Chung, S.-T. Yau. Belægninger, varmekerner og spændende træer // Electronic Journal of Combinatorics . - 1999. - T. 6 . - S. R12 .
Henry H. Crapo. Tutte-polynomiet // Aequationes Mathematicae. - 1969. - T. 3 , udg. 3 . — S. 211–229 . - doi : 10.1007/bf01817442 .
Graham E. Farr. Kombinatorik, kompleksitet og tilfældigheder. En hyldest til 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 og relation til andre 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. Utilnærmelighed af Tutte-polynomiet // Information og beregning . - 2008. - T. 206 , no. 7 . — S. 908–929 . - doi : 10.1016/j.ic.2008.04.003 .
Gary Haggard, David J. Pearce, Gordon Royle. Beregning af Tutte-polynomier // ACM-transaktioner på matematisk software . - 2010. - T. 37 , no. 3 . - C. Art. 24, 17 . - doi : 10.1145/1824801.1824802 .
F. Jaeger, DL Vertigan, DJA Welsh. Om den beregningsmæssige kompleksitet af Jones og Tutte polynomier // Mathematical Proceedings of the Cambridge Philosophical Society . - 1990. - T. 108 . — s. 35–53 . - doi : 10.1017/S0305004100068936 .
Mark Jerrum, Alistair Sinclair. Polynomial-tidstilnærmelsesalgoritmer til Ising-modellen // SIAM Journal on Computing . - 1993. - T. 22 , no. 5 . — S. 1087–1116 . - doi : 10.1137/0222066 .
Michael Korn, Igor Pak. Kombinatoriske evalueringer af Tutte-polynomiet . – 2003.
Michael Korn, Igor Pak. Fliselægning af rektangler med T-tetrominoer // Teoretisk datalogi . - 2004. - T. 319 , no. 1-3 . — S. 3–27 . - doi : 10.1016/j.tcs.2004.02.023 .
Michel Las Vergnas. Konveksitet i orienterede matroider // Journal of Combinatorial Theory . - 1980. - T. 29 , no. 2 . — S. 231–243 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(80)90082-9 .
Michel Las Vergnas. Om evalueringen ved (3, 3) af Tutte-polynomiet af en graf // Journal of Combinatorial Theory . - 1988. - T. 45 , no. 3 . — S. 367–372 . — ISSN 0095-8956 . - doi : 10.1016/0095-8956(88)90079-2 .
Pierre Martin. Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck (fransk) . - Joseph Fourier University , 1977. - (Ph.D.-afhandling).
David J. Pearce, Gary Haggard, Gordon Royle. Kantvalgsheuristik til beregning af Tutte-polynomier // Chicago Journal of Theoretical Computer Science. - 2010. - S. Artikel 6, 14 .
Kyoko Sekine, Hiroshi Imai, Seiichiro Tani. Algoritmer og beregninger (Cairns, 1995). - Springer , 1995. - T. 1004. - S. 224-233. — ( Forelæsningsnotater i Datalogi ). - doi : 10.1007/BFb0015427 .
Alan D. Sokal. Undersøgelser 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-polynomier // Fremskridt i anvendt matematik . - 2004. - T. 32 , no. 1-2 . — S. 5–9 . - doi : 10.1016/S0196-8858(03)00041-1 .
DL Vertigan, DJ Welsh. Tutte-planets beregningsmæssige kompleksitet: Bipartite-sagen // Combinatorics, Probability and Computing . - 1992. - Vol. 1 , udgave. 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 , no. 3 . — S. 690–712 . - doi : 10.1137/S0097539704446797 .
DJ walisisk. matroid teori . - Academic Press , 1976. - ISBN 012744050X .
Dominic Welsh. Kompleksitet: knob, farvelægning og tælling. - Cambridge University Press , 1993. - (London Mathematical Society Lecture Note Series). — ISBN 978-0521457408 .
Dominic Welsh. Tutte-polynomiet . — Tilfældige strukturer og 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 og Tutte-polynomiet // Journal of Mathematical Physics . - 2000. - T. 41 , no. 3 . - doi : 10.1063/1.533181 .
Herbert S. Wilf. Algoritmer og kompleksitet . - Prentice Hall , 1986. - ISBN 0-13-021973-8 .