Tutte-Polynom – Wikipedia

Das Polynom

Das Tutte-Polynom, auch genannt Dichromat oder der Tutte-Whitney-Polynomist ein Graphpolynom. Es ist ein Polynom in zwei Variablen, das in der Graphentheorie eine wichtige Rolle spielt. Sie wird für jedes ungerichtete Diagramm definiert

G{ displaystyle G}

und enthält Informationen darüber, wie das Diagramm verbunden ist. Es wird mit bezeichnet

T.G{ displaystyle T_ {G}}

.

Die Bedeutung dieses Polynoms ergibt sich aus den darin enthaltenen Informationen

G{ displaystyle G}

. Obwohl ursprünglich in der algebraischen Graphentheorie als Verallgemeinerung von Zählproblemen im Zusammenhang mit der Graphfärbung und dem Nirgendwo-Null-Fluss untersucht, enthält sie einige berühmte andere Spezialisierungen aus anderen Wissenschaften wie das Jones-Polynom aus der Knotentheorie und die Partitionsfunktionen des Potts-Modells aus der Statistik Physik. Es ist auch die Quelle mehrerer zentraler Rechenprobleme in der theoretischen Informatik.

Das Tutte-Polynom hat mehrere äquivalente Definitionen. Es ist gleichbedeutend mit Whitneys Rang Polynom, Tuttes eigene dichromatisches Polynom und Fortuin-Kasteleyns zufälliges Cluster-Modell unter einfachen Transformationen. Es ist im Wesentlichen eine Erzeugungsfunktion für die Anzahl der Kantensätze einer bestimmten Größe und der verbundenen Komponenten mit sofortigen Verallgemeinerungen auf Matroide. Es ist auch die allgemeinste Graphinvariante, die durch eine Wiederholung von Löschung und Kontraktion definiert werden kann. Mehrere Lehrbücher über Graphentheorie und Matroidentheorie widmen ihr ganze Kapitel.[1][2][3]

Definitionen[edit]

Definition. Für ein ungerichtetes Diagramm

