Der Ursprung des Begriffs der Baumbreite

Meine Frage ist heute (wie immer) ein bisschen albern; Ich bitte Sie jedoch, dies zu prüfen.

Ich wollte etwas über die Entstehung und / oder Motivation des baumweiten Konzepts wissen. Ich verstehe sicher, dass es in FPT-Algorithmen verwendet wird, aber ich glaube nicht, dass dies der Grund war, warum dieser Begriff definiert wurde.

Die dazugehörigen Notizen habe ich in der Klasse von Prof. Robin Thomas aufgeschrieben . Ich denke, ich verstehe einige der Anwendungen dieses Konzepts (da es die Trenneigenschaften des Baums auf das zerlegte Diagramm überträgt), aber aus irgendeinem Grund bin ich nicht wirklich überzeugt, dass der Grund, warum dieses Konzept entwickelt wurde, darin bestand, die Nähe eines Diagramms zu messen zu einem Baum.

Ich werde versuchen, mich klarer zu machen (ich bin nicht sicher, ob ich kann, lassen Sie es mich bitte wissen, wenn die Frage nicht klar ist). Ich würde gerne wissen, ob es in einem anderen Bereich der Mathematik ähnliche Begriffe gibt, von denen dieser Begriff angeblich "entlehnt" wurde. Meine Vermutung wird Topologie sein - aber aufgrund meines fehlenden Hintergrunds kann ich nichts sagen.

Der Hauptgrund dafür, warum ich neugierig bin, ist: Als ich die Definition zum ersten Mal las, war ich mir nicht sicher, warum und wie sich jemand das vorstellen würde und zu welchem ​​Zweck. Wenn die Frage immer noch nicht klar ist, würde ich endlich versuchen, sie so auszudrücken - tun wir so, als gäbe es den Begriff der Baumbreite nicht. Welche natürlichen Fragen (oder Erweiterungen einiger mathematischer Theoreme / Konzepte) zu diskreten Einstellungen führen dazu, dass man sich eine Definition (lassen Sie mich das betreffende Wort verwenden) als Baumbreite vorstellt.

Wenn Sie wirklich wissen wollen, was Neil Robertson und mich zu einer Baumbreite geführt hat, dann waren es überhaupt keine Algorithmen. Wir haben versucht, Wagners Vermutung zu lösen, dass in einer unendlichen Menge von Graphen einer von ihnen ein Moll eines anderen ist, und wir waren am Anfang richtig. Wir wussten, dass es wahr ist, wenn wir uns auf Graphen ohne k-Vertex-Pfad beschränken. lass mich erklären warum. Wir wussten, dass alle diese Graphen eine einfache Struktur haben (genauer gesagt, jeder Graph ohne k-Vertex-Pfad hat diese Struktur und jeder Graph mit dieser Struktur hat keinen 2 ^ k-Vertex-Pfad). und wir wussten, dass in jeder unendlichen Menge von Graphen, die alle diese Struktur hatten, einer von ihnen ein kleinerer von einem anderen war. Wagners Vermutung stimmte also für Graphen mit einer Begrenzung ihrer maximalen Weglänge.

Wir wussten auch, dass dies für Graphen ohne k-Stern als Moll zutrifft, da wir für solche Graphen einen Struktursatz hatten. Wir versuchten, nach allgemeineren Minderjährigen zu suchen, die entsprechende Struktursätze hatten, mit denen wir Wagners Vermutung beweisen konnten, und die uns zu einer Pfadbreite führten. Wenn Sie einen Baum als Nebenbaum ausschließen, erhalten Sie eine begrenzte Pfadbreite. Wenn Sie eine begrenzte Pfadbreite haben, gibt es Bäume, die Sie als Nebenbaum nicht haben können. (Das war ein schwieriger Satz für uns; wir hatten einen äußerst schwierigen Beweis in der ersten Ausgabe von Graph Minors, lesen Sie ihn nicht, es kann viel einfacher gemacht werden.) Aber wir konnten Wagners Vermutung für Graphen mit begrenzter Pfadbreite beweisen und das bedeutete, dass es für Graphen zutraf, die keinen festen Baum als Moll enthielten; eine große Verallgemeinerung der Pfad- und Sternfälle, die ich zuvor erwähnt habe.

