Tatta polynom

Tatta polynomial ( Tatta-Whitney polynomial ) je dva-polynomial proměnné, který hraje velkou roli v teorii grafů ; je definován pro jakýkoli neorientovaný graf a obsahuje informace o tom, jak je graf propojen . Standardní notace je . $T_{G}$

Zpočátku studoval v algebraické teorii grafů jako konstrukt pro zobecňující problémy počítání související s barvením grafu a nikde nulové toky , později byla nalezena souvislost s Jonesovým polynomem z teorie uzlů a statistickými součty Pottsova modelu ze statistické fyziky . Polynom je původem některých výpočetních problémů teoretické informatice .

Polynom má několik ekvivalentních definic: je ekvivalentní Whitneyho hodnostnímu polynomu , Tuttově dichromatickému polynomu a Fortuin-Castelynovu modelu náhodného shluku (po mírné transformaci) . Polynom je v podstatě generující funkce pro počet hran množin dané velikosti a spojených komponent a má přímé zobecnění v teorii matroidů . Polynom je také invariantem nejobecnějšího tvaru pro grafy, který lze definovat rekurzí odstranění - kontrakce . Některé knihy o teorii grafů a matroidech věnují tomuto konceptu celé kapitoly [1] [2] [3] .

Definice

Pro neorientovaný graf je Tatta polynom definován jako: $G=(V,E)$

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

kde znamená počet připojených složek grafu . Z definice je vidět, že polynom je dobře definovaný a polynom v a v . $k(A)$ $(V,A)$ $T_{G}$ $X$ $y$

Stejná definice může být uvedena v jiném zápisu, pokud je označena hodností grafu . Potom je Whitneyova generující funkce pro hodnost definována jako: $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)))

Obě funkce jsou ekvivalentní, jak ukazuje jednoduchá změna proměnných:

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

Tuttův dichromatický polynom je výsledkem další jednoduché transformace: $Q_{G}$

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

Tuttova původní definice pro souvislý graf je ekvivalentní (ale tato ekvivalence je technicky obtížnější ukázat): $T_{G}$ $G$

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

kde znamená počet kostry "vnitřní činnosti a vnější činnosti ". $t_{ij}$ $i$ $j$

Třetí definice používá rekurzi delece-pull . Kontrakce hrany grafu je graf získaný sloučením vrcholů a smazáním hrany a zápis znamená vymazání pouze hrany . Potom je polynom Tatta definován rekurzí: $fotr$ $G$ $u$ $proti$ $UV$ $G-uv$ $UV$

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

if není ani smyčka ani most , se základním případem: $E$

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

pokud obsahuje mosty a smyčky a žádné další hrany. Zejména pokud neobsahuje hrany. $G$ $i$ $j$ $T_{G}=1$ $G$

Fortuin-Castelyn model náhodného shluku [4] poskytuje jinou ekvivalentní definici [5] :

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

je ekvivalentní při transformaci [6] : $T_{G}$

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

Vlastnosti

Tatta polynom se rozkládá na spojené složky - pokud jde o spojení disjunktních grafů a , pak: $G$ $H$ $H'$

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

Jestliže je rovinný a označuje jeho duální graf , pak: $G$ $G^{*}$

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

Zejména chromatický polynom rovinného grafu je tokový polynom jeho duálu.

Příklady

Izomorfní grafy mají stejné Tuttovy polynomy, ale obráceně to neplatí. Například polynom Tatta jakéhokoli stromu s hranami je . $m$ $x^{m}$

Tuttovy polynomy jsou často publikovány jako řádková a sloupcová tabulka koeficientů . Například Tattův polynom Petersenova grafu , $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}}

Je zapsán ve formě následující tabulky:

0	36	84	75	35	9	jeden
36	168	171	65	deset
120	240	105	patnáct
180	170	třicet
170	70
114	12
56
21
6
jeden

Dalším příkladem je Tatta polynom oktaedronového grafu:

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

