Grafik Nebenfach - Graph minor

In der Graphentheorie , ein ungerichteter Graph H ist ein sogenannter minor des Graphen G , wenn H kann gebildet werden aus G von Kanten und Ecken und durch Löschen Vertrag Kanten .

Die Theorie der Graph-Minors begann mit dem Satz von Wagner, dass ein Graph genau dann planar ist, wenn seine Minor weder den vollständigen Graphen K ₅ noch den vollständigen bipartiten Graphen K _{3,3 umfassen} . Der Satz von Robertson-Seymour impliziert, dass für jede Eigenschaft von Graphen, die durch Deletionen und Kantenkontraktionen erhalten bleibt , eine analoge verbotene Nebencharakterisierung existiert. Für jeden festen Graphen H ist es möglich zu testen, ob H ein Minor eines Eingabegraphen G in polynomieller Zeit ist ; zusammen mit der verbotenen Nebencharakterisierung impliziert dies, dass jede durch Streichungen und Kontraktionen erhaltene Grapheigenschaft in polynomieller Zeit erkannt werden kann.

Andere Ergebnisse und Vermutungen, die Nebenwerte von Graphen beinhalten, sind der Graphenstruktursatz , nach dem die Graphen, die kein H als Nebenwert haben, durch Zusammenkleben einfacherer Teile gebildet werden können, und die Vermutung von Hadwiger, die die Unfähigkeit, einen Graphen zu färben, auf die Existenz von a . bezieht großer vollständiger Graph als kleiner davon. Wichtige Varianten von Graph-Nebenfächern sind die topologischen Nebenfächer und die Immersions-Nebenfächer.

Definitionen

Eine Kantenkontraktion ist eine Operation, die eine Kante aus einem Graphen entfernt und gleichzeitig die beiden Scheitelpunkte zusammenführt, die sie zum Verbinden verwendet hat. Ein ungerichteter Graph H ist ein Minor eines anderen ungerichteten Graphen G, wenn ein zu H isomorpher Graph aus G erhalten werden kann, indem man einige Kanten zusammenzieht, einige Kanten löscht und einige isolierte Ecken löscht. Die Reihenfolge, in der eine Folge solcher Kontraktionen und Löschungen auf G durchgeführt wird, beeinflusst den resultierenden Graphen H nicht .

Graph-Nebenfächer werden oft im allgemeineren Kontext von Matroid-Nebenfächern studiert . In diesem Zusammenhang wird angenommen, dass alle Graphen verbunden sind, wobei Selbstschleifen und Mehrfachkanten zulässig sind ( dh es handelt sich eher um Multigraphen als um einfache Graphen); das Zusammenziehen einer Schleife und das Löschen einer Schnittkante sind verbotene Operationen. Diese Sichtweise hat den Vorteil, dass Kantenlöschungen den Rang eines Graphen unverändert lassen und Kantenkontraktionen den Rang immer um eins reduzieren.

In anderen Kontexten (wie zum Beispiel beim Studium von Pseudowäldern ) ist es sinnvoller, das Löschen einer Schnittkante zuzulassen und getrennte Graphen zuzulassen, aber Multigraphen zu verbieten. In dieser Variation der Graphen-Minor-Theorie wird ein Graph nach jeder Kantenkontraktion immer vereinfacht, um seine Selbstschleifen und Mehrfachkanten zu eliminieren.

Eine Funktion f wird als "moll-monoton" bezeichnet, wenn immer dann, wenn H ein Moll von G ist, f(H) f(G) gilt.

Beispiel

Im folgenden Beispiel ist Graph H ein Minor von Graph G :

H.

G.

Das folgende Diagramm veranschaulicht dies. Konstruieren Sie zuerst einen Teilgraphen von G, indem Sie die gestrichelten Kanten (und den resultierenden isolierten Scheitelpunkt) löschen und dann die graue Kante zusammenziehen (durch Verschmelzen der beiden Scheitelpunkte, die sie verbindet):

Wichtigste Ergebnisse und Vermutungen