Damit haben wir jedenfalls versucht, weiter zu kommen. Wir konnten keine allgemeinen Graphen erstellen, also haben wir uns Gedanken über ebene Graphen gemacht. Wir haben einen Struktursatz für die planaren Graphen gefunden, der keine festen planaren Graphen als Nebengraphen enthielt (dies war einfach); es war baumbreitenbeschränkt. Wir haben bewiesen, dass für jeden festen planaren Graphen alle planaren Graphen, die ihn nicht als Minor enthielten, die Baumbreite begrenzt hatten. Wie Sie sich vorstellen können, war das wirklich aufregend. Zufällig war der Struktursatz zum Ausschließen von ebenen Graphen (innerhalb größerer ebener Graphen) eine natürliche Wendung des Struktursatzes zum Ausschließen von Bäumen (innerhalb allgemeiner Graphen). Wir hatten das Gefühl, etwas richtig zu machen. Und das lässt uns Wagners Vermutung für alle planaren Graphen beweisen, weil wir diesen Struktursatz hatten.

Da die Baumbreite beim Ausschließen von ebenen Diagrammen in größeren ebenen Diagrammen funktioniert hat, war es eine natürliche Frage, ob das Ausschließen von ebenen Diagrammen in nicht ebenen Diagrammen möglich ist Moll hatte Baumbreite begrenzt? Dies konnten wir lange Zeit nicht beweisen, aber so kamen wir dazu, über die Baumbreite allgemeiner Graphen nachzudenken. Und als wir das Konzept der Baumbreite hatten, war es ziemlich klar, dass es gut für Algorithmen war. (Und ja, wir hatten keine Ahnung, dass Halin bereits über die Baumbreite nachgedacht hatte.)

So können Sie sich selbst ein baumbreites Konzept einfallen lassen.

Angenommen, Sie möchten die Anzahl der unabhängigen Mengen in der folgenden Grafik zählen.

Unabhängige Mengen können in solche unterteilt werden, bei denen der oberste Knoten belegt ist, und solche, bei denen er nicht belegt ist

Beachten Sie nun, dass Sie, wenn Sie wissen, ob der oberste Knoten belegt ist, die Anzahl der unabhängigen Mengen in jedem Unterproblem separat zählen und diese multiplizieren können. Wenn Sie diesen Vorgang rekursiv wiederholen, erhalten Sie einen Algorithmus zum Zählen unabhängiger Mengen basierend auf Diagrammtrennzeichen.

Angenommen, Sie haben keinen Baum mehr. Dies bedeutet, dass die Trennzeichen größer sind, Sie können jedoch dieselbe Idee verwenden. Ziehen Sie in der folgenden Grafik in Betracht, unabhängige Mengen zu zählen.

Verwenden Sie die gleiche Idee, um das Problem in Unterprobleme auf dem Separator aufzuteilen

Wie im vorherigen Beispiel wird jeder Term in der Summe im Trennzeichen in zwei kleinere Zählaufgaben zerlegt.

Beachten Sie, dass die Summe mehr Terme enthält als im vorherigen Beispiel, da wir alle Konfigurationen in unserem Separator auflisten müssen, die potenziell exponentiell mit der Größe des Separators wachsen können (in diesem Fall Größe 2).

Die Baumzerlegung ist eine Datenstruktur zum kompakten Speichern dieser rekursiven Partitionierungsschritte. Betrachten Sie das folgende Diagramm und seine Baumzerlegung

Um mit dieser Zerlegung zu zählen, müssen Sie zuerst die Werte in Knoten 3,6 korrigieren, wodurch die Zerlegung in 2 Unterprobleme unterteilt wird. Im ersten Teilproblem würden Sie zusätzlich Knoten 5 reparieren, der seinen Teil in zwei kleinere Teile aufteilt.

Die Größe des größten Separators bei einer optimalen rekursiven Zerlegung ist genau die Baumbreite. Bei größeren Zählproblemen dominiert die Größe des größten Separators die Laufzeit, weshalb diese Größe so wichtig ist.

Bezüglich des Konzepts der Baumbreitenmessung, wie nah ein Graph an einem Baum ist, besteht eine Möglichkeit, es intuitiv zu machen, darin, die alternative Herleitung der Baumzerlegung zu betrachten - aus der Entsprechung mit Akkorddiagrammen. Triangulieren Sie zunächst den Graphen, indem Sie die Scheitelpunkte der Reihe nach durchlaufen und alle "höherwertigen" Nachbarn der einzelnen Scheitelpunkte miteinander verbinden.