Zájem Williama Tutta o vzorec delece-kontrakce vznikl během jeho studentských let na Trinity College (Cambridge) a byl inspirován dokonalými obdélníky [7] a kosočtverci . Často používal vzorec ve výzkumu a "byl překvapen, když objevil další zajímavé funkce na grafech, invariantní pod izomorfismy , s podobnými rekurzivními vzorci" [8] . Ronald Foster si všiml, že jednou z takových funkcí je chromatický polynom , a Tutt začal objevovat další. Původní terminologií pro grafové invarianty vyhovující rekurzi delece-kontrakce byla W-funkce a pro případ násobení komponent použil termín V-funkce . Tutt napsal: "Hraje si s W-funkcemi , dostal jsem polynom ve dvou proměnných, ze kterého se dal získat chromatický polynom nebo tokový polynom přiřazením jedné proměnné k nule a opravou znamének" [8] . Tutt nazval tuto funkci dichromatickou a ukázal, že jde o dvouproměnné zobecnění chromatického polynomu, ale tento polynom je obvykle označován jako Tuttův polynom. Podle Tutta "to by mohlo být frustrující pro Hassler Whitney , který používal podobné koeficienty a nesnažil se je přizpůsobit dvěma proměnným." (Mezi pojmy „bichromát“ a „bichromatický polynom“, které zavedl Tutt v jiném článku a mírně odlišné, dochází k záměně [9] .) Zobecnění Tuttova polynomu pro matroidy publikoval Crapo, ačkoli se již objevil v Tuttových tezích [10] .

Nezávisle na tom, když pracoval s algebraickou teorií grafů začal Potts v roce 1952 studovat rozdělovací funkce některých modelů statistické mechaniky . kombinovaný výraz, který ukázal vztah tohoto modelu s Tattovým polynomem [10] .

Specializace

V různých bodech a liniích v rovině poskytuje polynom Tatta hodnoty, které jsou samy o sobě studovány v různých oblastech matematiky a fyziky. Část přitažlivosti Tuttova polynomu je způsobena sjednocením metody analýzy těchto veličin. $(x,y)$

Chromatický polynom

V , se Tatta polynom změní na chromatický polynom, $y=0$

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

kde označuje počet připojených složek grafu . $k(G)$ $G$

Pro celé číslo je hodnota chromatického polynomu rovna počtu zabarvení vrcholů grafu pomocí barev. Je jasné, že nezáleží na sadě barev. Méně jasné je, že funkce je polynom s celočíselnými koeficienty. Abyste tomu porozuměli, poznamenejte si: $\lambda$ $\chi _{G}(\lambda )$ $G$ $\lambda$ $\chi _{G}(\lambda )$ $\lambda$

Pokud má graf vrcholy a žádné hrany, pak . $G$ $n$ ${\displaystyle \chi _{G}(\lambda )=\lambda ^{n))$
Pokud graf obsahuje smyčku (hranu spojující vrchol se stejným vrcholem), pak . $G$ $\chi _{G}(\lambda )=0$
Pokud je hrana, která není smyčkou, pak $E$

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

Tyto tři podmínky nám umožňují počítat podle sekvence delecí a kontrakcí. Tyto operace však nezaručují, že jiné pořadí operací povede ke stejnému výsledku. Jedinečnost je zaručena tím, že počítá věci nezávisle na rekurzi. Zejména, $\chi _{G}(\lambda )$ $\chi _{G}(\lambda )$

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

udává počet acyklických orientací.

Jonesův polynom

Podél hyperboly se Tuttův polynom rovinného grafu redukuje na Jonesův polynom souvisejícího střídavého uzlu . $xy=1$

Jednotlivé body

(2.1)

$T_{G}(2,1)$ spočítat počet stromů , tedy počet acyklických podmnožin hran.

(1.1)

$T_{G}(1,1)$ počítá počet koster ( acyklické podgrafy se stejným počtem připojených komponent jako graf ). Pokud je graf propojen, počítá se počet kostry. $G$ $T_{G}(1,1)$

