Tutteův polynom - Tutte polynomial

The Tutteův polynom, také nazývaný dichroman nebo Tutte – Whitneyův polynom, je polynom grafu. Je to polynomiální ve dvou proměnných, které hrají důležitou roli v teorie grafů. Je definován pro všechny neorientovaný graf a obsahuje informace o tom, jak je graf propojen. Označuje to .
Důležitost tohoto polynomu vyplývá z informací, o kterých obsahuje . Ačkoli původně studoval v algebraická teorie grafů jako zobecnění počítání problémů souvisejících s zbarvení grafu a nikde nulový tok, obsahuje několik slavných dalších specializací z jiných věd, jako je Jonesův polynom z teorie uzlů a funkce oddílů z Pottsův model z statistická fyzika. Je také zdrojem několika centrálních výpočetní problémy v teoretická informatika.
Polynom Tutte má několik ekvivalentních definic. Je to ekvivalent Whitneyho hodnostní polynom, Tutte vlastní dichromatický polynom a Fortuin – Kasteleyn model náhodného klastru pod jednoduchými transformacemi. Je to v zásadě a generující funkce pro počet sad hran dané velikosti a připojených komponent s okamžitým zobecněním na matroidy. Je také nejobecnější graf neměnný které lze definovat a delece – opakování kontrakce. Několik učebnic o teorii grafů a teorii matroidů jí věnuje celé kapitoly.[1][2][3]
Definice
Definice. Pro neorientovaný graf lze definovat Tutteův polynom tak jako
kde označuje počet připojené komponenty grafu . Z této definice je zřejmé, že je dobře definovaný a polynom v a .
Stejnou definici lze uvést pomocí mírně odlišné notace tím, že necháme označit hodnost grafu . Pak Whitney hodnost generující funkce je definován jako
Při jednoduché změně proměnných jsou tyto dvě funkce ekvivalentní:
Tutte's dichromatický polynom je výsledkem další jednoduché transformace:
Tutteho původní definice je ekvivalentní, ale méně snadné Pro připojené jsme si stanovili
kde označuje počet klenout se nad stromy z vnitřní činnost a vnější činnost .
Třetí definice používá a delece – opakování kontrakce. The kontrakce hran grafu je graf získaný sloučením vrcholů a a odstranění okraje . Píšeme pro graf, kde je hrana je pouze odstraněn. Potom je polynom Tutte definován relací opakování
-li není ani smyčka ani a most, se základním pouzdrem
-li obsahuje mosty a smyčky a žádné další hrany. Zvláště, -li neobsahuje žádné hrany.
The model náhodného klastru ze statistické mechaniky kvůli Fortuin & Kasteleyn (1972) poskytuje ještě další ekvivalentní definici.[4] Součet oddílů
je ekvivalentní k pod transformací[5]
Vlastnosti
Tutteovy polynomické faktory do spojených komponent. Li je spojení disjunktních grafů a pak
Li je rovinný a označuje jeho duální graf pak
Chromatický polynom rovinného grafu je zejména tokový polynom jeho duálu. Tutte označuje takové funkce jako V-funkce.[6]
Příklady
Izomorfní grafy mají stejný Tutteův polynom, ale obrácení není pravdivé. Například polynom Tutte každého stromu hran je .
Polynomy s tutusy jsou často uvedeny v tabulkové formě uvedením koeficientů z v řadě a sloupec . Například Tutteův polynom z Petersenův graf,
je uveden v následující tabulce.
0 | 36 | 84 | 75 | 35 | 9 | 1 |
36 | 168 | 171 | 65 | 10 | ||
120 | 240 | 105 | 15 | |||
180 | 170 | 30 | ||||
170 | 70 | |||||
114 | 12 | |||||
56 | ||||||
21 | ||||||
6 | ||||||
1 |
Jiným příkladem je polynom Tutte osmistěnového grafu
Dějiny
W. T. Tutte Zájem o vzorec vypuštění – kontrakce začal v jeho vysokoškolských dnech v Trinity College, Cambridge, původně motivováno perfektní obdélníky a klenout se nad stromy. Ve svém výzkumu často použil vzorec a „přemýšlel, jestli existují další zajímavé věci funkce grafů, invariantní za izomorfismu, s podobnými vzorci rekurze. “[6] R. M. Foster již poznamenal, že chromatický polynom je jedna taková funkce a Tutte začala objevovat více. Jeho původní terminologie pro grafové invarianty, které splňují rekurzi delece-kontrakce, byla W-funkce, a V-funkce pokud je multiplikativní přes komponenty. Tutte píše: „Hraju si s mým W-funkce Získal jsem dva proměnné polynomy, ze kterých lze získat chromatický polynom nebo tokový polynom nastavením jedné z proměnných na nulu a úpravou znaménka. “[6] Tutte tuto funkci nazvala dichroman, jak to viděl jako zobecnění chromatického polynomu na dvě proměnné, ale obvykle se označuje jako Tutteův polynom. Podle slov Tutté: „To může být nespravedlivé Hassler Whitney kdo znal a používal analogické koeficienty, aniž by se obtěžoval je umisťovat na dvě proměnné. “ (Existuje „pozoruhodný zmatek“[7] o podmínkách dichroman a dichromatický polynom, představený Tutte v různých příspěvcích a který se liší jen nepatrně.) Zobecnění Tutteova polynomu na matroidy poprvé publikoval Crapo, ačkoli se to již objevuje v Tutteho práci.[8]
Nezávisle na práci v algebraická teorie grafů, Potts začal studovat funkce oddílu některých modelů v statistická mechanika v roce 1952. Práce Fortuina a Kasteleyna[9] na model náhodného klastru, zobecnění Pottsův model, poskytl sjednocující výraz, který ukázal vztah k polynomu Tutte.[8]
Specializace
V různých bodech a liniích - rovina, Tutteův polynom hodnotí veličiny, které byly samostatně studovány v různých oblastech matematiky a fyziky. Část přitažlivosti Tutteova polynomu pochází ze sjednocujícího rámce, který poskytuje pro analýzu těchto veličin.
Chromatický polynom