Dann konstruieren Sie die Baumzerlegung, indem Sie maximale Cliquen nehmen und verbinden, wenn ihre Schnittmenge ein maximales Trennzeichen ist.

Auf rekursiven Separatoren und Triangulationen basierende Ansätze zur Konstruktion der Baumzerlegung sind äquivalent. Die Baumbreite + 1 ist die Größe der größten Clique bei optimaler Triangulation des Diagramms oder, wenn das Diagramm bereits trianguliert ist, nur die Größe der größten Clique.

In gewissem Sinne kann man sich Akkordgraphen mit der Breite tw als Bäume vorstellen, bei denen wir anstelle einzelner Knoten überlappende Cliquen mit einer Größe von höchstens tw + 1 haben. Nicht-Akkord-Graphen sind solche "Clique-Bäume", bei denen einige Clique-Kanten fehlen

Hier sind einige Akkorddiagramme und ihre Baumbreite.

Ich glaube, die Baumbreite selbst begann mit dem bereits gegebenen Artikel von Robertson Seymour. Einige frühere Vorläufer scheinen jedoch zu sein:

• Das Konzept einer "Dimension" eines Graphen, die das Verhalten von dynamischen Programmieralgorithmen darauf steuern würde, von Bertelé, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming .

• Das Konzept von Verfolgungs-Ausweich-Spielen auf Graphen von Parsons, TD (1976). "Verfolgungshinterziehung in einer Grafik". Theorie und Anwendung von Graphen . Springer-Verlag. S. 426–441. Eine Variante davon erwies sich viel später als gleichwertig mit der Baumbreite: Seymour, Paul D .; Thomas, Robin (1993), "Graphensuche und ein Min-Max-Theorem für die Baumbreite ", Journal of Combinatorial Theory, Reihe B 58 (1): 22–33, doi: 10.1006 / jctb.1993.1027 .

• Trennzeichenhierarchien für planare Graphen, beginnend mit Ungar, Peter (1951), "Ein Theorem über planare Graphen", Journal der London Mathematical Society 1 (4): 256, doi: 10.1112 / jlms / s1-26.4.256 und weiter mit mehreren Arbeiten von Lipton und Tarjan in den Jahren 1979-1980. Die Größe des größten Trennzeichens in einer Hierarchie dieses Typs hängt eng mit der Baumbreite zusammen.

Wenn wir uns einer Zeit nähern, in der die Robertson-Seymour-Ideen möglicherweise bereits im Umlauf waren, gibt es vor Graph Minors II auch einen Artikel, in dem die Ideen der Verfolgung, Umgehung und Trennung explizit miteinander verknüpft werden und der Begriff der Breite der Pfadbreite gleichgesetzt wird : Ellis, JA; Sudborough, IH; Turner, JS (1983), "Graph Separation and Search Number", Proc. 1983 Allerton Conf. zu Kommunikation, Kontrolle und Computing.

Reinhard Diestel führt in seiner Monographie zur Graphentheorie das Konzept der Baumbreite und der Baumzerlegung auf eine Arbeit von Halin aus dem Jahr 1976 zurück (allerdings ohne diese Namen). Er führt auch auf dieses Papier das Ergebnis zurück, dass planare Gittergraphen eine unbegrenzte Baumbreite haben. Natürlich erwähnt er auch den späteren Aufsatz von Robertson und Seymour, die "das Konzept wiederentdeckten, offensichtlich ohne Kenntnis von Halins Werk" (sorry, wenn meine Übersetzung schlecht ist).

• $S$
• Reinhard Diestel. Graphentheorie , 3. Deutsche Ausgabe, Notizen zu Kapitel 10. (Einige englische Ausgaben des Buches sind online zum kostenlosen Download verfügbar.)

Der Begriff der Baumbreite [1] (und der ähnliche Begriff der Astbreite ) wurde von Robertson und Seymour in ihren wegweisenden Arbeiten zu Graph Minors eingeführt .

$G$$H$

Siehe: N. Robertson, PD Seymour. Graph Minors. II. Algorithmische Aspekte der Baumbreite . JCT Series B (1986)