(1,2)

$T_{G}(1,2)$ počítá počet podgrafů zahrnujících stejný počet připojených komponent jako graf . $G$

(2.0)

$T_{G}(2,0)$ počítá počet acyklických orientací grafu [11] . $G$

(0,2)

$T_{G}(0,2)$ počítá počet silně propojených orientací grafu [12] . $G$

(0,−2)

Pokud je graf 4-běžný graf, pak $G$

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

počítá počet acyklických orientací grafu . Zde je počet připojených složek grafu [11] . $G$ $k(G)$ $G$

(3,3)

Pokud je graf - mřížka , pak počítá počet způsobů, jak mozaikovat obdélník s šířkou a výškou pomocí dlaždic T-tetromino [13] [14] $G$ $m\krát n$ $2T_{G}(3,3)$ $4m$ $4n$

Pokud je graf rovinný , pak se rovná součtu vážených Eulerových orientací ve středním grafu grafu , kde váha je od 2 do počtu sedlových vrcholů orientace (tj. počtu vrcholů s hrany v cyklickém pořadí "dovnitř, ven, dovnitř" [15] . $G$ $2T_{G}(3,3)$ $G$

Modely Potts a Ising

Pro hyperbolu v rovině : $xy$

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

Tuttův polynom se redukuje na rozdělovací funkci Isingova modelu , studovaného ve statistické fyzice . Zejména podél hyperboly tyto dva souvisí s rovnicí [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)

Zejména:

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

pro všechny složité . $\alpha$

Obecněji, pokud pro jakýkoli klad definujeme hyperbolu: $q$

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

pak se Tuttův polynom redukuje na rozdělovací funkci Pottsova modelu se stavy. Různé fyzikální veličiny analyzované pomocí Pottsova modelu přecházejí do specifických částí . $q$ ${\displaystyle H_{q))$

Korespondence mezi Pottsovým modelem a Tuttovou rovinou [17] .

Pottsův model	Tatta polynom
Feromagnetické	pozitivní větev ${\displaystyle H_{q))$
Antiferomagnetika	Negativní větev s ${\displaystyle H_{q))$ $y>0$
Teplo	Asymptota k ${\displaystyle H_{q))$ $y=1$
Nízkoteplotní feromagnetika	Asymptota kladné větve k ${\displaystyle H_{q))$ $x=1$
Feromagnetika s nulovou teplotou	Vybarvování grafu v q barvách , tj. $x=1-q,y=0$

Tokový polynom

Pro , Tatta polynom se změní na tokový polynom studovaný v kombinatorice. Pro spojený neorientovaný graf a celé číslo nikde nulový tok je přiřazení hodnot „toků“ hranám libovolné orientace v grafu tak, že součet vstupních a výstupních toků v každém vrcholu je shodný modulo . Polynom toku znamená počet nulových toků. Tato hodnota přímo souvisí s chromatickým polynomem. Ve skutečnosti, pokud je rovinný graf , chromatický polynom grafu je ekvivalentní tokovému polynomu jeho duálního grafu v tom smyslu, že platí následující tvrzení (Tatt): $x=0$ $G$ $k$ $k$ $1,2,\tečky ,k-1$ $G$ $k$ $C_{G}(k)$ $k$ $G$ $G$ $G^{*}$

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

Spojení s Tatta polynomem je dáno rovností:

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

Polynom vitality

V , se polynom Tatta změní na polynom přežití studovaný v teorii sítí. U spojeného grafu je jakákoli hrana odstraněna s pravděpodobností , což simuluje náhodné výpadky hrany. Pak je polynom přežití funkcí , polynom , který dává pravděpodobnost, že jakákoliv dvojice vrcholů v zůstane spojena poté, co hrana spadne. Souvislost s Tatta polynomem je dána rovností $x=1$ $G$ $p$ $R_{G}(p)$ $p$ $G$

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

Dichromatický polynom

Tutt také definoval blízké 2-proměnné zobecnění chromatického polynomu, grafový dichromatický polynom:

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

kde je počet připojených komponent rozpětí podgrafu . Souvisí s Whitneyho hodnostním polynomem podle rovnosti: $k(A)$ $(V,A)$

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

Dichromatický polynom není zobecněn na matroidy, protože není vlastností matroidů – různé grafy se stejným matroidem mohou mít různý počet spojených komponent. $k(A)$

Související polynomy

Martinův polynom

Martinův polynom orientovaného 4-pravidelného grafu definoval Pierre Martin v roce 1977 [18] . Ukázal, že jestliže je rovinný graf a je jeho orientovaným mediánovým grafem , pak $m_{\vec {G}}(x)$ ${\vec {G}}$ $G$ ${\vec {G}}_{m}$

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

Algoritmy

Vzorec pro odstranění - kontrakce

Aplikace delečního - kontrakčního vzorce pro Tatta polynom:

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

kde není ani smyčka ani můstek, poskytuje rekurzivní algoritmus pro výpočet polynomu - vybere se jakákoliv vhodná hrana a vzorec se použije, dokud nezůstanou pouze smyčky a můstky. Výsledné monomiály lze snadno vypočítat. $E$ $E$

Až do polynomiálního faktoru lze dobu provádění tohoto algoritmu vyjádřit počtem vrcholů a počtem hran grafu: $t$ $n$ $m$

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

rekurzivní relace, která definuje Fibonacciho čísla s řešením [19] .

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

Analýza může být vylepšena o hodnotu polynomického faktoru počtu kostry vstupního grafu [20] . Pro řídké grafy s dobou běhu algoritmu je . U běžných stupňových grafů může být počet kostry omezen hodnotou $\tau (G)$ $m=O(n)$ $O(\exp(n))$ $k$

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

kde

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

Například [21] [22] :

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

V praxi se kontrola izomorfismu používá, aby se zabránilo některým rekurzivním voláním . Tento přístup funguje dobře pro velmi řídké grafy a grafy s mnoha symetriemi, přičemž rychlost algoritmu závisí na metodě výběru hran [20] [23] [24] . $E$

Gaussova výjimka

V některých omezených případech může být Tuttův polynom spočítán v polynomiálním čase díky skutečnosti, že Gaussova eliminace počítá determinant a Pfaffian efektivně . Tyto algoritmy jsou samy o sobě důležitým výsledkem algebraické teorie grafů a statistické mechaniky .

$T_{G}(1,1)$ se rovná počtu kostry připojeného grafu. Lze jej vypočítat v polynomiálním čase jako determinant maximální hlavní podmatice Kirchhoffovy matice grafu , což je časný výsledek algebraické teorie grafů známé jako teorém maticového stromu . Podobně lze pomocí Gaussovy eliminační metody vypočítat rozměr prostoru kola v polynomiálním čase . $\tau (G)$ $G$ $T_{G}(-1,-1)$

Pro rovinné grafy lze distribuční funkci Isingova modelu, tj. Tuttův polynom na hyperbole , vyjádřit jako Pfaffian a efektivně vypočítat pomocí FKT algoritmu . Tuto myšlenku vyvinuli Fischer , Castelein a Temperley k výpočtu počtu kostek domina pokrývajících model rovinné mříže . $H_2$

Metoda Monte Carlo pro Markovovy řetězy

Pomocí metody Monte Carlo pro Markovovy řetězce lze libovolně dobře aproximovat Tuttův polynom podél větve ekvivalentně distribuční funkce feromagnetického Isingova modelu. Tento přístup využívá úzkého vztahu mezi Isingovým modelem a problémem počítání shod v grafu. Myšlenkou tohoto přístupu je podle Jerrama a Sinclaira [25] vytvořit Markovův řetězec , jehož stavy odpovídají shodám vstupního grafu. Přechody jsou určeny náhodným výběrem hran a odpovídajícím způsobem se upravují shody. Výsledný Markovův řetězec se rychle mísí a vede k „přiměřeně náhodným“ shodám, které lze použít k objevení distribuční funkce pomocí náhodného vzorkování. Výsledný algoritmus je Approximate Polynomial Time Scheme (FPRAS). $H_2$

Výpočetní složitost

S Tattovým polynomem jsou spojeny některé výpočetní problémy. Nejjednodušší algoritmus

Vstup Graf

G

Výstup Kurzy

T_{G}

Odvození umožňuje zejména počítat , což je ekvivalentní počítání 3 zabarvení grafu . Tento problém je #P-complete , i když je omezen na rodinu rovinných grafů , takže problém výpočtu koeficientů Tuttova polynomu pro daný graf je #P-hard i pro rovinné grafy . $T_{G}(-2,0)$ $G$

Mnohem více pozornosti bylo věnováno rodině problémů zvaných Tutte definovaných pro jakýkoli komplexní pár : $(x,y)$ $(x,y)$

Vstup Graf

G

Výstup Význam

T_{G}(x,y)

Obtížnost tohoto úkolu se liší v závislosti na souřadnicích . $(x,y)$

Přesný výpočet

Pokud a jsou nezáporná celá čísla, problém patří do třídy #P . V obecném případě, pro celočíselné páry, Tatta polynom obsahuje záporné členy, což dává problém do třídy složitosti GapP , uzavření třídy #P odečtením. Pro racionální souřadnice lze definovat racionální analog třídy #P [26] . $X$ $y$ $T_{G}(x,y)$ $(x,y)$

Výpočetní složitost přesného výpočtu spadá do dvou tříd pro . Problém je #P-těžký, pokud neleží na hyperbole nebo není jedním z bodů $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))

V těchto případech je problém řešitelný v polynomiálním čase [27] . Pokud je problém omezen na třídu rovinných grafů, v bodech hyperboly se problém stane vyčíslitelným v polynomiálním čase. Všechny ostatní body zůstávají #P-tvrdé i pro bipartitní rovinné grafy [28] . Vertigan ve svém článku o dichotomii rovinných grafů tvrdí, že stejný výsledek platí, pokud jsou na grafy uvalena další omezení (stupeň vrcholu nepřesahuje tři), s výjimkou bodu , který nepočítá toky nikde nula . a při kterém je problém řešitelný v polynomiálním čase [29] . $H_2$ $T_{G}(0,-2)$ $\mathbb{Z } _{3}$

Tyto výsledky obsahují některé důležité speciální případy. Například problém výpočtu distribuční funkce Isingova modelu je v obecném případě #P-těžký, ačkoliv algoritmy Onzangera a Fishera jej řeší pro ploché svazy. Také výpočet Jonesova polynomu je #P-těžký. Konečně, výpočet počtu čtyř zabarvení rovinného grafu je #P-úplný, i když problém řešitelnosti je triviální díky větě o čtyřech barvách . Naproti tomu je snadné vidět, že počítání počtu tří zabarvení rovinného grafu je #P-úplné, protože problém řešitelnosti je znám jako NP-úplný podle ekonomické redukce .

Aproximace

Otázka, které body umožňují aproximační algoritmy, byla dobře prostudována. Kromě bodů, které lze přesně vypočítat v polynomiálním čase, je jediným známým aproximačním algoritmem Jerramův a Sinclairův (FPRAS) algoritmus, který pracuje pro body na Isingově hyperbole pro . Pokud je vstupní graf omezen na husté grafy se stupněm , pak existuje algoritmus FPRAS if [30] . $T_{G}(x,y)$ $H_2$ $y>0$ $\omega(n)$ $x\geqslant 1,y\geqslant 1$

Přestože situace v případě aproximace není tak dobře pochopena jako u exaktních výpočtů, je známo, že velké plochy roviny je obtížné aproximovat [26] .

Viz také

Bolobash-Riordanův polynom

Poznámky

↑ Bollobás, 1998 , s. kapitola 10.
↑ Biggs, 1993 , str. kapitola 13.
↑ Godsil, Royle, 2004 , kap. patnáct.
↑ 1 2 Fortuin, Kasteleyn, 1972 .
↑ Sokal, 2005 .
↑ Sokal, 2005 , str. ekv. (2,26).
↑ Dokonalý obdélník je obdélník, který lze rozdělit na čtverce a všechny čtverce mají různé velikosti
↑ 12 Tutte , 2004 .
↑ Welch.
↑ 12 Farr , 2007 .
↑ 12. Velština , 1999 .
↑ Las Vergnas, 1980 .
↑ Korn, Pak, 2004 .
↑ Viz Korn a Pak ( 2003 ) pro kombinatorickou interpretaci mnoha dalších bodů.
↑ Las Vergnas, 1988 .
↑ Velština, 1993 , s. 62.
↑ 12 Velština, Merino, 2000 .
↑ Martin, 1977 .
↑ Wilf, 1986 , str. 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, Wales, 1990 .
↑ Vertigan, Wales, 1992 .
↑ Vertigan, 2005 .
↑ Pro případ ≥ 1 a = 1 viz Annan ( Annan 1994 ). Pro případ ≥ 1 a > 1 viz článek. Alon, Frieze a Welsh ( Alon, Frieze, Welsh 1995 ). $X$ $y$ $X$ $y$

Literatura

Alon N., Frieze A., Welsh DJA Polynomiální časově randomizovaná aproximační schémata pro Tutte-Gröthendieck invarianty: Hustý případ // Random Structures and Algorithms. - 1995. - T. 6 , no. 4 . — S. 459–478 . - doi : 10.1002/rsa.3240060409 .
Annan JD Randomizovaný aproximační algoritmus pro počítání počtu lesů v hustých grafech // Kombinatorika, pravděpodobnost a výpočetní technika . - 1994. - T. 3 , vydání. 3 . — S. 273–283 . - doi : 10.1017/S0963548300001188 .
Norman Biggs. Algebraická teorie grafů. — 2. - Cambridge University Press , 1993. - ISBN 0-521-45897-8 .
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. Proč. 47. výročního sympozia IEEE o základech počítačových věd (FOCS 2008). - 2008. - S. 677-686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 .
Béla Bollobas. Moderní teorie grafů. - Springer , 1998. - ISBN 978-0-387-98491-9 .
Fan Chung, S.-T. Yau. Krytiny, tepelná jádra a kostry // Electronic Journal of Combinatorics . - 1999. - T. 6 . - S. R12 .
Henry H. Crapo. Tutteův polynom // Aequationes Mathematicae. - 1969. - T. 3 , vydání. 3 . — S. 211–229 . - doi : 10.1007/bf01817442 .
Graham E. Farr. Kombinatorika, složitost a náhoda. Pocta Dominic Welsh / Geoffrey Grimmett, Colin McDiarmid. - Oxford University Press , 2007. - T. 34. - S. 28-52. — (Oxfordská řada přednášek z matematiky a jejích aplikací). — ISBN 0-19-857127-5 .
Cees M. Fortuin, Pieter W. Kasteleyn. Na modelu náhodného shluku: I. Úvod a vztah k jiným modelům. — Fyzika . - Elsevier , 1972. - T. 57. - S. 536-564. - doi : 10.1016/0031-8914(72)90045-6 .
Chris Godsil, Gordon Royle. Algebraická teorie grafů. - Springer , 2004. - ISBN 978-0-387-95220-8 .
Hrají: Leslie Ann Goldberg, Mark Jerrum. Neaproximovatelnost Tutteho polynomu // Informace a výpočty . - 2008. - T. 206 , č. 7 . — S. 908–929 . - doi : 10.1016/j.ic.2008.04.003 .
Gary Haggard, David J. Pearce, Gordon Royle. Výpočet Tutteových polynomů // Transakce ACM v matematickém softwaru . - 2010. - T. 37 , č. 3 . - C. Čl. 24, 17 . - doi : 10.1145/1824801.1824802 .
F. Jaeger, DL Vertigan, DJA Welsh. O výpočetní složitosti Jonesových a Tutteových polynomů // Mathematical Proceedings of the Cambridge Philosophical Society . - 1990. - T. 108 . — s. 35–53 . - doi : 10.1017/S0305004100068936 .
Mark Jerrum, Alistair Sinclair. Algoritmy aproximace polynomiálního času pro model Ising // SIAM Journal on Computing . - 1993. - T. 22 , no. 5 . — S. 1087–1116 . - doi : 10.1137/0222066 .
Michael Korn, Igor Pak. Kombinatorická ohodnocení Tutteho polynomu . — 2003.
Michael Korn, Igor Pak. Obklady obdélníků s T-tetromino // Teoretická informatika . - 2004. - T. 319 , č. 1–3 . — S. 3–27 . - doi : 10.1016/j.tcs.2004.02.023 .
Michel Las Vergnas. Konvexita v orientovaných matroidech // 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. O vyhodnocení na (3, 3) Tutteho polynomu grafu // 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 (Francie) . - Univerzita Josepha Fouriera , 1977. - (Ph.D. práce).
David J. Pearce, Gary Haggard, Gordon Royle. Heuristika hranového výběru pro výpočet Tutteových polynomů // Chicago Journal of Theoretical Computer Science. - 2010. - S. Článek 6, 14 .
Kyoko Sekine, Hiroshi Imai, Seiichiro Tani. Algoritmy a výpočty (Cairns, 1995). - Springer , 1995. - T. 1004. - S. 224-233. — ( Poznámky k přednáškám z informatiky ). - doi : 10.1007/BFb0015427 .
Alan D. Sokal. Průzkumy v kombinatorice / 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 . teorie grafů . - Cambridge University Press , 2001. - ISBN 978-0521794893 .
WT Tutte. Graf-polynomy // Pokroky v aplikované matematice . - 2004. - T. 32 , no. 1–2 . — S. 5–9 . - doi : 10.1016/S0196-8858(03)00041-1 .
DL Vertigan, DJA Welsh. Výpočetní složitost Tutteovy roviny: Bipartitní případ // Kombinatorika, pravděpodobnost a výpočetní technika . - 1992. - svazek 1 , vydání. 2 . — S. 181–187 . - doi : 10.1017/S0963548300000195 .
Dirk Vertigan. Výpočetní složitost Tutteových invariantů pro planární grafy // SIAM Journal on Computing . - 2005. - T. 35 , no. 3 . — S. 690–712 . - doi : 10.1137/S0097539704446797 .
DJA velština. teorie matroidů . - Academic Press , 1976. - ISBN 012744050X .
Dominic Welsh. Složitost: Uzly, barvy a počítání. - Cambridge University Press , 1993. - (London Mathematical Society Lecture Note Series). — ISBN 978-0521457408 .
Dominic Welsh. Tutteův polynom . — Náhodné struktury a algoritmy. - 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ův model a Tutteův polynom // Journal of Mathematical Physics . - 2000. - T. 41 , no. 3 . - doi : 10.1063/1.533181 .
Herbert S. Wilf. Algoritmy a složitost . - Prentice Hall , 1986. - ISBN 0-13-021973-8 .

Odkazy

Hazewinkel, Michiel, ed. (2001), Tutteův polynom , Encyklopedie matematiky , Springer , ISBN 978-1-55608-010-4
Weisstein, Eric W. Tutte polynom (anglicky) na webových stránkách Wolfram MathWorld .
PlanetMath Chromatický polynom
Steven R. Pagano: Matroidy a podepsané grafy
Sandra Kingan: Teorie matroidů . Spousta odkazů.
Kód pro výpočet Tutteových, chromatických a průtokových polynomů Gary Haggard, David J. Pearce a Gordon Royle: [1] (nedostupný odkaz)