Es ist leicht zu verifizieren, dass die Graph-Minor- Relation eine partielle Ordnung auf den Isomorphismusklassen endlicher ungerichteter Graphen bildet: sie ist transitiv (ein Minor eines Minor von G ist ein Minor von G selbst), und G und H können nur Minor sein voneinander, wenn sie isomorph sind, weil jede nichttriviale Nebenoperation Kanten oder Scheitelpunkte entfernt. Ein tiefgreifendes Ergebnis von Neil Robertson und Paul Seymour besagt, dass diese partielle Ordnung tatsächlich eine wohl-quasi-Ordnung ist : Wenn eine unendliche Liste G ₁ , G ₂ ,... von endlichen Graphen gegeben ist, dann existieren immer zwei Indizes i < j so dass G _i ein Minor von G _{j ist} . Eine andere äquivalente Art, dies zu sagen, besteht darin, dass jede Menge von Graphen nur eine endliche Anzahl von minimalen Elementen unter der Nebenordnung haben kann. Dieses Ergebnis bewies eine Vermutung, die früher nach Klaus Wagner als Wagnersche Vermutung bekannt war ; Wagner hatte es schon lange zuvor vermutet, es aber erst 1970 veröffentlicht.

Im Verlauf ihres Beweises beweisen Seymour und Robertson auch den Graphenstruktursatz, in dem sie für jeden festen Graphen H die grobe Struktur jedes Graphen bestimmen, der kein H als Nebenelement hat. Die Aussage des Theorems ist selbst lang und kompliziert, aber kurz gesagt stellt sie fest, dass ein solcher Graph die Struktur einer Cliquensumme kleinerer Graphen haben muss, die geringfügig von Graphen modifiziert werden, die auf Oberflächen der beschränkten Gattung eingebettet sind . Somit stellt ihre Theorie grundlegende Verbindungen zwischen Graph-Minors und topologischen Einbettungen von Graphen her.

