Satz von De Bruijn-Erdő (Graphentheorie)
Satz von De Bruijn-Erdő (Graphentheorie) In diesem Artikel geht es um das Färben von unendlichen Graphen. Für die durch eine endliche Menge von Punkten bestimmte Anzahl von Linien, siehe Satz von De Bruijn-Erdő (Einfallsgeometrie).
In der Graphentheorie, Der Satz von De Bruijn-Erdős bezieht die Graphenfärbung eines unendlichen Graphen auf dasselbe Problem auf seinen endlichen Teilgraphen. Es sagt, dass, wenn alle endlichen Teilgraphen mit gefärbt werden können {Anzeigestil c} Farben, das gleiche gilt für den gesamten Graphen. Der Satz wurde von Nicolaas Govert de Bruijn und Paul Erdős bewiesen (1951), nach wem es benannt ist.
Der Satz von De Bruijn-Erdős hat mehrere verschiedene Beweise, alle hängen in gewisser Weise vom Axiom der Wahl ab. Zu seinen Anwendungen gehört die Erweiterung des Vierfarbensatzes und des Satzes von Dilworth von endlichen Graphen und teilweise geordneten Mengen auf unendliche, und Reduzieren des Hadwiger-Nelson-Problems auf die chromatische Zahl der Ebene auf ein Problem über endliche Graphen. Es kann von einer endlichen Anzahl von Farben auf Mengen von Farben verallgemeinert werden, deren Kardinalität eine stark kompakte Kardinalzahl ist.
Inhalt 1 Definitionen und Erklärung 2 Anwendungen 3 Beweise 4 Abhängigkeit von der Wahl 5 Verallgemeinerungen 6 Anmerkungen 7 Referenzen Definitionen und Aussagen Ein ungerichteter Graph ist ein mathematisches Objekt, das aus einer Menge von Scheitelpunkten und einer Menge von Kanten besteht, die Paare von Scheitelpunkten verbinden. Die beiden mit jeder Kante verbundenen Scheitelpunkte werden als Endpunkte bezeichnet. Der Graph ist endlich, wenn seine Ecken und Kanten endliche Mengen bilden, und sonst unendlich. Eine Graphfärbung ordnet jedem Scheitelpunkt eine Farbe zu, die aus einem Satz von Farben gezogen wird, so, dass jede Kante an ihren Endpunkten zwei verschiedene Farben hat. Ein häufiges Ziel beim Färben von Diagrammen ist es, die Gesamtzahl der verwendeten Farben zu minimieren; die chromatische Zahl eines Graphen ist diese minimale Anzahl von Farben.[1] Der Vierfarbensatz besagt, dass jeder endliche Graph, der in der euklidischen Ebene kreuzungsfrei gezeichnet werden kann, höchstens vier Farben benötigt; jedoch, einige Graphen mit komplizierterer Konnektivität erfordern mehr als vier Farben.[2] Aus dem Auswahlaxiom folgt, dass die chromatische Zahl für unendliche Graphen wohldefiniert ist, aber für diese Graphen könnte die chromatische Zahl selbst eine unendliche Kardinalzahl sein.[3] Ein Teilgraph eines Graphen ist ein anderer Graph, der aus einer Teilmenge seiner Scheitelpunkte und einer Teilmenge seiner Kanten erhalten wird. Wenn die größere Grafik farbig ist, die gleiche Färbung kann für den Untergraphen verwendet werden. Deswegen, die chromatische Zahl eines Teilgraphen kann nicht größer sein als die chromatische Zahl des gesamten Graphen. Der Satz von De Bruijn-Erdős betrifft die chromatischen Zahlen unendlicher Graphen, und zeigt das (wieder, Annahme des Wahlaxioms) sie können aus den chromatischen Zahlen ihrer endlichen Teilgraphen berechnet werden. Es sagt, dass, wenn die chromatischen Zahlen der endlichen Teilgraphen eines Graphen {Anzeigestil G} einen endlichen Maximalwert haben {Anzeigestil c} , dann die chromatische Zahl von {Anzeigestil G} selbst ist genau {Anzeigestil c} . Auf der anderen Seite, wenn es keine endliche Obergrenze für die chromatischen Zahlen der endlichen Untergraphen von gibt {Anzeigestil G} , dann die chromatische Zahl von {Anzeigestil G} selbst muss unendlich sein.[4] Anwendungen Die ursprüngliche Motivation von Erdős beim Studium dieses Problems bestand darin, den Satz that von endlichen auf unendliche Graphen zu erweitern, immer dann, wenn ein Graph eine Orientierung mit endlichem maximalen Außengrad hat {Anzeigestil k} , es hat auch eine {Anzeigestil (2k+1)} -Färbung. Für endliche Graphen folgt dies, weil solche Graphen immer höchstens einen Knoten vom Grad haben {Anzeigestil 2k} , die mit einem von eingefärbt werden können {Anzeigestil 2k+1} Farben, nachdem alle verbleibenden Scheitelpunkte rekursiv gefärbt wurden. Unendliche Graphen mit einer solchen Orientierung haben nicht immer einen Scheitelpunkt niedrigen Grades (zum Beispiel, Bethe Gitter haben {Anzeigestil k=1} aber beliebig großer Mindestgrad), Dieses Argument erfordert also, dass der Graph endlich ist. Aber der Satz von De Bruijn-Erdős zeigt, dass a {Anzeigestil (2k+1)} -Färbung existiert sogar für unendliche Graphen.[5] Eine Siebenfärbung des Flugzeugs, und die vierfarbige Moser-Spindel, die als Einheitsabstandsgraph in der Ebene gezeichnet ist, Bereitstellung von Ober- und Untergrenzen für das Hadwiger-Nelson-Problem.
Eine weitere Anwendung des Satzes von De Bruijn-Erdős ist das Hadwiger-Nelson-Problem, die fragt, wie viele Farben benötigt werden, um die Punkte der euklidischen Ebene so zu färben, dass alle zwei Punkte, die eine Abstandseinheit voneinander entfernt sind, unterschiedliche Farben haben. Dies ist ein Graphenfärbungsproblem für einen unendlichen Graphen, der einen Scheitelpunkt für jeden Punkt der Ebene und eine Kante für jeweils zwei Punkte hat, deren euklidischer Abstand genau eins ist. Die induzierten Teilgraphen dieses Graphen werden Einheitsabstandsgraphen genannt. Ein Abstandsdiagramm mit sieben Scheitelpunkten, die Moser-Spindel, erfordert vier Farben; in 2018, Es wurden viel größere Einheitsabstandsdiagramme gefunden, die fünf Farben erfordern.[6] Der gesamte unendliche Graph hat eine bekannte Färbung mit sieben Farben, basierend auf einer sechseckigen Kachelung der Ebene. Deswegen, die chromatische Zahl der Ebene muss eine von beiden sein 5, 6, oder 7, aber es ist nicht bekannt, welche dieser drei Zahlen der richtige Wert ist. Das zeigt der Satz von De Bruijn-Erdős, für dieses Problem, Es gibt einen endlichen Einheitsabstandsgraphen mit derselben chromatischen Zahl wie die gesamte Ebene, Wenn also die chromatische Zahl größer als fünf ist, kann diese Tatsache durch eine endliche Rechnung bewiesen werden.[7] Der Satz von De Bruijn-Erdős kann auch verwendet werden, um den Satz von Dilworth von endlichen auf unendliche teilweise geordnete Mengen zu erweitern. Der Satz von Dilworth besagt, dass die Breite einer Teilordnung (die maximale Anzahl von Elementen in einer Menge miteinander nicht vergleichbarer Elemente) entspricht der Mindestanzahl von Ketten (total geordnete Teilmengen) in die die Teilordnung aufgeteilt werden kann. Eine Aufteilung in Ketten kann als Färbung des Unvergleichbarkeitsgraphen der Teilordnung interpretiert werden. Dies ist ein Graph mit einem Scheitelpunkt für jedes Element der Ordnung und einer Kante für jedes Paar von unvergleichbaren Elementen. Verwenden Sie diese Farbinterpretation, zusammen mit einem separaten Beweis des Satzes von Dilworth für endliche teilweise geordnete Mengen, Es ist möglich zu beweisen, dass eine unendliche teilweise geordnete Menge endliche Breite hat {Anzeigestil m} wenn und nur wenn es eine Partition in hat {Anzeigestil m} Ketten.[8] Auf die gleiche Weise, Der Satz von De Bruijn-Erdős erweitert den Vierfarbensatz von endlichen planaren Graphen auf unendliche planare Graphen. Jeder endliche planare Graph kann mit vier Farben eingefärbt werden, nach dem Vierfarbensatz. Der Satz von De Bruijn-Erdős zeigt dann, dass jeder Graph ohne Kreuzungen in der Ebene gezeichnet werden kann, endlich oder unendlich, kann mit vier Farben eingefärbt werden. Allgemeiner, jeder unendliche Graph, für den alle endlichen Teilgraphen planar sind, kann wieder vierfarbig sein.[9] Beweise Der ursprüngliche Beweis des Satzes von De Bruijn-Erdős, von DeBruyn, verwendet transfinite Induktion.[10] Gottschalk (1951) lieferte den folgenden sehr kurzen Beweis, basierend auf dem Kompaktheitssatz von Tychonoff in der Topologie. Nehme an, dass, für den gegebenen unendlichen Graphen {Anzeigestil G} , jeder endliche Teilgraph ist {Anzeigestil k} -färbbar, und lass {Anzeigestil X} sei der Raum aller Zuweisungen der {Anzeigestil k} Farben zu den Eckpunkten von {Anzeigestil G} (unabhängig davon, ob sie eine gültige Färbung bilden). Dann {Anzeigestil X} kann eine Topologie als Produktraum gegeben werden {Anzeigestil k^{v(G)}} , wo {Anzeigestil V(G)} bezeichnet die Menge der Knoten des Graphen. Nach dem Satz von Tychonoff ist dieser topologische Raum kompakt. Für jeden endlichen Teilgraphen {Anzeigestil F} von {Anzeigestil G} , Lassen {Anzeigestil X_{F}} sei die Teilmenge von {Anzeigestil X} bestehend aus Zuweisungen von Farben, die gültig färben {Anzeigestil F} . Dann das Mengensystem {Anzeigestil X_{F}} ist eine Familie abgeschlossener Mengen mit endlicher Schnitteigenschaft, aufgrund der Kompaktheit hat es also einen nichtleeren Durchschnitt. Jedes Mitglied dieser Schnittmenge ist eine gültige Färbung von {Anzeigestil G} .[11] Ein anderer Beweis mit dem Lemma von Zorn wurde von Lajos Pósa gegeben, und auch im 1951 Ph.D. Dissertation von Gabriel Andrew Dirac. Wenn {Anzeigestil G} ist ein unendlicher Graph, in dem jeder endliche Teilgraph ist {Anzeigestil k} -färbbar, dann ist es nach dem Lemma von Zorn ein Teilgraph eines maximalen Graphen {Anzeigestil M} mit gleichem Eigentum (eine, zu der keine weiteren Kanten hinzugefügt werden können, ohne dass ein endlicher Untergraph mehr als benötigt {Anzeigestil k} Farben). Die binäre Beziehung der Nichtadjazenz in {Anzeigestil M} ist eine Äquivalenzrelation, und seine Äquivalenzklassen bieten a {Anzeigestil k} -Färbung von {Anzeigestil G} . Jedoch, dieser Beweis ist schwieriger zu verallgemeinern als der Kompaktheitsbeweis.[12] Der Satz kann auch mit Ultrafiltern bewiesen werden[13] oder Nicht-Standard-Analyse.[14] Nash-Williams (1967) gibt einen Beweis für Graphen mit einer abzählbaren Anzahl von Scheitelpunkten basierend auf dem Unendlichkeitslemma von König.
Abhängigkeit von der Wahl Alle Beweise des Satzes von De Bruijn-Erdős verwenden irgendeine Form des Wahlaxioms. Eine Form dieser Annahme ist notwendig, da es Modelle der Mathematik gibt, in denen sowohl das Auswahlaxiom als auch der Satz von De Bruijn-Erdős falsch sind. Etwas präziser, Mycielski (1961) zeigte, dass der Satz eine Folge des Booleschen Primzahl-Ideal-Satzes ist, eine Eigenschaft, die durch das Wahlaxiom impliziert wird, aber schwächer ist als das vollständige Wahlaxiom, und Läuchli (1971) zeigte, dass der De Bruijn-Erdős-Satz und der Boolesche Primzahl-Ideal-Satz in axiomatischer Kraft äquivalent sind.[15] Es kann auch gezeigt werden, dass der Satz von De Bruijn-Erdő für zählbare Graphen in der axiomatischen Kraft äquivalent ist, innerhalb einer Theorie der Arithmetik zweiter Ordnung, zum Unendlichkeitslemma von König.[16] Für ein Gegenbeispiel zum Theorem in Modellen der Mengenlehre ohne Wahl, Lassen {Anzeigestil G} Sei ein unendlicher Graph, in dem die Ecken alle möglichen reellen Zahlen darstellen. Im {Anzeigestil G} , Verbinde jeweils zwei reelle Zahlen {Anzeigestil x} und {Anzeigestil y} durch eine Kante, wenn einer der Werte {Anzeigestil |x-y|pm {quadrat {2}}} ist eine rationale Zahl. Äquivalent, in dieser Grafik, Zwischen allen reellen Zahlen gibt es Kanten {Anzeigestil x} und alle reellen Zahlen der Form {Anzeigestil x+qpm {quadrat {2}}} , für rationale Zahlen {Anzeigestil q} . Jeder Pfad in diesem Diagramm, ausgehend von einer beliebigen reellen Zahl {Anzeigestil x} , wechselt zwischen Zahlen, die sich von unterscheiden {Anzeigestil x} durch eine rationale Zahl plus ein gerades Vielfaches von {Anzeigestil {quadrat {2}}} und Zahlen, die von abweichen {Anzeigestil x} durch eine rationale Zahl plus ein ungerades Vielfaches von {Anzeigestil {quadrat {2}}} . Diese Abwechslung verhindert {Anzeigestil G} keine Zyklen ungerader Länge enthalten, so benötigt jeder seiner endlichen Teilgraphen nur zwei Farben. Jedoch, im Solovay-Modell, in dem jede Menge reeller Zahlen Lebesgue-messbar ist, {Anzeigestil G} benötigt unendlich viele Farben, da in diesem Fall jede Farbklasse eine messbare Menge sein muss und gezeigt werden kann, dass jede messbare Menge reelle Zahlen ohne Kanten enthält {Anzeigestil G} muss das Maß Null haben. Deswegen, im Solovay-Modell, das (unendlich) chromatische Zahl aller {Anzeigestil G} ist viel größer als die chromatische Zahl seiner endlichen Teilgraphen (höchstens zwei).[17] Verallgemeinerungen Rado (1949) beweist den folgenden Satz, was als Verallgemeinerung des De Bruijn-Erdős-Theorems angesehen werden kann. Lassen {Anzeigestil V} sei eine unendliche Menge, zum Beispiel die Menge der Knoten in einem unendlichen Graphen. Für jedes Element {Anzeigestil v} von {Anzeigestil V} , Lassen {Anzeigestil c_{v}} sei eine endliche Menge von Farben. Zusätzlich, für jede endliche Teilmenge {Anzeigestil S} von {Anzeigestil V} , Wählen Sie eine bestimmte Farbe {Anzeigestil C_{S}} von {Anzeigestil S} , in dem die Farbe jedes Elements {Anzeigestil v} von {Anzeigestil S} gehört {Anzeigestil c_{v}} . Dann gibt es eine globale Färbung {Displaystil Chi } von allen {Anzeigestil V} mit der Eigenschaft, dass jede endliche Menge {Anzeigestil S} hat eine endliche Obermenge {Anzeigestil T} auf welche {Displaystil Chi } und {Anzeigestil C_{T}} zustimmen. Im Speziellen, wenn wir a wählen {Anzeigestil k} -Färbung für jeden endlichen Teilgraphen eines unendlichen Graphen {Anzeigestil G} , dann gibt es ein {Anzeigestil k} -Färbung von {Anzeigestil G} in dem jeder endliche Graph einen größeren Supergraphen hat, dessen Färbung mit der Färbung des gesamten Graphen übereinstimmt.[18] Wenn ein Graph keine endliche chromatische Zahl hat, dann impliziert der Satz von De Bruijn-Erdős, dass er endliche Untergraphen jeder möglichen endlichen chromatischen Zahl enthalten muss. Forscher haben auch andere Bedingungen auf den Subgraphen untersucht, die in diesem Fall zwangsläufig auftreten. Zum Beispiel, unbegrenzt chromatische Graphen müssen auch jeden möglichen endlichen bipartiten Graphen als Teilgraphen enthalten. Jedoch, Sie können einen beliebig großen ungeraden Umfang haben, und daher können sie jede endliche Menge von nicht zweigeteilten Untergraphen vermeiden.[19] Der Satz von De Bruijn-Erdős gilt auch direkt für Hypergraph-Färbeprobleme, wobei man verlangt, dass jede Hyperkante Scheitelpunkte von mehr als einer Farbe hat. Was Graphen angeht, Ein Hypergraph hat a {Anzeigestil k} -Färbung genau dann, wenn jeder seiner endlichen Unterhypergraphen a hat {Anzeigestil k} -Färbung.[20] Es ist ein Spezialfall des Kompaktheitssatzes von Kurt Gödel, besagt, dass eine Menge von Sätzen erster Ordnung genau dann ein Modell hat, wenn jede endliche Teilmenge davon ein Modell hat.[21] Genauer, Der Satz von De Bruijn-Erdő kann als Kompaktheit der Strukturen erster Ordnung interpretiert werden, deren nicht logische Werte eine endliche Menge von Farben sind und deren einziges Prädikat auf diesen Werten die Ungleichheit ist.[22] Der Satz kann auch auf Situationen verallgemeinert werden, in denen die Anzahl der Farben eine unendliche Kardinalzahl ist. Wenn {Anzeigestil kappa } ist ein stark kompakter Kardinal, dann für jeden Graphen {Anzeigestil G} und Kardinalzahl {zeige ihn an
Wenn Sie andere ähnliche Artikel wissen möchten Satz von De Bruijn-Erdő (Graphentheorie) Sie können die Kategorie besuchen Diagrammfärbung.
Hinterlasse eine Antwort