G=((V.,E.){ displaystyle G = (V, E)}

man kann das definieren Tutte-Polynom wie

wo

k((EIN){ displaystyle k (A)}

bezeichnet die Anzahl der verbundenen Komponenten des Diagramms

((V.,EIN){ displaystyle (V, A)}

. In dieser Definition ist es klar, dass

T.G{ displaystyle T_ {G}}

ist gut definiert und ein Polynom in

x{ displaystyle x}

und

y{ displaystyle y}

.

Dieselbe Definition kann durch leicht unterschiedliche Notation durch Vermieten gegeben werden

r((EIN)=|V.|– –k((EIN){ displaystyle r (A) = | V | -k (A)}

bezeichnen den Rang des Graphen

((V.,EIN){ displaystyle (V, A)}

. Dann ist die Whitney-Rang erzeugende Funktion ist definiert als

Die beiden Funktionen sind bei einer einfachen Änderung von Variablen äquivalent:

Tutte’s dichromatisches Polynom

Q.G{ displaystyle Q_ {G}}

ist das Ergebnis einer weiteren einfachen Transformation:

Tuttes ursprüngliche Definition von

T.G{ displaystyle T_ {G}}

ist gleichwertig, aber weniger leicht zu sagen. Für angeschlossene

G{ displaystyle G}

legen wir fest

wo

tichj{ displaystyle t_ {ij}}

bezeichnet die Anzahl der Spannbäume von interne Aktivität

ich{ displaystyle i}

und externe Aktivität

j{ displaystyle j}

.

Eine dritte Definition verwendet a Wiederholung von Löschung und Kontraktion. Die Kantenkontraktion

G/.uv{ displaystyle G / uv}

des Graphen

G{ displaystyle G}

ist der Graph, der durch Zusammenführen der Eckpunkte erhalten wird

u{ displaystyle u}

und

v{ displaystyle v}

und Entfernen der Kante

uv{ displaystyle uv}

. Wir schreiben

G– –uv{ displaystyle G-uv}

für das Diagramm, wo die Kante

uv{ displaystyle uv}

wird lediglich entfernt. Dann wird das Tutte-Polynom durch die Wiederholungsrelation definiert

wenn

e{ displaystyle e}

ist weder eine Schleife noch eine Brücke mit Basisgehäuse

wenn

G{ displaystyle G}

enthält

ich{ displaystyle i}

Brücken und

j{ displaystyle j}

Schleifen und keine anderen Kanten. Insbesondere,

T.G=1{ displaystyle T_ {G} = 1}

wenn

G{ displaystyle G}

enthält keine Kanten.

Das zufälliges Cluster-Modell aus der statistischen Mechanik aufgrund von Fortuin & Kasteleyn (1972) liefert noch eine weitere äquivalente Definition.[4] Die Partitionssumme

ist äquivalent zu

T.G{ displaystyle T_ {G}}

unter der Transformation[5]

Eigenschaften[edit]

Das Tutte-Polynom zerlegt in verbundene Komponenten. Wenn

G{ displaystyle G}

ist die Vereinigung disjunkter Graphen

H.{ displaystyle H}

und

H.{ displaystyle H ‘}

dann

Wenn

G{ displaystyle G}

ist planar und

G{ displaystyle G ^ {*}}

bezeichnet dann seinen dualen Graphen

Insbesondere ist das chromatische Polynom eines planaren Graphen das Strömungspolynom seines Dualen. Tutte bezieht sich auf solche Funktionen wie V-Funktionen.[6]

Beispiele[edit]

Isomorphe Graphen haben das gleiche Tutte-Polynom, aber das Gegenteil ist nicht der Fall. Zum Beispiel das Tutte-Polynom jedes Baumes auf

m{ displaystyle m}

Kanten ist

xm{ displaystyle x ^ {m}}

.

Tutte-Polynome werden häufig in tabellarischer Form angegeben, indem die Koeffizienten aufgelistet werden

tichj{ displaystyle t_ {ij}}

von

xichyj{ displaystyle x ^ {i} y ^ {j}}

in Reihe

ich{ displaystyle i}

und Spalte

j{ displaystyle j}

. Zum Beispiel das Tutte-Polynom des Petersen-Graphen,

wird durch die folgende Tabelle angegeben.

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

Ein anderes Beispiel ist das Tutte-Polynom des Oktaedergraphen gegeben durch

Geschichte[edit]

WT Tuttes Interesse an der Lösch-Kontraktions-Formel begann in seiner Studienzeit am Trinity College in Cambridge, ursprünglich motiviert durch perfekte Rechtecke und überspannende Bäume. Er wandte die Formel häufig in seiner Forschung an und fragte sich, ob es andere interessante Funktionen von Graphen gibt, die unter Isomorphismus invariant sind und ähnliche Rekursionsformeln aufweisen.[6]RM Foster hatte bereits beobachtet, dass das chromatische Polynom eine solche Funktion ist, und Tutte begann, mehr zu entdecken. Seine ursprüngliche Terminologie für Graphinvarianten, die die Lösch-Kontraktions-Rekursion erfüllen, war W-Funktion, und V-Funktion wenn multiplikativ über Komponenten. Tutte schreibt: „Mit meinem spielen W-Funktionen Ich habe ein Polynom mit zwei Variablen erhalten, aus dem entweder das chromatische Polynom oder das Flusspolynom erhalten werden kann, indem eine der Variablen gleich Null gesetzt und die Vorzeichen angepasst werden. “[6] Tutte nannte diese Funktion die Dichromat, wie er es als Verallgemeinerung des chromatischen Polynoms auf zwei Variablen ansah, wird es aber gewöhnlich als Tutte-Polynom bezeichnet. In Tuttes Worten: “Dies mag Hassler Whitney gegenüber unfair sein, der analoge Koeffizienten kannte und verwendete, ohne sich die Mühe zu machen, sie an zwei Variablen zu befestigen.” (Es gibt “bemerkenswerte Verwirrung”[7] über die Bedingungen Dichromat und dichromatisches PolynomDie Verallgemeinerung des Tutte-Polynoms auf Matroiden wurde erstmals von Crapo veröffentlicht, obwohl sie bereits in Tuttes These erscheint.[8]

Unabhängig von der Arbeit in der algebraischen Graphentheorie begann Potts 1952 mit der Untersuchung der Partitionsfunktion bestimmter Modelle in der statistischen Mechanik. Die Arbeit von Fortuin und Kasteleyn[9] Auf dem Zufallsclustermodell lieferte eine Verallgemeinerung des Potts-Modells einen einheitlichen Ausdruck, der die Beziehung zum Tutte-Polynom zeigte.[8]

Spezialisierungen[edit]

An verschiedenen Stellen und Linien der

((x,y){ displaystyle (x, y)}

-Ebene, das Tutte-Polynom bewertet Größen, die in verschiedenen Bereichen der Mathematik und Physik eigenständig untersucht wurden. Ein Teil der Attraktivität des Tutte-Polynoms beruht auf dem einheitlichen Rahmen für die Analyse dieser Größen.

Chromatisches Polynom[edit]

Das in der Tutte-Ebene gezeichnete chromatische Polynom

Beim

y=0{ displaystyle y = 0}

ist das Tutte-Polynom auf das chromatische Polynom spezialisiert,

wo

k((G){ displaystyle k (G)}

bezeichnet die Anzahl der angeschlossenen Komponenten von G.

Für die ganze Zahl λ der Wert des chromatischen Polynoms

χG((λ){ displaystyle chi _ {G} ( lambda)}

entspricht der Anzahl der Scheitelpunktfärbungen von G unter Verwendung eines Satzes von λ-Farben. Es ist klar, dass

χG((λ){ displaystyle chi _ {G} ( lambda)}

hängt nicht von der Farbpalette ab. Weniger klar ist, dass es sich um die Auswertung eines Polynoms mit ganzzahligen Koeffizienten bei λ handelt. Um dies zu sehen, beobachten wir:

  1. Wenn G hat n Eckpunkte und keine Kanten also
  2. Wenn G enthält dann eine Schleife (eine einzelne Kante, die einen Scheitelpunkt mit sich selbst verbindet)
  3. Wenn e ist also eine Kante, die keine Schleife ist

Die drei oben genannten Bedingungen ermöglichen uns die Berechnung

χG((λ){ displaystyle chi _ {G} ( lambda)}

durch Anwenden einer Folge von Kantenlöschungen und -kontraktionen; Sie geben jedoch keine Garantie dafür, dass eine unterschiedliche Abfolge von Löschungen und Kontraktionen zum gleichen Wert führt. Die Garantie ergibt sich aus der Tatsache, dass

χG((λ){ displaystyle chi _ {G} ( lambda)}

zählt etwas, unabhängig von der Wiederholung. Speziell,

gibt die Anzahl der azyklischen Orientierungen an.

Jones-Polynom[edit]

Das in der Tutte-Ebene gezeichnete Jones-Polynom

Entlang der Hyperbel

xy=1{ displaystyle xy = 1}

Das Tutte-Polynom eines planaren Graphen ist auf das Jones-Polynom eines zugehörigen alternierenden Knotens spezialisiert.

Einzelne Punkte[edit]

(2,1)[edit]

T.G((2,1){ displaystyle T_ {G} (2,1)}

zählt die Anzahl der Wälder, dh die Anzahl der Teilmengen der azyklischen Kanten.

(1,1)[edit]

T.G((1,1){ displaystyle T_ {G} (1,1)}

zählt die Anzahl der übergreifenden Gesamtstrukturen (Randteilmengen ohne Zyklen und die gleiche Anzahl verbundener Komponenten wie G). Wenn der Graph verbunden ist,

T.G((1,1){ displaystyle T_ {G} (1,1)}

zählt die Anzahl der überspannenden Bäume.

(1,2)[edit]

T.G((1,2){ displaystyle T_ {G} (1,2)}

zählt die Anzahl der übergreifenden Untergraphen (Randteilmengen mit der gleichen Anzahl verbundener Komponenten wie) G).

(2,0)[edit]

T.G((2,0){ displaystyle T_ {G} (2,0)}

zählt die Anzahl der azyklischen Orientierungen von G.[10]

(0,2)[edit]

T.G((0,2){ displaystyle T_ {G} (0,2)}

zählt die Anzahl der stark verbundenen Orientierungen von G.[11]

(2,2)[edit]

T.G((2,2){ displaystyle T_ {G} (2,2)}

ist die Nummer

2|E.|{ displaystyle 2 ^ {| E |}}

wo

|E.|{ displaystyle | E |}

ist die Anzahl der Kanten des Diagramms G.

(0, –2)[edit]

Wenn G ist also ein 4-regulärer Graph

zählt die Anzahl der Eulerschen Orientierungen von G. Hier

k((G){ displaystyle k (G)}

ist die Anzahl der verbundenen Komponenten von G.[10]

(3,3)[edit]

Wenn G ist der m × n dann Gittergraph

2T.G((3,3){ displaystyle 2T_ {G} (3,3)}

zählt die Anzahl der Möglichkeiten, ein Rechteck mit der Breite 4 zu kachelnm und Höhe 4n mit T-Tetrominoes.[12][13]

Wenn G ist also ein planarer Graph

2T.G((3,3){ displaystyle 2T_ {G} (3,3)}

entspricht der Summe über gewichteten Eulerschen Orientierungen in einem medialen Graphen von Gwobei das Gewicht einer Ausrichtung 2 zur Anzahl der Sattelscheitelpunkte der Ausrichtung beträgt (dh die Anzahl der Scheitelpunkte mit einfallenden Kanten, die zyklisch “in, out, in out” angeordnet sind).[14]

Potts und Ising Modelle[edit]

Die Partitionsfunktionen für das Ising-Modell und die in der Tutte-Ebene gezeichneten Potts-Modelle mit 3 und 4 Zuständen.

Definieren Sie die Hyperbel in der xy−Ebene:

Das Tutte-Polynom ist auf die Partitionsfunktion spezialisiert.

Z.((),{ displaystyle Z ( cdot),}

des in der statistischen Physik untersuchten Ising-Modells. Insbesondere entlang der Hyperbel

H.2{ displaystyle H_ {2}}

die beiden sind durch die Gleichung verbunden:[15]

Speziell,

für alle komplexen α.

Allgemeiner, wenn für eine positive ganze Zahl qdefinieren wir die Hyperbel:

dann ist das Tutte-Polynom auf die Partitionsfunktion des spezialisiert q-state Potts Modell. Verschiedene physikalische Größen, die im Rahmen des Potts-Modells analysiert wurden, lassen sich auf bestimmte Teile des

H.q{ displaystyle H_ {q}}

.

Strömungspolynom[edit]

Das in der Tutte-Ebene gezeichnete Strömungspolynom

Beim

x=0{ displaystyle x = 0}

Das Tutte-Polynom ist auf das in der Kombinatorik untersuchte Strömungspolynom spezialisiert. Für einen verbundenen und ungerichteten Graphen G und ganze Zahl k, ein Nirgendwo-Null k-flow ist eine Zuweisung von “Flow” -Werten

1,2,,k– –1{ displaystyle 1,2, dots, k-1}

zu den Rändern einer beliebigen Ausrichtung von G so dass der Gesamtfluss, der in jeden Scheitelpunkt eintritt und diesen verlässt, kongruent modulo ist k. Das Strömungspolynom

C.G((k){ displaystyle C_ {G} (k)}

bezeichnet die Zahl von Nirgendwo-Null k-flows. Dieser Wert ist eng mit dem chromatischen Polynom verbunden, wenn G ist ein planarer Graph, das chromatische Polynom von G entspricht dem Strömungspolynom seines Dualgraphen

G{ displaystyle G ^ {*}}

in dem Sinne, dass

Satz (Tutte).

Die Verbindung zum Tutte-Polynom ist gegeben durch:

Zuverlässigkeitspolynom[edit]

Das in der Tutte-Ebene gezeichnete Zuverlässigkeitspolynom

Beim

x=1{ displaystyle x = 1}

Das Tutte-Polynom ist auf das in der Netzwerktheorie untersuchte All-Terminal-Zuverlässigkeitspolynom spezialisiert. Für einen verbundenen Graphen G entferne jede Kante mit Wahrscheinlichkeit p;; Dies modelliert ein Netzwerk, das zufälligen Kantenfehlern ausgesetzt ist. Dann ist das Zuverlässigkeitspolynom eine Funktion

R.G((p){ displaystyle R_ {G} (p)}

, ein Polynom in p, das gibt die Wahrscheinlichkeit, dass jedes Paar von Eckpunkten in G bleibt verbunden, nachdem die Kanten ausgefallen sind. Die Verbindung zum Tutte-Polynom ist gegeben durch

Dichromatisches Polynom[edit]

Tutte definierte auch eine engere 2-Variablen-Verallgemeinerung des chromatischen Polynoms, der dichromatisches Polynom eines Graphen. Das ist

wo

k((EIN){ displaystyle k (A)}

ist die Anzahl der verbundenen Komponenten des übergreifenden Teilgraphen (V.,EIN). Dies hängt mit dem zusammen Korank-Null-Polynom durch

Das dichromatische Polynom verallgemeinert sich nicht auf Matroide, weil k((EIN) ist keine matroid-Eigenschaft: Unterschiedliche Diagramme mit derselben matroid können unterschiedliche Anzahlen verbundener Komponenten aufweisen.

Verwandte Polynome[edit]

Martin-Polynom[edit]

Das Martin-Polynom

mG((x){ displaystyle m _ { vec {G}} (x)}

eines orientierten 4-regulären Graphen

G{ displaystyle { vec {G}}}

wurde 1977 von Pierre Martin definiert.[17] Er zeigte das wenn G ist ein ebener Graph und

Gm{ displaystyle { vec {G}} _ {m}}

ist also sein gerichteter medialer Graph

Algorithmen[edit]

Löschen – Kontraktion[edit]

Der Lösch-Kontraktions-Algorithmus, der auf den Diamantgraphen angewendet wird. Rote Ränder werden im linken Kind gelöscht und im rechten Kind zusammengezogen. Das resultierende Polynom ist die Summe der Monome an den Blättern.

Die Deletions-Kontraktions-Wiederholung für das Tutte-Polynom,

ergibt sofort einen rekursiven Algorithmus für die Berechnung: Wählen Sie eine solche Kante e und wenden Sie die Formel wiederholt an, bis alle Kanten entweder Schleifen oder Brücken sind; Die resultierenden Basisfälle am Ende der Bewertung sind einfach zu berechnen.

Innerhalb eines Polynomfaktors die Laufzeit t dieses Algorithmus kann in Form der Anzahl der Eckpunkte ausgedrückt werden n und die Anzahl der Kanten m des Graphen,

Eine Wiederholungsrelation, die als Fibonacci-Zahlen mit Lösung skaliert[18]

Die Analyse kann innerhalb eines Polynomfaktors der Zahl verbessert werden

τ((G){ displaystyle tau (G)}

von Spannbäumen des Eingabegraphen.[19] Für spärliche Grafiken mit

m=Ö((n){ displaystyle m = O (n)}

Diese Laufzeit ist

Ö((exp((n)){ displaystyle O ( exp (n))}

. Für regelmäßige Gradgraphen kkann die Anzahl der Spannbäume begrenzt werden durch

wo

Der Lösch-Kontraktions-Algorithmus läuft also innerhalb eines Polynomfaktors dieser Grenze. Zum Beispiel:[20]

In der Praxis werden Graphisomorphismustests verwendet, um einige rekursive Aufrufe zu vermeiden. Dieser Ansatz eignet sich gut für Diagramme, die recht spärlich sind und viele Symmetrien aufweisen. Die Leistung des Algorithmus hängt von der Heuristik ab, mit der die Kante ausgewählt wird e.[19][21][22]

Gaußsche Eliminierung[edit]

In einigen eingeschränkten Fällen kann das Tutte-Polynom in Polynomzeit berechnet werden, letztendlich weil die Gaußsche Eliminierung die Matrixoperationsdeterminante und Pfaffian effizient berechnet. Diese Algorithmen sind selbst wichtige Ergebnisse der algebraischen Graphentheorie und der statistischen Mechanik.

T.G((1,1){ displaystyle T_ {G} (1,1)}

entspricht der Zahl

τ((G){ displaystyle tau (G)}

von überspannenden Bäumen eines verbundenen Graphen. Dies ist in der Polynomzeit als Determinante einer maximalen Hauptsubmatrix der Laplace-Matrix von berechenbar G, ein frühes Ergebnis in der algebraischen Graphentheorie, bekannt als Kirchhoffs Matrix-Tree-Theorem. Ebenso ist die Abmessung des Fahrradraums bei

T.G((– –1,– –1){ displaystyle T_ {G} (- 1, -1)}

kann durch Gaußsche Eliminierung in Polynomzeit berechnet werden.

Für planare Graphen die Partitionsfunktion des Ising-Modells, dh das Tutte-Polynom an der Hyperbel

H.2{ displaystyle H_ {2}}

kann als Pfaffian ausgedrückt und über den FKT-Algorithmus effizient berechnet werden. Diese Idee wurde von Fisher, Kasteleyn und Temperley entwickelt, um die Anzahl der Dimerabdeckungen eines planaren Gittermodells zu berechnen.

Markov-Kette Monte Carlo[edit]

Unter Verwendung einer Markov-Ketten-Monte-Carlo-Methode kann das Tutte-Polynom entlang des positiven Zweigs von beliebig gut angenähert werden

H.2{ displaystyle H_ {2}}

äquivalent dazu die Partitionsfunktion des ferromagnetischen Ising-Modells. Dies nutzt die enge Verbindung zwischen dem Ising-Modell und dem Problem des Zählens von Übereinstimmungen in einem Diagramm. Die Idee hinter diesem gefeierten Ergebnis von Jerrum und Sinclair[23] besteht darin, eine Markov-Kette einzurichten, deren Zustände den Übereinstimmungen des Eingabegraphen entsprechen. Die Übergänge werden definiert, indem Kanten zufällig ausgewählt und die Übereinstimmung entsprechend geändert werden. Die resultierende Markov-Kette mischt sich schnell und führt zu „ausreichend zufälligen“ Übereinstimmungen, mit denen die Partitionsfunktion mithilfe von Zufallsstichproben wiederhergestellt werden kann. Der resultierende Algorithmus ist ein vollständig polynomialzeit-randomisiertes Approximationsschema (fpras).

Rechenkomplexität[edit]

Mit dem Tutte-Polynom sind mehrere Rechenprobleme verbunden. Das einfachste ist

Eingabe: Ein Diagramm

Ausgabe: Die Koeffizienten von

Insbesondere ermöglicht die Ausgabe eine Auswertung

T.G((– –2,0){ displaystyle T_ {G} (- 2,0)}

Dies entspricht dem Zählen der Anzahl der 3-Farben von G. Diese letztere Frage ist # P-vollständig, selbst wenn sie auf die Familie der planaren Graphen beschränkt ist, so dass das Problem der Berechnung der Koeffizienten des Tutte-Polynoms für einen gegebenen Graphen selbst für planare Graphen # P-schwer ist.

Der Problemfamilie Tutte wurde viel mehr Aufmerksamkeit geschenkt

((x,y){ displaystyle (x, y)}

definiert für jedes komplexe Paar

((x,y){ displaystyle (x, y)}

::

Eingabe: Ein Diagramm
Ausgabe: Der Wert von

Die Härte dieser Probleme variiert mit den Koordinaten

((x,y){ displaystyle (x, y)}

.

Genaue Berechnung[edit]

Das Tutte-Flugzeug. Jeder Punkt

Wenn beides x und y sind nicht negative ganze Zahlen, das Problem

T.G((x,y){ displaystyle T_ {G} (x, y)}

gehört zu #P. Für allgemeine ganzzahlige Paare enthält das Tutte-Polynom negative Terme, wodurch das Problem in die Komplexitätsklasse GapP, das Schließen von #P, subtrahiert wird. Rationale Koordinaten berücksichtigen

((x,y){ displaystyle (x, y)}

kann man ein rationales Analogon von #P definieren.[24]

Die rechnerische Komplexität des exakten Rechnens

T.G((x,y){ displaystyle T_ {G} (x, y)}

fällt in eine von zwei Klassen für jede

x,yC.{ displaystyle x, y in mathbb {C}}

. Das Problem ist # P-schwer, es sei denn

((x,y){ displaystyle (x, y)}

liegt auf der Hyperbel

H.1{ displaystyle H_ {1}}

oder ist einer der Punkte

In diesen Fällen ist es in Polynomzeit berechenbar.[25] Wenn das Problem auf die Klasse der planaren Graphen beschränkt ist, werden die Punkte auf der Hyperbel angezeigt

H.2{ displaystyle H_ {2}}

werden auch polynomialzeitberechnbar. Alle anderen Punkte bleiben # P-hart, auch für zweigeteilte planare Graphen.[26] In seiner Arbeit über die Dichotomie für planare Graphen behauptet Vertigan (in seiner Schlussfolgerung), dass das gleiche Ergebnis gilt, wenn es weiter auf Graphen mit einem Scheitelpunktgrad von höchstens drei beschränkt wird, abgesehen von dem Punkt

T.G((0,– –2){ displaystyle T_ {G} (0, -2)}

, was nirgendwo Null zählt Z.3-flows und ist in Polynomzeit berechenbar.[27]

Diese Ergebnisse enthalten mehrere bemerkenswerte Sonderfälle. Zum Beispiel ist das Problem der Berechnung der Partitionsfunktion des Ising-Modells im Allgemeinen # P-schwer, obwohl berühmte Algorithmen von Onsager und Fisher es für planare Gitter lösen. Außerdem ist das Jones-Polynom # P-schwer zu berechnen. Schließlich ist die Berechnung der Anzahl der Vierfarben eines planaren Graphen # P-vollständig, obwohl das Entscheidungsproblem nach dem Vierfarbensatz trivial ist. Im Gegensatz dazu ist leicht zu erkennen, dass das Zählen der Anzahl von Dreifarben für planare Graphen # P-vollständig ist, da bekannt ist, dass das Entscheidungsproblem über eine sparsame Reduktion NP-vollständig ist.

Annäherung[edit]

Die Frage, welche Punkte einen guten Approximationsalgorithmus zulassen, wurde sehr gut untersucht. Abgesehen von den Punkten, die genau in Polynomzeit berechnet werden können, ist dies der einzige bekannte Näherungsalgorithmus

T.G((x,y){ displaystyle T_ {G} (x, y)}

ist das FPRAS von Jerrum und Sinclair, das für Punkte auf der Hyperbel „Ising“ arbeitet

H.2{ displaystyle H_ {2}}

zum y > 0. Wenn die Eingabediagramme auf dichte Instanzen mit Grad beschränkt sind

Ω((n){ displaystyle Omega (n)}

gibt es ein FPRAS wenn x ≥ 1, y ≥ 1.[28]

Obwohl die Situation nicht so gut verstanden ist wie für die genaue Berechnung, ist bekannt, dass große Bereiche der Ebene schwer zu approximieren sind.[24]

Siehe auch[edit]

  1. ^ Bollobás 1998, Kapitel 10.
  2. ^ Biggs 1993, Kapitel 13.
  3. ^ Godsil & Royle 2004, Kap. 15.
  4. ^ Sokal 2005.
  5. ^ Sokal 2005, Gl. (2.26).
  6. ^ ein b c Tutte 2004.
  7. ^ Walisisch.
  8. ^ ein b Farr 2007.
  9. ^ Fortuin & Kasteleyn 1972.
  10. ^ ein b Walisisch 1999.
  11. ^ Las Vergnas 1980.
  12. ^ Korn & Pak 2004.
  13. ^ Siehe Korn & Pak 2003 für kombinatorische Interpretationen vieler anderer Punkte.
  14. ^ Las Vergnas 1988.
  15. ^ Welsh 1993, p. 62.
  16. ^ Welsh & Merino 2000.
  17. ^ Martin 1977.
  18. ^ Wilf 1986, p. 46.
  19. ^ ein b Sekine, Imai & Tani 1995.
  20. ^ Chung & Yau 1999 nach Björklund et al. 2008.
  21. ^ Haggard, Pearce & Royle 2010.
  22. ^ Pearce, Haggard & Royle 2010.
  23. ^ Jerrum & Sinclair 1993.
  24. ^ ein b Goldberg & Jerrum 2008.
  25. ^ Jaeger, Vertigan & Welsh 1990.
  26. ^ Vertigan & Welsh 1992.
  27. ^ Vertigan 2005.
  28. ^ Im Falle x ≥ 1 und y = 1, siehe Annan 1994. Für den Fall x ≥ 1 und y > 1, siehe Alon, Frieze & Welsh 1995.

Verweise[edit]

  • Alon, N.; Frieze, A.; Welsh, DJA (1995), “Polynomialzeit-randomisierte Approximationsschemata für Tutte-Gröthendieck-Invarianten: Der dichte Fall”, Zufällige Strukturen und Algorithmen, 6 (4): 459–478, doi:10.1002 / rsa.3240060409.
  • Annan, JD (1994), “Ein randomisierter Approximationsalgorithmus zum Zählen der Anzahl von Wäldern in dichten Graphen”, Kombinatorik, Wahrscheinlichkeit und Computing, 3 (3): 273–283, doi:10.1017 / S0963548300001188.
  • Biggs, Norman (1993), Algebraische Graphentheorie (2. Aufl.), Cambridge University Press, ISBN 0-521-45897-8.
  • Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), “Berechnung des Tutte-Polynoms in vertexexponentieller Zeit”, Proc. des 47. jährlichen IEEE-Symposiums über Grundlagen der Informatik (FOCS 2008)S. 677–686, arXiv:0711.2585, doi:10.1109 / FOCS.2008.40, ISBN 978-0-7695-3436-7.
  • Bollobás, Béla (1998), Moderne Graphentheorie, Springer, ISBN 978-0-387-98491-9.
  • Chung, Fan; Yau, S.-T. (1999), “Bedeckungen, Hitzekerne und Spannbäume”, Elektronisches Journal für Kombinatorik, 6: R12, MR 1667452.
  • Crapo, Henry H. (1969), “Das Tutte-Polynom”, Aequationes Mathematicae, 3 (3): 211–229, doi:10.1007 / bf01817442.
  • Farr, Graham E. (2007), “Tutte-Whitney-Polynome: einige Geschichte und Verallgemeinerungen”, in Grimmett, Geoffrey; McDiarmid, Colin (Hrsg.), Kombinatorik, Komplexität und Zufall. Eine Hommage an Dominic Welsh, 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), “Über das Random-Cluster-Modell: I. Einführung und Beziehung zu anderen Modellen”, Physica, Elsevier, 57 (4): 536–564, Bibcode:1972Phy …. 57..536F, doi:10.1016 / 0031-8914 (72) 90045-6, ISSN 0031-8914.
  • Godsil, Chris; Royle, Gordon (2004), Algebraische Graphentheorie, Springer, ISBN 978-0-387-95220-8.
  • Goldberg, Leslie Ann; Jerrum, Mark (2008), “Inapproximierbarkeit des Tutte-Polynoms”, Information und Berechnung, 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”, ACM-Transaktionen mit mathematischer Software, 37 (3): Art. 24, 17, doi:10.1145 / 1824801.1824802, HERR 2738228.
  • Jaeger, F.; Vertigan, DL; Welsh, DJA (1990), “Zur rechnerischen Komplexität der Jones- und Tutte-Polynome”, Mathematische Verfahren der Cambridge Philosophical Society, 108 (1): 35–53, Bibcode:1990MPCPS.108 … 35J, doi:10.1017 / S0305004100068936.
  • Jerrum, Mark; Sinclair, Alistair (1993), “Polynom-Zeit-Approximationsalgorithmen für das Ising-Modell” (PDF), SIAM Journal on Computing, 22 (5): 1087–1116, doi:10.1137 / 0222066.
  • Korn, Michael; Pak, Igor (2003), Kombinatorische Auswertungen des Tutte-Polynoms (PDF) (Vordruck).
  • Korn, Michael; Pak, Igor (2004), “Tilings von Rechtecken mit T-Tetrominoes”, Theoretische Informatik, 319 (1–3): 3–27, doi:10.1016 / j.tcs.2004.02.023.
  • Las Vergnas, Michel (1980), “Konvexität in orientierten Matroiden”, Zeitschrift für kombinatorische Theorie, Serie B, 29 (2): 231–243, doi:10.1016 / 0095-8956 (80) 90082-9, ISSN 0095-8956, HERR 0586435.
  • Las Vergnas, Michel (1988), “Zur Bewertung des Tutte-Polynoms eines Graphen bei (3, 3)”, Zeitschrift für kombinatorische Theorie, Serie 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 [Eulerian Enumerations in multigraphs and Tutte-Grothendieck invariants] (Doktorarbeit) (auf Französisch), Joseph Fourier University.
  • Pearce, David J.; Haggard, Gary; Royle, Gordon (2010), “Kantenauswahlheuristiken zur Berechnung von Tutte-Polynomen” (PDF), Chicago Journal of Theoretical Computer Science: Artikel 6, 14, MR 2659710.
  • Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), “Berechnung des Tutte-Polynoms eines Graphen mittlerer Größe”, Algorithmen und Berechnungen (Cairns, 1995), Lecture Notes in Computer Science, 1004Springer, S. 224–233, doi:10.1007 / BFb0015427, HERR 1400247.
  • Sokal, Alan D. (2005), “Das multivariate Tutte-Polynom (alias Potts-Modell) für Graphen und Matroiden”, in Webb, Bridget S. (Hrsg.), Umfragen in der Kombinatorik, Lecture Note Series der London Mathematical Society, 327, Cambridge University Press, S. 173–226, arXiv:math / 0503607, doi:10.1017 / CBO9780511734885.009.
  • Tutte, WT (2001), Graphentheorie, Cambridge University Press, ISBN 978-0521794893.
  • Tutte, WT (2004), “Graph-Polynomials”, Fortschritte in der angewandten Mathematik, 32 (1–2): 5–9, doi:10.1016 / S0196-8858 (03) 00041-1.
  • Vertigan, DL; Welsh, DJA (1992), “Die rechnerische Komplexität der Tutte-Ebene: der zweigliedrige Fall”, Kombinatorik, Wahrscheinlichkeit und Computing, 1 (2): 181–187, doi:10.1017 / S0963548300000195.
  • Vertigan, Dirk (2005), “Die rechnerische Komplexität von Tutte-Invarianten für planare Graphen”, SIAM Journal on Computing, 35 (3): 690–712, doi:10.1137 / S0097539704446797.
  • Welsh, DJA (1976), Matroidentheorie, Academic Press, ISBN 012744050X.
  • Welsh, Dominic (1993), Komplexität: Knoten, Färbungen und Zählen, Lecture Note Series der London Mathematical Society, Cambridge University Press, ISBN 978-0521457408.
  • Welsh, Dominic (1999), “Das Tutte-Polynom”, Zufällige Strukturen & Algorithmen, 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.
  • Walisisch, DJA; Merino, C. (2000), “Das Potts-Modell und das Tutte-Polynom”, Zeitschrift für Mathematische Physik, 41 (3): 1127–1152, Bibcode:2000JMP …. 41.1127W, doi:10.1063 / 1.533181.
  • Wilf, Herbert S. (1986), Algorithmen und Komplexität (PDF), Prentice Hall, ISBN 0-13-021973-8, HERR 0897317.

Externe Links[edit]