Na , Tutteův polynom se specializuje na chromatický polynom,
kde označuje počet připojených komponent G.
Pro celé číslo λ je hodnota chromatického polynomu se rovná počtu vrcholová barviva z G pomocí sady barev λ. Je jasné že nezávisí na sadě barev. Méně jasné je, že se jedná o vyhodnocení u λ polynomu s celočíselnými koeficienty. Abychom to viděli, pozorujeme:
- Li G má n pak vrcholy a žádné hrany .
- Li G obsahuje smyčku (jeden okraj spojující vrchol k sobě), poté .
- Li E je tedy hrana, která není smyčkou
Tři výše uvedené podmínky nám umožňují vypočítat , aplikací sekvence okrajových delecí a kontrakcí; ale neposkytují žádnou záruku, že odlišná sekvence delecí a kontrakcí povede ke stejné hodnotě. Záruka vychází ze skutečnosti, že něco počítá, nezávisle na opakování. Zejména,
udává počet acyklických orientací.
Jonesův polynom

Podél hyperboly , Tutteův polynom rovinného grafu se specializuje na Jonesův polynom přidruženého střídavý uzel.
Jednotlivé body
(2,1)
počítá počet lesy, tj. počet acyklických podmnožin hran.
(1,1)
počítá počet překlenujících lesů (okrajové podmnožiny bez cyklů a stejný počet připojených komponent jako G). Pokud je graf připojen, spočítá počet koster.
(1,2)
počítá počet překlenujících podgrafů (podmnožiny hran se stejným počtem připojených komponent jako G).
(2,0)
počítá počet acyklické orientace z G.[10]
(0,2)
počítá počet silně spojené orientace z G.[11]
(2,2)
je číslo kde je počet okrajů grafu G.
(0,−2)
Li G je tedy 4 pravidelný graf
počítá počet Euleriánské orientace z G. Tady je počet připojených komponent G.[10]
(3,3)
Li G je m × n mřížkový graf, pak spočítá počet způsobů, jak obkládat obdélník o šířce 4m a výška 4n s T-tetrominoes.[12][13]
Li G je rovinný graf, pak se rovná součtu nad váženými Eulerianskými orientacemi v a mediální graf z G, kde váha orientace je 2 k počtu sedlových vrcholů orientace (tj. počet vrcholů s dopadajícími hranami cyklicky seřazených „dovnitř, ven, dovnitř“).[14]
Potts a Ising modely

