Hadwiger Nummer – Wikipedia

Ein Diagramm mit vier verbundenen Untergraphen, die bei Vertragsabschluss ein vollständiges Diagramm bilden. Nach Wagners Theorem hat es kein vollständiges Moll mit fünf Eckpunkten, daher ist seine Hadwiger-Zahl genau vier.

In der Graphentheorie ist die Hadwiger Nummer eines ungerichteten Graphen G ist die Größe des größten vollständigen Graphen, der durch Zusammenziehen der Kanten von erhalten werden kann G. Entsprechend die Hadwiger-Nummer h((G) ist die größte Zahl k für die das komplette Diagramm K._k ist ein Minderjähriger von G, ein kleinerer Graph erhalten von G durch Kantenkontraktionen und Scheitelpunkt- und Kantenlöschungen. Die Hadwiger-Nummer ist auch als bekannt Kontraktionscliquennummer von G oder der Homomorphismusgrad von G. Es ist nach Hugo Hadwiger benannt, der es 1943 in Verbindung mit der Hadwiger-Vermutung einführte, wonach die Hadwiger-Zahl immer mindestens so groß ist wie die chromatische Zahl von G.

Die Graphen mit der Hadwiger-Zahl von höchstens vier wurden von Wagner (1937) charakterisiert. Die Graphen mit einer endlichen Bindung an die Hadwiger-Zahl sind spärlich und haben eine kleine chromatische Zahl. Die Bestimmung der Hadwiger-Zahl eines Graphen ist NP-hart, aber mit festen Parametern nachvollziehbar.

Grafiken mit kleiner Hadwiger-Zahl[edit]

Ein Graph G hat die Hadwiger-Zahl höchstens zwei, wenn und nur wenn es sich um einen Wald handelt, denn ein vollständiger Moll mit drei Scheitelpunkten kann nur durch Kontraktion eines Zyklus in gebildet werden G.

Ein Graph hat genau dann eine Hadwiger-Zahl von höchstens drei, wenn seine Baumbreite höchstens zwei beträgt. Dies gilt genau dann, wenn jede seiner zweifach verbundenen Komponenten ein seriell-paralleler Graph ist.

Eine Cliquensumme aus zwei planaren Graphen und dem Wagner-Graphen, die mit Hadwiger Nummer vier einen größeren Graphen bilden.

Wagners Theorem, das die planaren Graphen durch ihre verbotenen Minderjährigen charakterisiert, impliziert, dass die planaren Graphen höchstens vier Hadwiger-Zahlen haben. In derselben Arbeit, die diesen Satz bewies, charakterisierte Wagner (1937) auch die Graphen mit der Hadwiger-Zahl von höchstens vier genauer: Es handelt sich um Graphen, die durch Cliquensummenoperationen gebildet werden können, die planare Graphen mit dem Wagner-Graphen mit acht Scheitelpunkten kombinieren.

Die Diagramme mit höchstens fünf Hadwiger-Nummern enthalten die Apex-Diagramme und die verlinkbar einbettbaren Diagramme, die beide das vollständige Diagramm enthalten K.₆ unter ihren verbotenen Minderjährigen.

Sparsamkeit[edit]

Jedes Diagramm mit n Eckpunkte und Hadwigerzahl k hat O (nk √Log k) Kanten. Diese Grenze ist eng: für jeden kgibt es Graphen mit Hadwiger-Nummer k die haben Ω (nk √Log k) Kanten.^[4] Wenn ein Graph G hat Hadwiger Nummer k, dann haben alle seine Untergraphen höchstens auch die Hadwiger-Nummer kund daraus folgt G muss Entartung haben O (k √Log k). Daher sind die Graphen mit begrenzter Hadwigerzahl spärliche Graphen.

Färbung[edit]

Die Hadwiger-Vermutung besagt, dass die Hadwiger-Zahl immer mindestens so groß ist wie die chromatische Zahl von G. Das heißt, jeder Graph mit Hadwiger-Nummer k sollte eine Grafikfarbe mit höchstens haben k Farben. Der Fall k = 4 entspricht (durch Wagners Charakterisierung der Graphen mit dieser Hadwiger-Zahl) dem Vierfarbensatz über die Färbung planarer Graphen, und die Vermutung wurde auch bewiesen k ≤ 5, bleibt aber für größere Werte von unbewiesen k.

Aufgrund ihrer geringen Entartung sind die Graphen mit Hadwiger höchstens nummeriert k kann durch einen gierigen Färbealgorithmus mit O (k √Log k) Farben.

Rechenkomplexität[edit]

Testen, ob die Hadwiger-Zahl eines bestimmten Graphen mindestens ein bestimmter Wert ist k ist NP-vollständig, woraus folgt, dass die Bestimmung der Hadwiger-Zahl NP-hart ist. Das Problem ist jedoch mit festen Parametern nachvollziehbar: Es gibt einen Algorithmus zum Auffinden des größten Clique Minor in einer Zeitspanne, die nur polynomial von der Größe des Graphen abhängt, jedoch exponentiell in h((G).^[7] Zusätzlich können Polynomzeitalgorithmen die Hadwiger-Zahl signifikant genauer als die beste Polynomzeitnäherung (unter der Annahme von P ≠ NP) an die Größe des größten vollständigen Teilgraphen approximieren.^[7]

Verwandte konzepte[edit]

Die achromatische Zahl eines Graphen G ist die Größe der größten Clique, die durch das Zusammenziehen einer Familie unabhängiger Gruppen gebildet werden kann G.

Unzählige Clique-Minderjährige in unendlichen Graphen können durch Zufluchtsorte charakterisiert werden, die die Ausweichstrategien für bestimmte Verfolgungsspiele formalisieren: Wenn die Hadwiger-Zahl unzählbar ist, entspricht sie der größten Ordnung eines Hafens in der Grafik.

Jede Grafik mit Hadwiger-Nummer k hat höchstens n2^{Ö(k log log k)}Cliquen (vollständige Untergraphen).

Halin (1976) definiert eine Klasse von Graphparametern, die er aufruft S.-Funktionen, die die Hadwiger-Nummer enthalten. Diese Funktionen von Graphen bis zu ganzen Zahlen müssen in Graphen ohne Kanten Null sein, müssen mollmonoton sein,^[10] um eins zu erhöhen, wenn ein neuer Scheitelpunkt hinzugefügt wird, der an alle vorherigen Scheitelpunkte angrenzt, und den größeren Wert aus den beiden Untergraphen auf beiden Seiten eines Cliquentrenners zu entnehmen. Die Menge all dieser Funktionen bildet unter den Operationen der elementweisen Minimierung und Maximierung ein vollständiges Gitter. Das untere Element in diesem Gitter ist die Hadwiger-Zahl, und das obere Element ist die Baumbreite.

Verweise[edit]