Für jeden Graphen H müssen die einfachen H- moll-freien Graphen dünn besetzt sein , was bedeutet, dass die Anzahl der Kanten kleiner ist als ein konstantes Vielfaches der Anzahl der Knoten. Genauer gesagt, wenn H hat h Ecken, dann eine einfache n -eckiges einfachen H - moll-freie Graphen höchstens haben Kanten und einige K _h haben moll-freie Graphen so viele Kanten zumindest. Wenn H also h Knoten hat, dann haben H- moll-freie Graphen einen mittleren Grad und außerdem eine Entartung . Zusätzlich haben die H- moll-freien Graphen einen Separatorsatz ähnlich dem planaren Separatorsatz für planare Graphen: Für jedes feste H und jeden n- Eckpunkt H- moll-freien Graphen G ist es möglich, eine Teilmenge von Ecken zu finden deren Entfernung G in zwei (möglicherweise getrennte) Teilgraphen mit höchstens 2 n /3 Ecken pro Teilgraph aufspaltet . Noch stärker, für jedes feste H haben H- moll-freie Graphen treewidth . ${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$${\displaystyle \scriptstyle O({\sqrt {n}})}$ ${\displaystyle \scriptstyle O({\sqrt {n}})}$

Die Hadwiger-Vermutung in der Graphentheorie schlägt vor, dass, wenn ein Graph G keine Nebenisomorphie zum vollständigen Graphen auf k Ecken enthält, G eine echte Färbung mit k  − 1 Farben hat. Der Fall k  = 5 ist eine Neuformulierung des Vierfarbensatzes . Die Hadwiger-Vermutung ist für k  ≤ 6 bewiesen , aber im allgemeinen Fall unbekannt. Bollobás, Catlin & Erdős (1980) nennen es „eines der tiefsten ungelösten Probleme der Graphentheorie“. Ein weiteres Ergebnis, das das Vierfarben-Theorem auf Graphen- Minors bezieht, ist das von Robertson, Sanders, Seymour und Thomas angekündigte Snark-Theorem , eine Verstärkung des von WT Tutte vermuteten Vierfarben-Theorems , das besagt, dass jeder brückenlose 3-reguläre Graph , der vier . erfordert, Farben in einer Kantenfärbung müssen den Petersen-Graphen als Minor haben.

Nebensächlich geschlossene Graphfamilien

Viele Graphenfamilien haben die Eigenschaft, dass jeder Minor eines Graphen in F auch in F ist ; eine solche Klasse wird als minor-closed bezeichnet . Zum Beispiel kann in jedem planaren Graphen oder jeder Einbettung eines Graphen auf einer festen topologischen Oberfläche weder das Entfernen von Kanten noch die Kontraktion von Kanten die Gattung der Einbettung erhöhen ; daher bilden planare Graphen und die Graphen, die auf einer beliebigen festen Oberfläche einbettbar sind, im Nebensatz geschlossene Familien.

Wenn F eine Moll-geschlossene Familie ist, dann gibt es (wegen der gut-quasi-ordnenden Eigenschaft von Molls) unter den Graphen, die nicht zu F gehören, eine endliche Menge X von Moll-Minimal-Graphen. Diese Graphen sind verbotene Minor für F : Ein Graph gehört genau dann zu F, wenn er keinen Graphen in X als Minor enthält . Das heißt, jede untergeordnete geschlossene Familie F kann als Familie von X- moll-freien Graphen für eine endliche Menge X verbotener untergeordneter Graphen charakterisiert werden . Das bekannteste Beispiel für eine solche Charakterisierung ist Wagners Satz , der die planaren Graphen als die Graphen charakterisiert, die weder K ₅ noch K _3,3 als Minor haben.

In einigen Fällen können die Eigenschaften der Graphen in einer minderjährigen geschlossenen Familie eng mit den Eigenschaften ihrer ausgeschlossenen Minderjährigen verbunden sein. Zum Beispiel eine kleine geschlossene Diagramm Familie F beschränktes hat pathwidth , wenn und nur wenn ihr verboten Minderjährigen einen sind Wald , F beschränktes hat Baumtiefe , wenn und nur wenn ihr verboten Minderjährigen eine disjunkte Vereinigung umfassen Pfadgraphen , F hat beschränkte Baumweite , wenn und nur dann , wenn seine verbotenen Minderjährigen umfassen einen planaren Graphen und F hat lokale Baumweite (eine funktionelle Beziehung zwischen begrenzten Durchmesser und Baumweite) , wenn und nur wenn seine verbotenen Minderjährigen Einschluss- apex Diagramm (ein Diagramm, das planar durch die Entfernung eines einzelnen vorgenommen werden können Scheitel). Wenn H in der Ebene nur mit einer einzigen Kreuzung gezeichnet werden kann ( dh sie hat Kreuzungsnummer eins), dann haben die H- moll-freien Graphen einen vereinfachten Struktursatz, in dem sie als Cliquensummen von planaren Graphen und Graphen gebildet werden von begrenzter Baumbreite. Zum Beispiel haben sowohl K ₅ als auch K _3,3 die Kreuzungsnummer eins, und wie Wagner gezeigt hat, sind die K ₅ -freien Graphen genau die 3-Clique-Summen von planaren Graphen und dem Wagner-Graphen mit acht Ecken , während der K _{3, 3} -freie Graphen sind genau die 2-Clique-Summen von planaren Graphen und  K ₅ .

Variationen

Topologische Nebenfächer

Ein Graph H ist ein sogenannter topologischen minor eines Graphen G , wenn eine Unterteilung von H ist isomorph zu einem Untergraphen von G . Es ist leicht zu erkennen, dass jedes topologische Minor auch ein Minor ist. Das Umgekehrte gilt jedoch im Allgemeinen nicht (zum Beispiel ist der vollständige Graph K ₅ im Petersen-Graphen ein kleiner, aber kein topologischer), sondern gilt für einen Graphen mit maximalem Grad nicht größer als drei.

Die topologische Minor-Beziehung ist keine wohlquasi-Ordnung auf der Menge endlicher Graphen und daher gilt das Ergebnis von Robertson und Seymour nicht für topologische Minor-Beziehungen. Es ist jedoch einfach, endliche verbotene topologische Nebencharakterisierungen aus endlichen verbotenen Nebencharakterisierungen zu konstruieren, indem jede Zweigmenge mit k ausgehenden Kanten durch jeden Baum auf k Blättern ersetzt wird, der mindestens einen Abwärtsgrad von zwei hat.

Induzierte Minderjährige

Ein Graph H heißt induzierter Minor eines Graphen G, wenn er durch Kantenkontraktion aus einem induzierten Teilgraphen von G gewonnen werden kann. Andernfalls G wird gesagt, dass H -induzierten minor frei.

Immersion Minor

Eine Graphenoperation namens Lifting ist von zentraler Bedeutung in einem Konzept namens Immersion . Das Anheben ist ein Vorgang an benachbarten Kanten. Gegeben drei Knoten v , u und w , wobei (v,u) und (u,w) Kanten im Graphen sind, ist das Abheben von vuw oder das Äquivalent von (v,u), (u,w) die Operation das löscht die beiden Kanten (v,u) und (u,w) und fügt die Kante (v,w) hinzu . In dem Fall, in dem (v,w) bereits vorhanden war, werden v und w nun durch mehr als eine Kante verbunden, und daher ist diese Operation intrinsisch eine Multigraph-Operation.

In dem Fall, in dem ein Graph H aus einem Graphen G durch eine Folge von Hebeoperationen (auf G ) und dann Auffinden eines isomorphen Untergraphen erhalten werden kann, sagen wir, dass H ein Immersions-Minor von G ist . Es gibt noch eine andere Möglichkeit, Immersionsminderjährige zu definieren, die dem Hebevorgang entspricht. Wir sagen, dass H ein Immersionsmoll von G ist, wenn es eine injektive Abbildung von Ecken in H zu Ecken in G gibt, wobei die Bilder benachbarter Elemente von H in G durch kantendisjunkte Pfade verbunden sind.

Die Immersions-Moll-Beziehung ist eine wohlquasi-Ordnung auf der Menge endlicher Graphen, und daher gilt das Ergebnis von Robertson und Seymour für Immersions-Moll. Dies bedeutet außerdem, dass jede immersionsminderjährige geschlossene Familie durch eine endliche Familie von verbotenen Immersionsminderjährigen gekennzeichnet ist.

Beim Zeichnen von Graphen entstehen Immersions-Minors als Planarisierungen von nicht-planaren Graphen : Aus einer Zeichnung eines Graphen in der Ebene mit Kreuzungen kann man einen Immersions-Minor bilden, indem man jeden Kreuzungspunkt durch einen neuen Scheitelpunkt ersetzt, und dabei auch Unterteilen jeder gekreuzten Kante in einen Pfad. Dadurch können Zeichenmethoden für planare Graphen auf nicht-planare Graphen erweitert werden.

oberflächliche Minderjährige

Ein flacher Minor eines Graphen G ist ein Minor, bei dem die Kanten von G , die zusammengezogen wurden, um den Minor zu bilden, eine Sammlung von disjunkten Untergraphen mit geringem Durchmesser bilden . Shallow Minors interpolieren zwischen den Theorien von Graph Minors und Subgraphs, indem flache Minors mit hoher Tiefe mit der üblichen Art von Graph Minor übereinstimmen, während die flachen Minors mit Tiefe Null genau die Subgraphen sind. Sie erlauben auch eine Erweiterung der Theorie der Graphen-Minors auf Klassen von Graphen wie die 1-planaren Graphen , die nicht unter Minor geschlossen sind.

Paritätsbedingungen

Eine alternative und äquivalente Definition eines Graphen-Minor ist, dass H ein Minor von G ist, wenn die Ecken von H durch eine Sammlung von knotendisjunkten Unterbäumen von G dargestellt werden können , so dass, wenn zwei Ecken in H benachbart sind , eine Kante existiert mit seinen Endpunkten in den entsprechenden zwei Bäumen in G . Ein ungerader Minor schränkt diese Definition ein, indem diesen Teilbäumen Paritätsbedingungen hinzugefügt werden. Wenn H wie oben durch eine Ansammlung von Unterbäumen von G repräsentiert wird , dann ist H immer dann ein ungerader kleiner von G, wenn es möglich ist, den Scheitelpunkten von G zwei Farben so zuzuweisen , dass jede Kante von G innerhalb eines Unterbaums richtig gefärbt ist (seine Endpunkte haben unterschiedliche Farben) und jede Kante von G , die eine Nachbarschaft zwischen zwei Unterbäumen darstellt, ist monochromatisch (beide Endpunkte haben dieselbe Farbe). Anders als bei der üblichen Art von Graph-Minors sind Graphen mit verbotenen ungeraden Minors nicht unbedingt spärlich. Die Hadwiger-Vermutung , dass k- chromatische Graphen notwendigerweise k- vertex- vollständige Graphen als Minor enthalten , wurde auch aus der Sicht der ungeraden Minor untersucht.

Eine andere paritätsbasierte Erweiterung des Begriffs der Graph-Minors ist das Konzept eines bipartite minor , das einen bipartiten Graphen erzeugt, wenn der Ausgangsgraph bipartit ist. Ein Graph H ist ein bipartites Minor eines anderen Graphen G immer dann, wenn H aus G durch Löschen von Scheiteln, Löschen von Kanten und Kollabieren von Paaren von Scheiteln erhalten werden kann, die entlang eines Umfangszyklus des Graphen im Abstand zwei voneinander entfernt sind . Für bipartite Minor gilt eine Form des Wagnerschen Theorems : Ein bipartiter Graph G ist genau dann ein planarer Graph, wenn er nicht den Nutzengraphen K _3,3 als bipartite Minor besitzt.

Algorithmen

Das Problem der Entscheidung , ob ein Graph G enthält H als Neben NP-vollständig ist im Allgemeinen; wenn beispielsweise H ein Kreisgraph mit der gleichen Anzahl von Ecken wie G ist , dann ist H genau dann ein Minor von G, wenn G einen Hamiltonkreis enthält . Wenn G jedoch Teil der Eingabe ist, aber H fest ist, kann es in polynomieller Zeit gelöst werden. Genauer gesagt ist die Laufzeit zum Testen, ob H ein Minor von G ist, in diesem Fall O ( n ³ ), wobei n die Anzahl der Scheitelpunkte in G ist und die große O-Notation eine Konstante verbirgt, die superexponentiell von H abhängt ; seit dem ursprünglichen Ergebnis von Graph Minors wurde dieser Algorithmus auf die Zeit O ( n ² ) verbessert . Somit ist es durch Anwendung des Polynomialzeitalgorithmus zum Testen, ob ein gegebener Graph irgendwelche der verbotenen Minderjährigen enthält, theoretisch möglich, die Mitglieder einer beliebigen, in Polynomialzeit geschlossenen Familie zu erkennen . Dieses Ergebnis wird in der Praxis nicht verwendet, da die versteckte Konstante so groß ist ( zum Ausdrücken drei Schichten von Knuths Aufwärtspfeil-Notation benötigt ), um jede Anwendung auszuschließen, was sie zu einem galaktischen Algorithmus macht . Um dieses Ergebnis konstruktiv anwenden zu können, ist es außerdem notwendig zu wissen, was die verbotenen Minderjährigen der Graphenfamilie sind. In einigen Fällen sind die verbotenen Minderjährigen bekannt oder können berechnet werden.

Für den Fall, dass H ein fester planarer Graph ist , können wir in linearer Zeit in einem Eingabegraphen G testen, ob H ein Minor von G ist . In Fällen, in denen H nicht festgelegt ist, sind schnellere Algorithmen für den Fall bekannt, in dem G planar ist.

Anmerkungen

Verweise

Externe Links

• Weisstein, Eric W. "Graph Minor" . MathWorld .