Definujte hyperbolu v xy- letadlo:
polynom Tutte se specializuje na funkci oddílu, z Isingův model studoval v statistická fyzika. Konkrétně podél hyperboly dva jsou příbuzné rovnicí:[15]
Zejména,
pro všechny komplexní α.
Obecněji, pokud pro jakékoli kladné celé číslo q, definujeme hyperbolu:
potom se polynom Tutte specializuje na funkci rozdělení v q-Stát Pottsův model. Různé fyzické veličiny analyzované v rámci Pottsova modelu se překládají do konkrétních částí .
Pottsův model | Tutteův polynom |
---|---|
Feromagnetické | Pozitivní odvětví |
Antiferromagnetic | Negativní větev s |
Vysoká teplota | Asymptota z na |
Nízkoteplotní feromagnetický | Pozitivní odvětví asymptotické na |
Antiferomagnetická s nulovou teplotou | Graf q-zbarvení, tj., |
Tok polynomu

Na , Tutteův polynom se specializuje na tokový polynom studovaný v kombinatorice. Pro připojený a neorientovaný graf G a celé číslo k, nikde nula k-flow je přiřazení hodnot „flow“ k okrajům libovolné orientace G tak, že celkový tok vstupující a opouštějící každý vrchol je shodný modulo k. Tok polynomu označuje počet nikde nula k-proudí. Tato hodnota úzce souvisí s chromatickým polynomem, ve skutečnosti, pokud G je rovinný graf, chromatický polynom z G je ekvivalentní s polynomem toku jeho duální graf V tom smyslu, že
Věta (Tutte).
Spojení s polynomem Tutte je dáno vztahem:
Spolehlivostní polynom

Na , Tutteův polynom se specializuje na polynomial spolehlivosti všech terminálů studovaný v teorii sítí. Pro připojený graf G odstranit každou hranu s pravděpodobností p; to modeluje síť, která podléhá náhodným výpadkům hran. Pak je polynom spolehlivosti funkcí , polynom v p, což dává pravděpodobnost, že každá dvojice vrcholů G zůstává spojen i po selhání hran. Spojení s Tutteovým polynomem je dáno vztahem
Dichromatický polynom
Tutte také definoval užší zobecnění 2 proměnných chromatického polynomu, dichromatický polynom grafu. Tohle je
kde je počet připojené komponenty překlenovacího podgrafu (PROTI,A). To souvisí s conomk-nullity polynomial podle
Dichromatický polynom nezobecňuje na matroidy, protože k(A) není vlastnost matroid: různé grafy se stejným matroidem mohou mít různý počet připojených komponent.
Související polynomy
Martinův polynom
Martinův polynom orientovaného 4 pravidelného grafu definoval Pierre Martin v roce 1977.[17] Ukázal, že pokud G je rovinný graf a je jeho řízený mediální graf, pak
Algoritmy
Vypuštění - kontrakce

Opakování delece-kontrakce pro Tutteův polynom,
okamžitě získá rekurzivní algoritmus pro jeho výpočet: vyberte libovolnou takovou hranu E a opakovaně aplikujte vzorec, dokud nejsou všechny hrany smyčkami nebo můstky; výsledné základní případy ve spodní části hodnocení lze snadno vypočítat.
V rámci polynomiálního faktoru doba provozu t tohoto algoritmu lze vyjádřit jako počet vrcholů n a počet hran m grafu,
relace opakování, která se mění jako Fibonacciho čísla s řešením[18]
Analýza může být vylepšena v rámci polynomiálního faktoru čísla z klenout se nad stromy vstupního grafu.[19] Pro řídké grafy s tato doba běhu je . Pro pravidelné grafy stupně k, počet koster může být omezen
kde
takže algoritmus delece – kontrakce běží uvnitř polynomiálního faktoru této vazby. Například:[20]
V praxi, izomorfismus grafu testování se používá, aby se zabránilo některým rekurzivním voláním. Tento přístup funguje dobře pro grafy, které jsou poměrně řídké a vykazují mnoho symetrií; výkonnost algoritmu závisí na heuristice použité k výběru okraje E.[19][21][22]
Gaussova eliminace
V některých omezených případech lze Tutteův polynom vypočítat v polynomiálním čase, protože Gaussova eliminace efektivně počítá maticové operace určující a Pfaffian. Tyto algoritmy jsou samy o sobě důležité výsledky algebraická teorie grafů a statistická mechanika.
rovná se číslo z klenout se nad stromy připojeného grafu. To je vypočítatelné v polynomiálním čase jako určující maximální hlavní submatice Laplaciánská matice z G, časný výsledek v algebraické teorii grafů známý jako Kirchhoffova věta Matrix – Tree. Stejně tak rozměr prostoru pro jízdní kolo na lze vypočítat v polynomiálním čase Gaussovou eliminací.
U rovinných grafů je funkce rozdělení modelu Ising, tj. Tutteův polynom v hyperbole , lze vyjádřit jako Pfaffian a efektivně vypočítat pomocí Algoritmus FKT. Tuto myšlenku vyvinul Rybář, Kasteleyn, a Temperley vypočítat počet dimer kryty rovinných mřížový model.
Markovský řetězec Monte Carlo
Používat Markovský řetězec Monte Carlo Metoda může být Tutteův polynom libovolně dobře aproximován podél kladné větve , ekvivalentně, funkce rozdělení feromagnetického Isingova modelu. To využívá úzké spojení mezi Isingovým modelem a problémem počítání párování v grafu. Myšlenka tohoto oslavovaného výsledku Jerruma a Sinclaira[23] je zřídit a Markovův řetězec jejichž stavy jsou shody vstupního grafu. Přechody jsou definovány náhodným výběrem hran a odpovídajícím způsobem upravením shody. Výsledný Markovův řetězec se rychle mísí a vede k „dostatečně náhodným“ shodám, které lze použít k obnovení funkce oddílu pomocí náhodného vzorkování. Výsledný algoritmus je a plně randomizované aproximační schéma v polynomiálním čase (fpras).
Výpočetní složitost
S Tutteovým polynomem je spojeno několik výpočetních problémů. Nejpřímější je
- Vstup: Graf
- Výstup: Koeficienty
Výstup umožňuje zejména vyhodnocení což odpovídá počítání počtu 3 barev G. Tato druhá otázka zní # P-kompletní, i když jsou omezeny na rodinu rovinné grafy, takže problém výpočtu koeficientů Tutteova polynomu pro daný graf je # P-tvrdé dokonce i pro rovinné grafy.
Mnohem větší pozornost byla věnována rodině problémů zvaných Tutte definované pro každý komplexní pár :
- Vstup: Graf
- Výstup: Hodnota
Tvrdost těchto problémů se mění se souřadnicemi .
Přesný výpočet

Pokud obojí X a y jsou nezáporná celá čísla, problém patří #P. U obecných celočíselných párů obsahuje Tutteův polynom záporné členy, které staví problém do třídy složitosti GapP uzavření #P odečteno. Přizpůsobit racionální souřadnice , lze definovat racionální analog #P.[24]
Výpočetní složitost přesného výpočtu spadá do jedné ze dvou tříd pro jakoukoli . Problém je # P-těžký, pokud leží na hyperbole nebo je jedním z bodů
v jakých případech je vypočítatelný v polynomiálním čase.[25] Pokud je problém omezen na třídu rovinných grafů, body na hyperbole stát se také vypočítatelným v polynomiálním čase. Všechny ostatní body zůstávají # P-tvrdé, dokonce i pro bipartitní planární grafy.[26] Ve své práci o dichotomii pro planární grafy Vertigan tvrdí (ve svém závěru), že stejný výsledek platí, když je dále omezen na grafy se stupněm vrcholů nejvýše třemi, kromě bodu , což se počítá nikde nula Z3-toky a je vypočítatelný v polynomiálním čase.[27]
Tyto výsledky obsahují několik pozoruhodných zvláštních případů. Například problém výpočtu funkce oddílu modelu Ising je obecně # P-hard, přestože slavné algoritmy Onsagera a Fishera to řeší pro rovinné mřížky. Jonesův polynom je také těžko vypočítatelný. Nakonec je výpočet počtu čtyřbarevnosti planárního grafu # P-kompletní, i když rozhodovací problém je triviální čtyřbarevná věta. Naproti tomu je snadné vidět, že počítání počtu tříbarev pro planární grafy je # P-úplné, protože je známo, že rozhodovací problém je NP-úplný prostřednictvím šetrné snížení.
Přiblížení
Otázka, které body připouštějí dobrý aproximační algoritmus, byla velmi dobře prostudována. Kromě bodů, které lze vypočítat přesně v polynomiálním čase, je známý jediný algoritmus aproximace je FPRAS od Jerruma a Sinclaira, který pracuje pro body v hyperbole „Ising“ pro y > 0. Pokud jsou vstupní grafy omezeny na husté instance se stupněm , existuje FPRAS, pokud X ≥ 1, y ≥ 1.[28]
I když situace není tak dobře pochopena jako pro přesný výpočet, je známo, že velké oblasti roviny je obtížné aproximovat.[24]
Viz také
- Bollobás – Riordanův polynom
- A Tutte-Grothendieck invariantní je jakékoli vyhodnocení Tutteova polynomu
Poznámky
- ^ Bollobás 1998, kapitola 10.
- ^ Biggs 1993, kapitola 13.
- ^ Godsil a Royle 2004, kap. 15.
- ^ Sokal 2005.
- ^ Sokal 2005 ekv. (2,26).
- ^ A b C Tutte 2004.
- ^ Velština.
- ^ A b Farr 2007.
- ^ Fortuin & Kasteleyn 1972.
- ^ A b Velština 1999.
- ^ Las Vergnas 1980.
- ^ Korn & Pak 2004.
- ^ Vidět Korn & Pak 2003 pro kombinatorické interpretace mnoha dalších bodů.
- ^ Las Vergnas 1988.
- ^ Velština 1993, str. 62.
- ^ Welsh & Merino 2000.
- ^ Martin 1977.
- ^ Wilf 1986, str. 46.
- ^ A b Sekine, Imai & Tani 1995.
- ^ Chung & Yau 1999, Následující Björklund a kol. 2008.
- ^ Haggard, Pearce & Royle 2010.
- ^ Pearce, Haggard & Royle 2010.
- ^ Jerrum & Sinclair 1993.
- ^ A b Goldberg & Jerrum 2008.
- ^ Jaeger, Vertigan a Welsh 1990.
- ^ Vertigan & Welsh 1992.
- ^ Vertigan 2005.
- ^ Pro případ X ≥ 1 a y = 1, viz Annan 1994. Pro případ X ≥ 1 a y > 1, viz Alon, Frieze & Welsh 1995.
Reference
- Alon, N .; Frieze, A .; Velština, D. J. A. (1995), „Polynomiální časově randomizovaná aproximační schémata pro Tutte-Gröthendieckovy invarianty: Hustý případ“, Náhodné struktury a algoritmy, 6 (4): 459–478, doi:10,1002 / rsa.3240060409.
- Annan, J. D. (1994), „Randomizovaný aproximační algoritmus pro počítání počtu lesů v hustých grafech“, Kombinatorika, pravděpodobnost a výpočet, 3 (3): 273–283, doi:10.1017 / S0963548300001188.
- Biggs, Norman (1993), Algebraická teorie grafů (2. vyd.), Cambridge University Press, ISBN 0-521-45897-8.
- Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), „Computing the Tutte polynomial in vertex-exponential time“, Proc. 47. ročníku IEEE Symposium on Foundations of Computer Science (FOCS 2008), str. 677–686, arXiv:0711.2585, doi:10.1109 / FOCS.2008.40, ISBN 978-0-7695-3436-7.
- Bollobás, Béla (1998), Teorie moderních grafů, Springer, ISBN 978-0-387-98491-9.
- Chung, Fan; Yau, S.-T. (1999), „Krytiny, tepelná jádra a kostry“, Electronic Journal of Combinatorics, 6: R12, PAN 1667452.
- Crapo, Henry H. (1969), „The Tutte polynomial“, Aequationes Mathematicae, 3 (3): 211–229, doi:10.1007 / bf01817442.
- Farr, Graham E. (2007), „Tutte-Whitney polynomials: some history and generalizations“, v Grimmett, Geoffrey; McDiarmid, Colin (eds.), Kombinatorika, složitost a náhoda. Pocta Dominic Welshovi, Oxford Lecture Series in Mathematics and its Applications, 34, Oxford University Press, s. 28–52, ISBN 978-0-19-857127-8, Zbl 1124.05020.
- Fortuin, Cees M .; Kasteleyn, Pieter W. (1972), „K modelu náhodného shluku: I. Úvod a vztah k jiným modelům“, Physica, Elsevier, 57 (4): 536–564, Bibcode:1972Phy .... 57..536F, doi:10.1016/0031-8914(72)90045-6, ISSN 0031-8914.
- Godsil, Chris; Royle, Gordone (2004), Algebraická teorie grafů, Springer, ISBN 978-0-387-95220-8.
- Goldberg, Leslie Ann; Jerrum, Marku (2008), „Nepřibližitelnost Tuttova polynomu“, Informace a výpočet, 206 (7): 908–929, arXiv:cs / 0605140, doi:10.1016 / j.ic.2008.04.003.
- Haggard, Gary; Pearce, David J .; Royle, Gordon (2010), „Computing Tutte polynomials“, Transakce ACM na matematickém softwaru, 37 (3): Čl. 24, 17, doi:10.1145/1824801.1824802, PAN 2738228.
- Jaeger, F .; Vertigan, D. L .; Velština, D. J. A. (1990), „O výpočetní složitosti Jonesových a Tuttových polynomů“, Mathematical Proceedings of the Cambridge Philosophical Society, 108 (1): 35–53, Bibcode:1990MPCPS.108 ... 35J, doi:10.1017 / S0305004100068936.
- Jerrum, Marku; Sinclair, Alistair (1993), "Algoritmy aproximace v polynomiálním čase pro Isingův model" (PDF), SIAM Journal on Computing, 22 (5): 1087–1116, doi:10.1137/0222066.
- Korn, Michael; Pak, Igor (2003), Kombinatorické vyhodnocení Tutteova polynomu (PDF) (předtisk).
- Korn, Michael; Pak, Igor (2004), „Obklady obdélníků s T-tetrominy“, Teoretická informatika, 319 (1–3): 3–27, doi:10.1016 / j.tcs.2004.02.023.
- Las Vergnas, Michel (1980), "Konvexita v orientovaných matroidech", Journal of Combinatorial Theory, Řada B, 29 (2): 231–243, doi:10.1016/0095-8956(80)90082-9, ISSN 0095-8956, PAN 0586435.
- Las Vergnas, Michel (1988), „O vyhodnocení (3, 3) Tutteova polynomu grafu“, Journal of Combinatorial Theory, Řada B, 45 (3): 367–372, doi:10.1016/0095-8956(88)90079-2, ISSN 0095-8956.
- Martin, Pierre (1977), Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck [Euleriánské výčty v multigrafech a Tutte-Grothendieckových invariantech] (Ph.D. práce) (ve francouzštině), Univerzita Josepha Fouriera.
- Pearce, David J .; Haggard, Gary; Royle, Gordon (2010), "Heuristika výběru hran pro výpočet polynomů Tutte" (PDF), Chicago Journal of Theoretical Computer Science: Články 6, 14, PAN 2659710.
- Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), „Výpočet Tutteova polynomu grafu střední velikosti“, Algoritmy a výpočty (Cairns, 1995), Přednášky z informatiky, 1004, Springer, str. 224–233, doi:10.1007 / BFb0015427, PAN 1400247.
- Sokal, Alan D. (2005), „Multivariační Tutteův polynom (alias Pottsův model) pro grafy a matroidy“, Webb, Bridget S. (ed.), Průzkumy v kombinatorice, Série přednášek London Mathematical Society, 327, Cambridge University Press, str. 173–226, arXiv:matematika / 0503607, doi:10.1017 / CBO9780511734885.009.
- Tutte, W. T. (2001), Teorie grafů, Cambridge University Press, ISBN 978-0521794893.
- Tutte, W. T. (2004), „Graph-polynomials“, Pokroky v aplikované matematice, 32 (1–2): 5–9, doi:10.1016 / S0196-8858 (03) 00041-1.
- Vertigan, D. L .; Velština, D. J. A. (1992), „Výpočetní složitost roviny Tutte: bipartitní případ“, Kombinatorika, pravděpodobnost a výpočet, 1 (2): 181–187, doi:10.1017 / S0963548300000195.
- Vertigan, Dirk (2005), „Výpočetní složitost Tutteových invariants pro rovinné grafy“, SIAM Journal on Computing, 35 (3): 690–712, doi:10.1137 / S0097539704446797.
- Velština, D. J. A. (1976), Teorie matroidů, Akademický tisk, ISBN 012744050X.
- Velšština, Dominiku (1993), Složitost: Uzly, barviva a počítání, Série přednášek London Mathematical Society, Cambridge University Press, ISBN 978-0521457408.
- Velšština, Dominiku (1999), „The Tutte polynomial“, Náhodné struktury a algoritmy, Wiley, 15 (3–4): 210–228, doi:10.1002 / (SICI) 1098-2418 (199910/12) 15: 3/4 <210 :: AID-RSA2> 3.0.CO; 2-R, ISSN 1042-9832.
- Velština, D. J. A.; Merino, C. (2000), „The Potts model and the Tutte polynomial“, Journal of Mathematical Physics, 41 (3): 1127–1152, Bibcode:2000JMP .... 41,1127W, doi:10.1063/1.533181.
- Wilf, Herbert S. (1986), Algoritmy a složitost (PDF), Prentice Hall, ISBN 0-13-021973-8, PAN 0897317.
externí odkazy
- "Tutte polynomial", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
- Weisstein, Eric W. "Tutte polynomial". MathWorld.
- PlanetMath Chromatický polynom
- Steven R. Pagano: Matroidy a podepsané grafy
- Sandra Kingan: Teorie matroidů. Mnoho odkazů.
- Kód pro výpočet Tutte, Chromatic a Flow Polynomials Gary Haggard, David J. Pearce a Gordon Royle: [1]