Benutzer:Schojoha/Spielwiese/Graphentheorie

Zum Satz von Hajnal und Surányi

Satz

Es gilt der folgende Lehrsatz, der auf eine Arbeit von András Hajnal und János Surányi aus dem Jahre 1958 zurückgeht:

Ist $G$ ein endlicher, schlichter, chordaler Graph und , so stimmen für jeden induzierten Teilgraphen $G^{'}$ von $G$ die Unabhängigkeitszahl $\alpha (G^{'})$ überein mit der kleinsten Anzahl $\theta (G^{'})$ von Cliquen einer Cliquenüberdeckung von $G$.

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie. Springer-Verlag, Wien, New York 1996, ISBN 3-211-82774-9, S. 202 ff. 

Satz von Mantel

Der Satz von Mantel , englisch Mantel's theorem, ist einer der klassischen Lehrsätze des mathematischen Teilgebiets der extremalen Graphentheorie. Der Satz geht auf eine Arbeit von W. Mantel aus dem Jahre 1907 zurück und behandelt eine Bedingung, unter der ein Graph Dreiecke enthält.

Formulierung des Satzes

Der Satz lässt sich zusammengefasst angeben wie folgt:

Gegeben sei ein endlicher schlichter Graph $G=(V,E)$ der Knotenzahl $n=n(G)$ und der Kantenzahl $m=m(G)$.

Dabei soll die Ungleichung

$m>{\frac {n^{2}}{4}}$

erfüllt sein.

Dann enthält $G$ einen Kreisgraphen vom Typ $\,C_{3}\,$.

Anders gesagt:

Ist ein endlicher schlichter Graph der Knotenzahl $\,n\,$ dreiecksfrei, so besitzt er höchstens $\,{\tfrac {n^{2}}{4}}\,$ Kanten.

Verwandter Satz

→ Hauptartikel: Satz von Reiman

Von István Reiman (1927–2012) wurde im Jahre 1958 ein dem Mantel'schen verwandter Satz vorgelegt, welcher die entsprechende Fragestellung für den Kreisgraphen vom Typ $C_{4}$ behandelt. Dieser Satz lässt sich angeben wie folgt:

Sei $\,G\,$ ein endlicher schlichter Graph der Knotenzahl $\,n\,$ und der Kantenzahl $\,m\,$ und sei weiter vorausgesetzt, dass $\,G\,$ keinen Kreisgraphen des Typs $C_{4}$ enthalte.

Dann ist die Ungleichung

$m\leq \lfloor {\frac {n}{4}}\cdot \left(1+{\sqrt {4n-3}}\right)\rfloor$

erfüllt.

Hintergrund

Zum Beweis des Mantel’schen Satzes werden in der Monographie Extremal Combinatorics von Stasys Jukna sowohl die Cauchy-Schwarzsche Ungleichung als auch (nicht zuletzt) zwei elementare Formeln zu Mengensystemen auf endlichen Mengen herangezogen. Letztere lassen sich angeben wie folgt:

Gegeben sei eine endliche Menge $X$ sowie ein Teilmengensystem ${\mathcal {F}}\subseteq {\mathcal {P}}(X)$ und dazu der Hypergraph $H=(X,{\mathcal {F}})$.

Dabei sei $d\colon \,X\to \mathbb {N} _{0},\,x\mapsto d(x):=|\{F\in {\mathcal {F}}\mid x\in F\}|\,(x\in X)\,$ die zugehörige $H$-Gradfunktion.

Dann gelten folgende Formeln:

(i) $\sum _{x\in Y}d(x)=\sum _{F\in {\mathcal {F}}}|Y\cap F|\,\,\left(\forall Y\subseteq X\right)$ .

(ii) $\sum _{x\in X}{d(x)^{2}}=\sum _{F\in {\mathcal {F}}}\sum _{x\in F}d(x)=\sum _{F_{1}\in {\mathcal {F}}}\sum _{F_{2}\in {\mathcal {F}}}|F_{1}\cap F_{2}|$ .

Literatur

• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. Mit Zeichnungen von Karl H. Hofmann. 5. Auflage. Springer-Verlag, Berlin, Heidelberg 2018, ISBN 978-3-662-57766-0, doi:10.1007/978-3-662-57767-7. 
• Zoltán Füredi, András Gyárfás: An extension of Mantel’s theorem to k-graphs. In: American Mathematical Monthly. Band 127, 2020, S. 263–268 (MR4067898). 
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer-Verlag, Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9 (MR2865719). 
• László Lovász: Combinatorial Problems and Exercises (= Texts in Theoretical Computer Science). North-Holland Publishing Company, Amsterdam, New York, Oxford 1979, ISBN 0-444-85219-0 (MR0537284). 
• W. Mantel: Problem 28. In: Wiskundige Opgaven 10. Band 10, 1907, S. 60–61. 

Einzelnachweise

rreferences />

Anmerkungen

rreferences group="A" />

KKKategorie:Satz (Graphentheorie)|Mantel]]

Satz von Ghouila-Houri

In der Theorie der gerichteten Graphen, einem der Teilgebiete der Graphentheorie, ist der Satz von Ghouila-Houri das Pendant zum Satz von Dirac in der Theorie der ungerichteten Graphen. Der Satz geht auf eine Arbeit des französischen Mathematikers Alain Ghouila-Houri aus dem Jahre 1960 zurück. Von mehreren Autoren wird hervorgehoben, dass der Beweis des Ghouila-Houri'schen Satzes um einiges schwieriger sei als der des diracschen.

Formulierung des Satzes

Der Satz lässt sich zusammengefasst angeben wie folgt:

Gegeben sei ein endlicher gerichteter Graph $D$.

$D$ sei stark zusammenhängend und habe zudem die Eigenschaft, dass an jedem Knoten $v$ für den Grad $d_{G}(v)=d_{G}^{-}(v)+d_{G}^{+}(v)$ in Bezug auf die Knotenzahl $n(D)$ durchweg die Ungleichung

${d_{G}}(v)\geq n(D)$

erfüllt ist.

Dann besitzt $D$ einen hamiltonschen Zyklus, also einen Zyklus, auf dem alle Knoten von $D$ genau einmal vorkommen.

Insbesondere gilt diese Aussage für den Fall, dass an jedem Knoten $v$ hinsichtlich Eingangsgrad und Ausgangsgrad die beiden Ungleichungen

$d_{G}^{-}(v)\geq {\frac {n(D)}{2}}$

und

$d_{G}^{+}(v)\geq {\frac {n(D)}{2}}$

erfüllt sind.

Verschärfung

Der Satz von Ghouila-Houri wurde von mehreren Autoren verschärft; so im Jahre 1973 von M. Meyniel wie folgt:

Ist $D$ ein endlicher stark zusammenhängender gerichteter Graph, der für je zwei verschiedene nicht benachbarte Knoten $v_{1}$ und $v_{2}$ die Ungleichung

${d_{G}}(v_{1})+{d_{G}}(v_{2})\geq 2n(D)-1$.

erfüllt, so besitzt $D$ einen hamiltonschen Zyklus.

Literatur

• Alain Ghouila-Houri: Une condition suffisante d'existence d'un circuit hamiltonien. In: Comptes rendus de l’Académie des sciences Paris. Band 251, 1960, S. 495–497 (MR0114771). 
• Rudolf Halin: Graphentheorie. 2., überarbeitete und erweiterte Auflage. Wissenschaftliche Buchgesellschaft, Darmstadt 1989, ISBN 3-534-10140-5 (MR1068314). 
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• M. Meyniel: Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente. In: Journal of Combinatorial Theory. Series B. Band 14, 1973, S. 137–147 (MR0317997). 
• Robin J. Wilson: Einführung in die Graphentheorie. Aus dem Englischen übersetzt von Gerd Wegner (= Moderne Mathematik in elementarer Darstellung. Band 15). Vandenhoeck & Ruprecht, Göttingen 1976 (MR0434854 – Englische Vorlage: Introduction to Graph Theory, Longman, London 1975). 

Einzelnachweise

rreferences />

KKKategorie:Satz (Graphentheorie)|Ghouila-Houri]] KKKategorie:Satz (Mathematik)|Ghouila-Houri]]

Satz von Berge

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Berge einer von mehreren Sätzen, die auf den französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung größtmöglicher Matchings in endlichen Graphen. In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Ein Matching $M$ in einem endlichen Graphen $G$ ist von maximaler Mächtigkeit (und besteht damit aus genau $\nu (G)$ Kanten) dann und nur dann, wenn es in $G$ keinen $M$-erweiternden Weg gibt.

Erklärungen

• In einem endlichen Graphen $G$ ist ein Matching $M\subseteq E(G)$ von maximaler Mächtigkeit genau dann, wenn in $G$ kein anderes Matching $M^{*}$ existiert mit $|M^{*}|>|M|$. Die Mächtigkeit eines solchen größtmöglichen Matchings nennt man die Matchingzahl von $G$ und bezeichnet sie mit $\nu (G)$.
• Ist ein Weg in $G$ gegeben, so wird $W$ als $M$-alternierend bezeichnet, falls die in $W$ vorkommenden Kanten abwechselnd zu $M$ und zu $E(G)\setminus M$ gehören.
• Inzidieren die durch einen $M$-alternierenden Weg $W$ verbundenen Endknoten mit keiner der in $M$ vorkommenden Kanten, so wird $W$ als $M$-erweiternd (oder als $M$-zunehmend) bezeichnet.

Anmerkungen

• In der englischsprachigen Graphentheorieliteratur spricht man von einem augmenting path. Daher ist der Satz von Berge hier auch als augmenting path theorem bekannt.
• Der Satz tritt auch schon in der Pionierarbeit Die Theorie der regulären Graphs des dänischen Mathematikers Julius Petersen aus dem Jahre 1891 auf.
• Oft wird (so etwa im Bronstein) ein Matching von maximaler Mächtigkeit auch kurz ein maximales Matching genannt, obwohl diese Benennung nicht dem sonst üblichen – von der Ordnungstheorie herrührenden – Maximalitätsbegriff entspricht.

Literatur

• Claude Berge: Two theorems in graph theory. In: Proceedings of the National Academy of Sciences. Band 43, 1957, S. 842–844 (MR0094811). 
• Claude Berge: Graphs and Hypergraphs. Translated [from the French] by Edward Minieka (= North-Holland Mathematical Library. Band 6). North-Holland Publishing Company, Amsterdam, London 1973 (MR0357172). 
• I. N. Bronstein, K. A. Semendjajew, G. Musiol, H. Mühlig (Hrsg.): Taschenbuch der Mathematik. 10., überarbeitete Auflage. Europa-Lehrmittel, Haan-Gruiten 2016, ISBN 978-3-8085-5790-7. 
• John Clark, Derek Allan Holton: Graphentheorie. Grundlagen und Anwendungen. Spektrum Akademischer Verlag, Heidelberg, Berlin, Oxford 1994, ISBN 3-86025-331-X. 
• Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory (= Discrete Mathematics and its Applications). CRC Press, Boca Raton u. a. 2004, ISBN 1-58488-090-2. 
• Dieter Jungnickel: Graphs, Networks and Algorithms. With 209 Figures and 9 Tables (= Algorithms and Computation in Mathematics. Band 5). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2008, ISBN 978-3-540-72779-8 (MR2363884). 
• Julius Petersen: Die Theorie der regulären Graphs. In: Acta Mathematica. Band 15, 1891, S. 193–220 (PDF). 
• Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag, Wien / New York 1996, ISBN 3-211-82774-9 (MR1392955). 

Einzelnachweise

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Berge]] KKKategorie:Satz (Mathematik)|Berge]]

Satz von Babai

Der Satz von Babai ist ein mathematischer Lehrsatz, welcher im Übergangsfeld zwischen den Teilgebieten Graphentheorie und Gruppentheorie angesiedelt ist. Er geht auf eine Veröffentlichung des ungarischen Mathematikers László Babai aus dem Jahre 1974 zurück. Der Satz ist verwandt mit dem Satz von Frucht, denn er behandelt eine spezielle Problemstellung im Zusammenhang mit der Frage der Darstellbarkeit endlicher Gruppen als Automorphismengruppen schlichter Graphen. Er zieht als Folgerung nach sich, dass eine von Pál Turán im Jahre 1969 gestellte Frage, ob nämlich jede endliche Gruppe als Automorphismengruppe eines ebenen Graphen darstellbar ist, verneinend zu beantworten ist.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Sei ${\mathcal {G}}$ eine Klasse schlichter Graphen mit den folgenden beiden Eigenschaften:

(1) ${\mathcal {G}}$ enthält mit einem schlichten Graphen $G\in {\mathcal {G}}$ stets auch jedes graphenhomomorphe Bild eines jeden Minors $G^{*}\preccurlyeq G$ .

(2) Zu jeder endlichen Gruppe $\Gamma$ gebe es in ${\mathcal {G}}$ einen (möglicherweise unendlichen) schlichten Graphen $G_{\Gamma }$, dessen Automorphismengruppe $\mathrm {Aut} (G_{\Gamma })$ gruppenisomorph zu $\Gamma$ ist.

Dann gilt:

Die Graphenklasse ${\mathcal {G}}$ enthält alle endlichen schlichten Graphen.

Quellen und Literatur

• Rudolf Halin: Graphentheorie. 2., überarbeitete und erweiterte Auflage. Wissenschaftliche Buchgesellschaft, Darmstadt 1989, ISBN 3-534-10140-5.  MR1068314
• László Babai: Automorphism groups of graphs and edge-contraction. In: Discrete Mathematics. Band 8, 1974, S. 13–20 ([1]).  MR0332554

Siehe auch

• Satz von Frucht

Einzelnachweise

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Gruppentheorie]] KKKategorie:Satz (Graphentheorie)]] KKKategorie:Satz (Mathematik)]]

Satz von Tutte (Hamiltonkreisproblem)

In der Topologischen Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Tutte zum Hamiltonkreisproblem einer der Lehrsätze des britisch-kanadischen Graphentheoretikers William Thomas Tutte (1917–2002). Tutte publizierte den Satz im Jahre 1956 und verknüpft dabei – an ein Resultat von Hassler Whitney aus dem Jahre 1931 anschließend – das Hamiltonkreisproblem mit der Frage der Plättbarkeit und des mehrfachen Zusammenhangs. Der Satz ist bedeutsam in Bezug auf das Vier-Farben-Problem.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Ist ein endlicher schlichter Graph $G$ plättbar und $4$-fach zusammenhängend, so enthält $G$ einen hamiltonschen Kreis.

Der Satz lässt sich auch so formulieren:

In jedem endlichen schlichten Graphen $G$, der plättbar ist und keinen minimalen Schnitt mit drei oder weniger Knoten enthält, gibt es einen hamiltonschen Kreis.

Der whitneysche Satz

Der von Hassler Whitney 1931 vorgelegte Satz macht die gleiche Aussage wie der tuttesche Satz, tut dies allerdings unter einer zusätzlichen Voraussetzung. Es soll nämlich hier der den Graphen darstellenden Streckengraph zusätzlich der Bedingung genügen, dass jedes Land seiner topologischen Landkarte eine Dreiecksfläche in der euklidischen Ebene ist.

Bezug zum Vier-Farben-Problem

Wie Hansjoachim Walther/Heinz-Jürgen Voß und Øystein Ore ausführen, ist für die topologischen Landkarten der betrachteten Graphen das Vier-Farben-Problem gelöst. Denn ein solcher Graph lässt sich stets derart in die Oberfläche der Einheitskugel einbetten, dass die Knoten des hamiltonschen Kreises sämtlich auf dem Äquators der Kugeloberfläche zu liegen kommen. Davon ausgehend lässt sich durch vollständige Induktion nachweisen, dass sowohl die Länder der Nordhalbkugel der zugehörigen topologischen Landkarte als auch ihre Länder auf der Südhalbkugel stets eine zulässige Färbung mit zwei Farben besitzen, weswegen die gesamte topologische Landkarte eine zulässige Färbung mit vier Farben gestattet.

Quellen und Literatur

• Øystein Ore: The Four-Color Problem. (= Pure and Applied Mathematics. Band 27). Academic Press, New York, London 1967.  MR0216979
• W. T. Tutte: A theorem on planar graphs. In: Transactions of the American Mathematical Society. Band 82, 1956, S. 99–116, doi:10.2307/1992980.  MR0081471
• Hansjoachim Walther, Heinz-Jürgen Voß: Über Kreise in Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin 1974. 
• Hassler Whitney: A theorem on graphs. In: Annals of Mathematics (2). Band 32, 1931, S. 378–390, doi:10.2307/1968197.  MR1503003

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Graphentheorie)]] KKKategorie:Satz (Mathematik)]]

Satz von Battle-Harary-Kodama

Der Satz von Battle-Harary-Kodama ist ein mathematischer Lehrsatz, welcher dem Gebiet der Topologischen Graphentheorie angehört und auf eine Veröffentlichung der drei Mathematiker Joseph Battle, Frank Harary und Yukihiro Kodama aus dem Jahre 1962 zurückgeht. Er behandelt die Frage der Plättbarkeit von endlichen schlichten Graphen und der zugehörigen Komplementärgraphen und beruht auf einer Vermutung von John L. Selfridge. Im Jahre 1963 hat William Tutte einen vereinfachten Beweis des Satzes geliefert.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

(1) Ist ein endlicher schlichter Graph $G=(V,E)$ plättbar und hat er $p\geq 9$ Knoten, so ist sein Komplementärgraph ${\overline {G}}=(V,{\binom {V}{2}}\setminus E)$ nicht plättbar.

(2) Die Zahl $9$ ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Verwandter Satz

Von D. P. Geller wurde ein verwandter Satz vorgelegt, welcher die analoge Frage in Bezug auf die Eigenschaft der kreisartigen Plättkeit behandelt. Hier bezeichnet man einen endlichen schlichten Graphen $G$ als kreisartig plättbar, wenn $G$ eine ebene Darstellung in Form eines Streckengraphen $G^{'}$ besitzt, dessen Knoten sämtlich Randpunkte eines einzigen Landes der zugehörigen topologischen Landkarte sind.

Der Satz von Geller lässt sich dann so formulieren:

(1) Ist ein endlicher schlichter Graph $G$ kreisartig plättbar und hat er $p\geq 7$ Knoten, so ist sein Komplementärgraph ${\overline {G}}$ nicht kreisartig plättbar.

(2) Die Zahl $7$ ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Quellen und Literatur

• Joseph Battle, Frank Harary, Yukihiro Kodama: Every planar graph with nine points has a nonplanar complement. In: Bull. Amer. Math. Soc. (N.S.). Band 68, 1962, S. 569–571 ([2]).  MR0155314
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• W. T. Tutte: The non-biplanar character of the complete 9-graph. In: Canadian Mathematical Bulletin. Band 6, 1963, S. 319–319 ([3]).  MR0159318

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Battle-Harary-Kodama, Satz von]] KKKategorie:Satz (Mathematik)|Battle-Harary-Kodama, Satz von]]

Satz von Steinitz

Der Satz von Steinitz, englisch Steinitz's theorem, ist ein mathematischer Lehrsatz, welcher sowohl dem Gebiet der Topologischen Graphentheorie als auch dem der Geometrischen Graphentheorie zuzurechnen ist. Der Satz geht zurück auf eine Veröffentlichung des Mathematikers Ernst Steinitz (1871–1928) aus dem Jahre 1916 und zählt zusammen mit dem eulerschen Polyedersatz, dem Satz von Kuratowski und dem Satz von Wagner zu den klassischen Ergebnissen der Graphentheorie über plättbare Graphen.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Ein endlicher schlichter Graph $G$ hat dann und nur dann eine geradlinige Darstellung als $3$-dimensionaler Polyedergraph $G^{'}\subset \mathbb {R} ^{3}$, wenn $G$ plättbar und zugleich $3$-fach zusammenhängend ist.

Bedeutung des Satzes

Der steinitzsche Satz ist einer der grundlegenden Sätze in der Lehre von den Polyedern und offenbar schätzte auch Ernst Steinitz dies selbst so ein. Wie Branko Grünbaum hierzu in seinem 1975er Artikel Polytopal Graphs hervorhebt, bezeichnete Steinitz seinen Satz daher sogar als Fundamentalsatz der konvexen Typen [von Polyedern] (englisch Fundamental Theorem of Convex Types [of Polyhedra]) und präsentierte dazu nicht weniger als drei sorgfältig ausgearbeitet Beweise. Diese sind in der klassischen Monographie Vorlesungen über die Theorie der Polyeder von Steinitz und Rademacher dargestellt. Wie Grünbaum weiter schreibt, bedient sich diese Darstellung jedoch nicht der modernen Begriffe der Graphentheorie - wie den des Zusammenhangs oder den der Plättbarkeit - sondern eigener Begrifflichkeiten, wodurch Steinitz' Beweisführung (aus heutiger Sicht) recht schwerfällig (englisch rather cumbersome) sei.

Verwandter Satz

Ein verwandter Satz, welcher die Polytope aller höheren Dimensionen betrifft und von dem Mathematiker Michel Louis Balinski gefunden wurde, ist der folgende:

Hat ein endlicher schlichter Graph eine geradlinige Darstellung als $d$-dimensionaler Polytopgraph im $\mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 2)$ , so ist er notwendigerweise $d$-fach zusammenhängend.

Quellen und Literatur

• M. L. Balinski: On the graph structure of convex polyhedra in n-space. In: Pacific Journal of Mathematics. Band 11, 1961, S. 431–434 ([4]).  MR0126765
• Lowell W. Beineke, Robin J. Wilson (Hrsg.): Topics in Topological Graph Theory (= Encyclopedia of Mathematics and its Applications. Band 128). Cambridge University Press, Cambridge 2009, ISBN 978-0-521-80230-7.  MR2581536
• Branko Grünbaum: Polytopal Graphs in: Studies in Graph Theory. Part II (Hrsg. D. R. Fulkerson) (= Studies in Mathematics. Band 12). Mathematical Association of America, Washington, DC 1975, ISBN 0-88385-112-1, S. 201–224.  MR0406868 MR0392630
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• E. Steinitz, H. Rademacher: Vorlesungen über die Theorie der Polyeder (Reprint 1976 ). Unter Einschluß der Elemente der Topologie (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Band 41). Springer Verlag, Berlin, Heidelberg, New York 1976, ISBN 3-540-06293-9.  MR0430958

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Topologische Graphentheorie]] KKKategorie:Geometrische Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Steinitz, Satz von]] KKKategorie:Satz (Mathematik)|Steinitz, Satz von]]

Satz von Schnyder (unfertig)

Der Satz von Schnyder ist ein mathematischer Lehrsatz, welcher an der Nahtstelle zwischen Graphentheorie als auch der Ordnungstheorie liegt. Er geht zurück auf den niederländischen Mathematiker Walter Schnyder, der ihn im Jahre 1989 publizierte. Der Satz behandelt die Frage der Plättbarkeit endlicher schlichter Graphen aus ordnungstheoretischer Sicht und formuliert hierzu ein elegantes Kriterium.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Ein endlicher schlichter Graph $G$ ist plättbar dann und nur dann, wenn für die Ordnungsdimension der zugehörigen Inzidenzordnung ${\mathcal {P}}(G)$ die Ungleichung ${\mathcal {odim}}({\mathcal {P}}(G))\leq 3$ gilt.

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Schnyder, Satz von]] KKKategorie:Satz (Mathematik)|Schnyder, Satz von]]

Satz von Richardson

Der Satz von Richardson ist ein Lehrsatz der Graphentheorie, einem der Teilgebiete der Mathematik. Der Satz wurde von dem Mathematiker Moses Richardson im Jahre 1953 publiziert. Er behandelt die Frage der Existenz von Kernen in endlichen gerichteten Graphen.

Formulierung des Satzes

Er lässt sich zusammengefasst angeben wie folgt:

Jeder endliche gerichtete Graphen ohne Kreise ungerader Länge besitzt mindestens einen Kern.

Literatur

• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2005, ISBN 3-540-26182-6.  MR2159259
• Jørgen Bang-Jensen, Gregory Z. Gutin: Digraphs. Theory, Algorithms and Applications (= Springer Monographs in Mathematics). 2. Auflage. Springer Verlag, London, Dordrecht, Heidelberg, New York 2010, ISBN 978-1-84800-997-4, doi:10.1007/78-1-84800-998-1.  MR2472389
• Moses Richardson: Solutions of irreflexive relations. In: Annals of Mathematics (2). Band 58, 1953, S. 573–590.  MR0075184
• Gunther Schmidt, Thomas Ströhlein: Relationen und Graphen (= Mathematik für Informatiker). Springer Verlag, Berlin (u. a.) 1989, ISBN 3-540-50304-8.  MR1011038

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Mathematik)|Richardson, Satz von]] KKKategorie:Satz (Graphentheorie)|Richardson, Satz von]]

Topologische Graphentheorie

Topologische Landkarte ist ein Terminus aus dem mathematischen Teilgebiet der Topologischen Graphentheorie. Der Terminus hat Bedeutung insbesondere im Zusammenhang mit Untersuchungen zu Färbungsproblemen und hier nicht zuletzt im Zusammenhang mit dem Vier-Farben-Satz und verwandten mathematischen Lehrsätzen.

Definitionen und Bezeichnungen

• Eine topologische Landkarte ${\mathfrak {K}}$ auf einer Fläche $F\subset \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 2)$ ist ein Tripel ${\mathfrak {K}}=({\mathfrak {L}},{\mathfrak {G}},E)$, wobei ${\mathfrak {L}}$ und ${\mathfrak {G}}$ zwei endliche Mengensysteme von Teilmengen von $F$ sind und $E\subset F$ ebenfalls eine endliche Menge darstellt.
  • Dabei ist ${\mathfrak {G}}$ die Kantenmenge eines topologischen Graphen in $F$ und $E$ ist die zugehörige Knotenmenge.
  • $E$ besteht genau aus denjenigen Punkten von $F$, welche für eine der Jordankurven $g\in {\mathfrak {G}}$ als Anfangs- oder Endpunkt auftreten.
  • Das Mengensystem ${\mathfrak {L}}$ besteht genau aus den Wegzusammenhangskomponenten der Komplementmenge $F\setminus \bigcup {\mathfrak {G}}$.
• Man bezeichnet hierbei jedes Element von ${\mathfrak {L}}$ als Land, jedes Element von ${\mathfrak {G}}$ als Grenzlinie und jedes Element von $E$ als Ecke der topologischen Landkarte ${\mathfrak {K}}$.
• Ein Punkt $x\in \mathbb {R} ^{d}$ ist Randpunkt eines zu der Landkarte gehörenden Landes $L$, wenn er dem relativen topologischen Abschluss ${\overline {L}}\cap F$ von $L$ in $F$ angehört.
• Zwei Länder $L_{1}$ und $L_{2}$ von ${\mathfrak {K}}$ heißen benachbart oder Nachbarländer, wenn unter den Grenzlinien von ${\mathfrak {K}}$ eine vorkommt, welcher ganz aus Randpunkten sowohl von $L_{1}$ als auch von $L_{2}$ besteht.
• Eine zu einer ganzen Zahl $n>0$ gegebene Abbildung $f\colon \,{\mathfrak {L}}\to \{1,\ldots ,n\}$ nennt man $n$-Färbung.
  • Die Elemente von $\{1,\ldots ,n\}$ bezeichnet man (in Einklang mit den Gepflogenheiten der Graphentheorie) als Farben.
  • Eine $n$-Färbung $f\colon \,{\mathfrak {L}}\to \{1,\ldots ,n\}$ heißt zulässig, wenn je zwei benachbarten Ländern vermöge $f$ stets zwei verschiedene Farben zugeordnet sind.
  • Gestattet eine topologischen Landkarte ${\mathfrak {K}}$ auf $F$ für eine ganze Zahl $n>0$ eine zulässige $n$-Färbung, jedoch keine zulässige Färbung mit weniger als $n$ Farben, so nennt man diese ganze Zahl $n$ die chromatische Zahl von ${\mathfrak {K}}$ und bezeichnet sie mit $\chi ({\mathfrak {K}})$.
  • Bildet man über alle topologischen Landkarten auf $F$ das Supremum   $\sup\{\chi ({\mathfrak {K}}):{\mathfrak {K}}\;{\text{topologische Landkarte auf F}}\}$   aller zugehörigen chromatischen Zahlen und ist diese ganze Zahl $<\infty$, so ist dies die chromatische Zahl von $F$. Sie wird mit $\chi (F)$ bezeichnet.

Anmerkung

• Die untersuchten Flächen sind in aller Regel Flächen $F\subset \mathbb {R} ^{d}\;(d=2,3,4)$ .

Bedeutende Lehrsätze

• Satz von Weiske: Ist $F$ der $\mathbb {R} ^{2}$ oder die Einheitssphäre $S^{2}$, so gibt es keine Landkarte mit fünf paarweise benachbarten Ländern.
• Zweifarbensatz: Ist $F$ ein Rechteck und sind darüber hinaus die Grenzlinien einer gegebenen topologischen Landkarte ${\mathfrak {K}}$ so beschaffen, dass jede von ihnen nur zwischen Randpunkten des Rechtecks verläuft oder eine innerhalb des Rechtecks verlaufene geschlossene Jordankurve darstellt, so existiert zu einer solchen topologischen Landkarte ${\mathfrak {K}}$ stets eine zulässige $2$-Färbung.
• Vier-Farben-Satz: Ist $F$ der $\mathbb {R} ^{2}$ oder die Einheitssphäre $S^{2}$, so existiert zu jeder topologischen Landkarte auf $F$ eine zulässige $4$-Färbung.
• Fünf-Farben-Satz: Ist $M$ der $\mathbb {R} ^{2}$ oder die Einheitssphäre $S^{2}$, so existiert zu jeder topologischen Landkarte auf $F$ eine zulässige $5$-Färbung.
• Sechsfarbensatz für das Möbiusband: Das Möbiusband $M$ hat die chromatische Zahl ${\chi }(M)=6$ und es besitzt auf ihm jede topologische Landkarte eine zulässige $6$-Färbung, wobei es unter diesen auch mindestens eine gibt, die nicht mit fünf Farben auskommt.
• Heawoodsche Ungleichung: Ist für eine ganze Zahl $p>0$   $H_{p}$ eine geschlossene orientierbare Fläche vom Geschlecht $p$ und ist dabei $m_{p}=\lfloor {\frac {7+{\sqrt {1+48p}}}{2}}\rfloor$, so existiert zu jeder topologischen Landkarte auf $H_{p}$ eine zulässige $m_{p}$-Färbung. Mit anderen Worten: Für jede derartige Fläche $H_{p}$ erfüllt die chromatische Zahl ${\chi }(H_{p})$ die Ungleichung ${\chi }(H_{p})\leq m_{p}$.
  • Es gilt sogar für ein solches $H_{p}$ stets die Identitätsgleichung ${\chi }(H_{p})=m_{p}$.
  • Insbesondere hat der Volltorus $H_{1}$ die chromatische Zahl ${\chi }(H_{1})=7$ und es besitzt auf ihm jede topologische Landkarte eine zulässige $7$-Färbung, wobei unter diesen auch solche vorkommen, die nicht mit sechs Farben auskommen.

Anmerkungen zu den Lehrsätzen

• Der Satz von Weiske geht auf den Philologen Benjamin Gotthold Weiske (1783–1836), einen Freund des Mathematikers August Ferdinand Möbius, zurück. Die Urheberschaft für dieses Resultat wurde von dem Geometer Richard Baltzer bei Durchsicht des Nachlasses von Möbius herausgefunden. Als Baltzer über den Satz von Weiske und seine Geschichte in einem Vortrag im Jahre 1885 berichtete, setzte er dann jedoch den Irrtum in die Welt, dass sich mit Weiskes Satz bereits der Vierfarbensatz als leichte Folgerung ergibt. Richtig ist dagegen, dass im Gegensatz zu der Darstellung von Baltzer Weiskes Satz allein eine leichte Herleitung des Fünffarbensatzes ermöglicht. Der Irrtum von Baltzer wurde erst im Jahre 1959 von dem Geometer Harold Scott MacDonald Coxeter abschließend beseitigt.
• Der Vierfarbensatz wird heute zwar von vielen, jedoch keineswegs von allen Mathematikern als bewiesen angesehen. So äußerte etwa der Graphentheoretiker Horst Sachs im Jahre 1989 Bedenken gegen diese Auffassung und explizit die Meinung, dass die endgültige Lösung des Vierfarbenproblems noch aussteht.
• Dass in der heawoodschen Ungleichung sogar das Gleichheitszeichen zu gelten hat, wurde schon von Percy John Heawood vermutet und konnte dann im Jahre 1968 von den beiden Mathematikern Gerhard Ringel und John William Theodore Youngs abschließend bewiesen werden.

Das Fadenproblem

Das Fadenproblem besteht in der Frage nach der Lösung folgender Aufgabe:

Es soll - wenn möglich - für eine gegebene natürliche Zahl $m\geq 3$ diejenige kleinste natürliche Zahl $\gamma (m)$ bestimmt werden, für welche auf einer geschlossenen orientierbaren Fläche $H_{\gamma (m)}$ des Geschlechtes $\gamma (m)$ beliebig ausgewählte unterschiedliche Punkte $p_{1},p_{2},\ldots ,p_{\gamma (m)}\in H_{\gamma (m)}$ immer paarweise durch einfache Jordankurven in der Weise verbunden werden können, dass all diese Jordankurven einander nie überkreuzen und höchstens in den ausgewählten Punkten $p_{1},p_{2},\ldots ,p_{\gamma (m)}$ treffen.

Wie sich zeigt, ist das Fadenproblem lösbar und dabei ergibt sich die Formel

$\gamma (m)=\lceil {\frac {(m-3)(m-4)}{12}}\rceil \;(m\in \mathbb {N} \;,\;m\geq 3)$.

Dabei zeigt sich weiter, dass die Gültigkeit dieser Formel auch die Gültigkeit der heawoodschen Identitätsgleichung ${\chi }(H_{p})=m_{p}\;(p\in \mathbb {N} \;,\;p>0)$ nach sich zieht.

Literatur

• Rudolf Fritsch: Der Vierfarbensatz. Geschichte, topologische Grundlagen und Beweisidee. Unter Mitarbeit von Gerda Fritsch. BI Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich 1994, ISBN 3-411-15141-2.  MR1270673
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1. 
• K. P. Müller, H. Wölpert: Anschauliche Topologie. Eine Einführung in die elementare Topologie und Graphentheorie (= Mathematik für die Lehrerausbildung). B. G. Teubner Verlag, Stuttgart 1976, ISBN 3-519-02709-7. 
• Gerhard Ringel: Das Kartenfärbungsproblem. In: Selecta Mathematica III (Hrsg. Konrad Jacobs) (= Heidelberger Taschenbücher. Band 86). Springer Verlag, Berlin, Heidelberg, New York 1971, ISBN 3-540-05333-6.  MR0504534
• Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag, Wien, New York 1996, ISBN 3-211-82774-9.  MR1392955
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4. 

Einzelnachweise

KKKategorie:Topologische Graphentheorie]]

Satz von van der Waerden (Zerlegung endlicher Mengen)

Der Satz von van der Waerden über die Zerlegung endlicher Mengen ist ein mathematischer Lehrsatz, welcher sowohl der Mengenlehre als auch der Graphentheorie zugerechnet werden kann. Er geht zurück auf den niederländischen Mathematiker Bartel Leendert van der Waerden, der ihn im Jahre 1927 publizierte. Der Satz behandelt Zerlegungen endlicher Mengen und ist engstens verwandt mit einem graphentheoretischen Satz des ungarischen Mathematikers Dénes Kőnig über reguläre bipartite Graphen aus dem Jahr 1914.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Gegeben seien zwei natürliche Zahlen $n,k\in \mathbb {N}$ und dazu eine endliche Grundmenge $X$ mit $n\cdot k$ Elementen.

Weiter gegeben seien zwei Zerlegungen ${\mathcal {A}}=(A_{1},\ldots ,A_{n})$ und ${\mathcal {B}}=(B_{1},\ldots ,B_{n})$ von $X$ in Klassen gleicher Größe; also dergestalt, dass stets die Gleichungen $|A_{i}|=k=|B_{j}|\;(i,j=1,\ldots ,n)$ erfüllt sind.

Dann gilt:

Unter diesen Gegebenheiten besitzen ${\mathcal {A}}$ und ${\mathcal {B}}$ immer ein gemeinsames Vertretersystem; also ein Vertretersystem derart, dass jede ${\mathcal {A}}$-Klasse und jede ${\mathcal {B}}$-Klasse von genau einem dieser Vertreter repräsentiert wird .

Folgerung: Der Satz von Miller

B. L. van der Waerden hat seinen Satz als direkte Verallgemeinerung eines gruppentheoretischen Satzes des US-amerikanischen Mathematikers George Abram Miller gefunden und formuliert. Der millersche Satz ergibt sich, wenn man den van der Waerden'schen Satz auf die Rechts- und Linksnebenklassen der Untergruppen endlicher Gruppen anwendet. Zusammenhängend formuliert besagt der Satz von Miller also:

In einer endlichen Gruppe gibt es für die Rechts- und Linksnebenklassen einer jeden Untergruppe stets ein gemeinsames Vertretersystem.

Zusammenhang mit bipartiten Graphen: Ein Satz von Kőnig in drei Versionen

I

Wie Dénes Kőnig in seiner Monographie Theorie der endlichen und unendlichen Graphen darlegt und auch B. L. van der Waerden in seiner 1927er Arbeit anmerkt, ist der van der Waerden'sche Satz gleichwertig mit einem frühen graphentheoretischen Satz von Dénes Kőnig, der sich (in moderner Formulierung) folgendermaßen angeben lässt:

Ein endlicher regulärer bipartiter Graph besitzt stets einen $1$-Faktor.

II

Über den obigen Satz hat Kőnig zum ersten Mal in 1914 auf dem Pariser Kongress für mathematische Philosophie vorgetragen und dabei zugleich auf die Gleichwertigkeit mit dem folgenden Satz hingewiesen:

Jeder endliche $m$-reguläre bipartite Graph ($m\in \mathbb {N}$) zerfällt in $m$   $1$-Faktoren.

III

Wie Kőnig weiter zeigt, sind die beiden zuletzt zitierten Sätze ihrerseits gleichwertig mit einem von ihm im Jahre 1916 publizierten Satz, der sich formulieren lässt wie folgt:

Laufen in jedem Knoten eines endlichen bipartiten Graphen höchstens $m$ Kanten zusammen, so kann man die Kantenmenge so in $m$ Klassen zerlegen, dass je zwei benachbarte Kanten stets verschiedenen Klassen angehören.

Mit anderen Worten:

Ist der Maximalgrad eines endlichen bipartiten Graphen gleich $m$, so ist er $m$-kantenfärbbar.

Dies bedeutet jedoch nichts weiter als das folgende Resultat:

Für einen endlichen bipartiten Graphen sind Kantenfärbungszahl und Maximalgrad stets identisch, also:

$\chi ^{\prime }(G)=\Delta (G)$  .

Siehe auch

• Satz von Vizing

Quellen und Literatur

Originalarbeiten

• Dénes König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. In: Mathematische Annalen. Band 77, 1916, S. 453–465 ([5]).  MR1511872
• Bartel L. van der Waerden: Ein Satz über Klasseneinteilungen von endlichen Mengen. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. Band 5, 1927, S. 185–188 ([6]).  MR3069474
• G. A. Miller: On a method due to Galois. In: Quarterly Journal of Mathematics. Band 41, 1910, S. 382–384. 

Monographien

• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2005, ISBN 3-540-26182-6.  MR2159259
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• Dénes König: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Hrsg.: H. Sachs (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4. 

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Mengenlehre]] KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|van der Waerden, Satz von]] KKKategorie:Satz (Mathematik)|van der Waerden, Satz von]]

Satz von Rédei (Graphentheorie)

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Rédei ein Lehrsatz, der grundlegend für die Frage der Durchlaufbarkeit von Turniergraphen ist. Der Satz geht zurück auf eine Arbeit des ungarischen Mathematikers László Rédei aus dem Jahre 1934.

Formulierung des Satzes

Der rédeische Satz lässt sich zusammengefasst angeben wie folgt:

In einem endlichen Turnier mit mindestens zwei Knoten ist die Anzahl der darin vorkommenden hamiltonschen Bahnen stets eine ungerade Zahl.

Demnach gibt es in jedem endlichen Turnier mindestens eine Bahn, die jeden Knoten genau einmal enthält.

Anmerkungen zum Beweis

• Der zweite Teil des obigen Satzes von Rédei lässt sich leicht mittels vollständiger Induktion beweisen.
• Horst Sachs zufolge ist für den Satz insgesamt kein einfacher Beweis bekannt. Von dem ungarischen Mathematiker Tibor Szele wurde im Jahre 1943 ein (gemäß Sachs) sehr schöner kombinatorischer Beweis geliefert.

Quellen und Literatur

• Rudolf Halin: Graphentheorie. I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• Dénes König: Theorie der endlichen und unendlichen Graphen. Mit einer Abhandlung von L. Euler. Hrsg.: H. Sachs (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4. 
• L. Rédei: Ein kombinatorischer Satz. In: [[Universität der Wissenschaften Szeged#Acta Universitatis Szegediensis

  |Band=7
  |Datum=1934
  |Seiten=39–43
  |Online=[7]
  |1=Acta Scientiarum Mathematicarum [früher: Acta Litterarum ac Scientiarum (Sectio Scientiarum Mathematicarum), Szeged]]]. 

• Horst Sachs: Einführung in die Theorie der endlichen Graphen. Carl Hanser Verlag, München 1971, ISBN 3-446-11463-7.  MR0345857
• T. Szele: Kombinatorische Untersuchungen über gerichtete vollständige Graphen. In: Publicationes Mathematicae Debrecen. Band 13, 1966, S. 145–168 ([8]).  MR0207591

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Rédei, Satz von]] KKKategorie:Satz (Mathematik)|Satz von Rédei (Graphentheorie)]]

Satz von Kruskal

Der Satz von Kruskal ist ein Lehrsatz der Graphentheorie, einem der Teilgebiete der Mathematik. Er wurde von dem Mathematiker Joseph Bernard Kruskal im Jahre 1960 publiziert. Der Satz behandelt eine wichtige Eigenschaft der Klasse der endlichen Bäume.

Formulierung des Satzes

Der Satz lautet wie folgt:

Die Klasse der endlichen Bäume ist durch die Quasiordnungsrelation der Bildung des topologischen Minors wohlquasigeordnet.

Verwandte Sätze

Der Satz von Kruskal wurde in den 1960-er Jahren von Crispin St. J. A. Nash-Williams auf unendliche Bäume verallgemeinert. Einen vereinfachten Beweis beider Sätze legte Daniela Kühn im Jahre 2001 vor. Der kruskalsche Satz ist eingebunden in den Problemkreis um das bedeutende Minorentheorem.

Literatur

Originalarbeiten

• J. B. Kruskal: Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture. In: Transactions of the American Mathematical Society. Band 95, 1960, S. 210–225 ([9]).  MR0111704
• Daniela Kühn: On well-quasi-ordering infinite trees—Nash-Williams's theorem revisited. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 130, 2001, S. 401–408.  MR1816801
• C. St. J. A. Nash–Williams: On well-quasi-ordering infinite trees. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 61, 1965, S. 697–720.  MR0175814
• C. St. J. A. Nash–Williams: On better-quasi-ordering transfinite sequences. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 64, 1968, S. 273–290.  MR0221949

Monographien

• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2005, ISBN 3-540-26182-6.  MR2159259
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8.  MR2127991
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4.  MR0282850

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Mathematik)|Kruskal, Satz von]]

Äquivalenzsatz von Wagner

Der Äquivalenzsatz von Wagner, auch als Äquivalenzsatz von K. Wagner oder als wagnerscher Äquivalenzsatz bezeichnet, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Er stellt eine Verbindung zwischen der Hadwiger-Vermutung und dem Vierfarbenproblem her.

Formulierung des Satzes

Der Satz lässt sich angeben wie folgt:

Die Vierfarbenvermutung ist mit der Hadwiger-Vermutung $(H_{5})$ äquivalent.

Anmerkung zu Einordnung des Resultats

Dem Graphentheoretiker Rudolf Halin zufolge ist der Äquivalenzsatz ein überraschendes Resultat. Er sei der früheste Versuch, das Vierfarbenproblem zu „enttopologisieren“. Es werde in der Tat ... bei der Fomulierung von $(H_{5})$ keinerlei Bezug auf eine ebene Darstellung genommen. ... Es [das Vierfarbenproblem] hat auch den Anstoß dazu gegeben, die allgemeine Vermutung $(H_{n})$ auszusprechen und näher zu untersuchen.

Siehe auch

• Satz von Wagner
• Satz von Wagner und Fáry

Literatur

• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2005, ISBN 3-540-26182-6.  MR2159259
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• Klaus Wagner: Über eine Eigenschaft der ebenen Komplexe. In: Mathematische Annalen. Band 114, 1937, S. 570–590 ([10]). MR1513158
• Klaus Wagner: Bemerkungen zu Hadwigers Vermutung. In: Mathematische Annalen. Band 141, 1960, S. 433–451 ([11]). MR0121309
• Klaus Wagner: Beweis einer Abschwächung der Hadwiger-Vermutung. In: Mathematische Annalen. Band 153, 1964, S. 139–141 ([12]). MR0121309
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4. 

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Mathematik)|Wagner, Äquivalenzsatz von]]

Satz von Nordhaus-Gaddum

Der Satz von Nordhaus-Gaddum ist ein Lehrsatz aus dem mathematischen Teilgebiet der Graphentheorie, welcher auf eine Arbeit der beiden Mathematiker Edward Alfred Nordhaus und Jerry W. Gaddum aus dem Jahre 1956 zurückgeht. Der Satz formuliert vier grundlegende Ungleichungen über den Zusammenhang zwischen der chromatischen Zahl eines Graphen, der chromatischen Zahl des zugehörigen Komplementärgraphen und der Knotenzahl. Der Satz war Anstoß für eine Anzahl von Folgearbeiten.

Formulierung des Satzes

Der Satz lautet wie folgt:

Für einen endlichen schlichten Graphen $G=(V,E)$ mit $p=|V|$ Knoten und seinen Komplementärgraphen ${\overline {G}}=(V,{\binom {V}{2}}\setminus E)$ gelten stets folgende Ungleichungen:

$2\cdot {\sqrt {p}}\leq \chi (G)+\chi ({\overline {G}})\leq p+1$

$p\leq \chi (G)\cdot \chi ({\overline {G}})\leq {\frac {(p+1)^{2}}{4}}$

Literatur

• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• Rudolf Halin: Graphentheorie. I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• E. A. Nordhaus, J. W. Gaddum: On complementary graphs. In: Amer. Math. Monthly. Band 63, 1956, S. 175–177, doi:10.2307/2306659.  MR0078685
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4.  MR0282850

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Mathematik)|Nordhaus-Gaddum, Satz von]]

Satz von Wagner

Der Satz von Wagner ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Der Satz ist verwandt mit dem Satz von Kuratowski und gibt wie dieser eine Charakterisierung plättbarer Graphen.

Formulierung des Satzes

Abb. 1: Der Kuratowski-Graph $K_{5}$

Abb. 2: Der Kuratowski-Graph $K_{3,3}$

Der Satz lautet wie folgt:

Ein endlicher schlichter Graph $G=(V,E)$ ist plättbar genau dann, wenn in ihm kein Teilgraph enthalten ist, der zu einem der beiden Kuratowski-Graphen $K_{5}$ und $K_{3,3}$ kontrahierbar ist.

Anwendung

Mit dem Satz von Wagner lässt sich zeigen, dass der Petersen-Graph nicht plättbar ist.

Folgerung

Die beiden Sätze von Kuratowski und Wagner führen zusammengenommen zu folgendem Resultat:

Für einen endlichen schlichten Graphen $G=(V,E)$ sind gleichwertig:

 $(I)$   : $G$ ist plättbar.

 $(II)$   : In $G$ ist keiner der beiden Kuratowski-Graphen als Minor enthalten.

 $(III)$   : In $G$ ist keiner der beiden Kuratowski-Graphen als topologischer Minor enthalten.

Siehe auch

• Satz von Wagner und Fáry
• Äquivalenzsatz von Wagner

Literatur

• Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2005, ISBN 3-540-26182-6.  MR2159259
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3.  MR0586234
• Dieter Jungnickel: Graphs, Networks and Algorithms. With 209 Figures and 9 Tables (= Algorithms and Computation in Mathematics. Band 5). 3. Auflage. Springer Verlag, Berlin, Heidelberg, New York 2008, ISBN 978-3-540-72779-8.  MR2363884
• Klaus Wagner: Über eine Eigenschaft der ebenen Komplexe. In: Mathematische Annalen. Band 114, 1937, S. 570–590 ([13]). MR1513158
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4. 

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Mathematik)|Wagner, Satz von]]

Satz von Wagner und Fáry

Der Satz von Wagner und Fáry, manchmal auch als Satz von Wagner oder Satz von Fáry bezeichnet, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher zuerst im Jahre 1936 von dem Mathematiker Klaus Wagner gefunden und dann im Jahre 1948 von dem Mathematiker István Fáry erneut gefunden wurde. Der Satz behandelt eine wichtige Eigenschaft plättbarer Graphen, die nicht zuletzt im Zusammenhang mit dem Vierfarbensatz und verwandten mathematischen Lehrsätzen von Bedeutung ist.

Formulierung des Satzes

Nach einem geeigneten Homoöomorphismus sind auch B und D durch eine Strecke verbunden.

Erste Version

Die erste Version des Satzes lautet wie folgt:

Ist ein endlicher schlichter Graph $G=(V,E)$ plättbar, so existiert sogar ein isomorpher ebener Graph $G'=(V',E')$ dergestalt, dass die zu den Kanten $e'\in E'$ gehörigen Jordankurven sämtlich abgeschlossene Strecken sind, die einander nie in einem inneren Punkt kreuzen, also paarweise stets höchstens einen der Knoten $v'\in V'$ gemeinsam haben.

Zweite Version

Ein ebener Graphen $G'=(V',E')$ der in der ersten Version genannten Art wird auch als Streckengraph oder als geradlinige Darstellung (des Graphen $G$) bezeichnet. Unter Verwendung dieser Begriffe lässt sich der Satz auch folgendermaßen fomulieren:

Jeder ebene Graph kann durch einen Homöomorphismus der euklidischen Ebene auf sich in einen Streckengraphen, also in eine geradlinige Darstellung, überführt werden.

Anmerkungen

• Die Bedeutung des Satzes von Wagner und Fáry (in der zweiten Version) für den Vierfarbensatz geht aus einer Anmerkung hervor, die der Mathematiker Rudolf Fritsch in seiner Monographie Der Vierfarbensatz dazu macht. Fritsch schreibt, dass der Satz die endgültige Befreiung aus dem Gruselkabinett beliebiger Jordankurven bringt und den Vierfarbensatz aus den Klauen der allgemeinen Topologie löst.
• Die Vermutung, dass die Aussage des Satzes von Wagner und Fáry gelte, wurde István Fáry zufolge schon früher von dem ungarischen Mathematiker Tibor Szele geäußert.

Siehe auch

• Äquivalenzsatz von Wagner
• Satz von Wagner

Literatur

• István Fáry: On straight line representation of planar graphs. In: Acta Univ. Szeged. Sect. Sci. Math. Band 11, 1948, S. 229–233 (MR0026311). 
• Rudolf Fritsch: Der Vierfarbensatz. Geschichte, topologische Grundlagen und Beweisidee. Unter Mitarbeit von Gerda Fritsch. BI Wissenschaftsverlag, Mannheim / Leipzig / Wien / Zürich 1994, ISBN 3-411-15141-2 (MR1270673). 
• Rudolf Halin: Graphentheorie II (= Erträge der Forschung. Band 161). Wissenschaftliche Buchgesellschaft, Darmstadt 1981, ISBN 3-534-08269-9 (MR0668698). 
• Nora Hartsfield, Gerhard Ringel: Pearls in Graph Theory. A Comprehensive Introduction. Academic Press, Boston (u. a.) 1990, ISBN 0-12-328552-6 (MR1069559). 
• Jonathan L. Gross, Thomas W. Tucker: Topological Graph Theory (= Wiley-Interscience Series in Discrete Mathematics and Optimization). John Wiley & Sons, New York 1987, ISBN 0-471-04926-3 (MR0898434). 
• Klaus Wagner: Bemerkungen zum Vierfarbenproblem. In: Jahresbericht der Deutschen Mathematiker-Vereinigung. Band 46, 1936, S. 26–32. 
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4 (MR0282850). 

Einzelnachweise und Fußnoten

Kreferences />

KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Mathematik)|Wagner und Fáry, Satz von]]

Topologische Landkarte

Topologische Landkarte ist ein Terminus aus dem mathematischen Teilgebiet der Topologischen Graphentheorie. Der Terminus hat Bedeutung insbesondere im Zusammenhang mit Untersuchungen zu Färbungsproblemen und hier nicht zuletzt im Zusammenhang mit dem Vier-Farben-Satz und verwandten mathematischen Lehrsätzen.

Definitionen und Bezeichnungen

• Eine topologische Landkarte ${\mathfrak {K}}$ auf einer Fläche $F\subset \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 2)$ ist ein Tripel ${\mathfrak {K}}=({\mathfrak {L}},{\mathfrak {G}},E)$, wobei ${\mathfrak {L}}$ und ${\mathfrak {G}}$ zwei endliche Mengensysteme von Teilmengen von $F$ sind und $E\subset F$ ebenfalls eine endliche Menge darstellt.
  • Dabei ist ${\mathfrak {G}}$ die Kantenmenge eines topologischen Graphen in $F$ und $E$ ist die zugehörige Knotenmenge.
  • $E$ besteht genau aus denjenigen Punkten von $F$, welche für eine der Jordankurven $g\in {\mathfrak {G}}$ als Anfangs- oder Endpunkt auftreten.
  • Das Mengensystem ${\mathfrak {L}}$ besteht genau aus den Wegzusammenhangskomponenten der Komplementmenge $F\setminus \bigcup {\mathfrak {G}}$.
• Man bezeichnet hierbei jedes Element von ${\mathfrak {L}}$ als Land, jedes Element von ${\mathfrak {G}}$ als Grenzlinie und jedes Element von $E$ als Ecke der topologischen Landkarte ${\mathfrak {K}}$.
• Ein Punkt $x\in \mathbb {R} ^{d}$ ist Randpunkt eines zu der Landkarte gehörenden Landes $L$, wenn er dem relativen topologischen Abschluss ${\overline {L}}\cap F$ von $L$ in $F$ angehört.
• Zwei Länder $L_{1}$ und $L_{2}$ von ${\mathfrak {K}}$ heißen benachbart oder Nachbarländer, wenn unter den Grenzlinien von ${\mathfrak {K}}$ eine vorkommt, welcher ganz aus Randpunkten sowohl von $L_{1}$ als auch von $L_{2}$ besteht.
• Eine zu einer ganzen Zahl $n>0$ gegebene Abbildung $f\colon \,{\mathfrak {L}}\to \{1,\ldots ,n\}$ nennt man $n$-Färbung.
  • Die Elemente von $\{1,\ldots ,n\}$ bezeichnet man (in Einklang mit den Gepflogenheiten der Graphentheorie) als Farben.
  • Eine $n$-Färbung $f\colon \,{\mathfrak {L}}\to \{1,\ldots ,n\}$ heißt zulässig, wenn je zwei benachbarten Ländern vermöge $f$ stets zwei verschiedene Farben zugeordnet sind.
  • Gestattet eine topologischen Landkarte ${\mathfrak {K}}$ auf $F$ für eine ganze Zahl $n>0$ eine zulässige $n$-Färbung, jedoch keine zulässige Färbung mit weniger als $n$ Farben, so nennt man diese ganze Zahl $n$ die chromatische Zahl von ${\mathfrak {K}}$ und bezeichnet sie mit $\chi ({\mathfrak {K}})$.
  • Bildet man über alle topologischen Landkarten auf $F$ das Supremum   $\sup\{\chi ({\mathfrak {K}}):{\mathfrak {K}}\;{\text{topologische Landkarte auf F}}\}$   aller zugehörigen chromatischen Zahlen und ist diese ganze Zahl $<\infty$, so ist dies die chromatische Zahl von $F$. Sie wird mit $\chi (F)$ bezeichnet.

Anmerkung

• Die untersuchten Flächen sind in aller Regel Flächen $F\subset \mathbb {R} ^{d}\;(d=2,3,4)$ .

Bedeutende Lehrsätze

• Satz von Weiske: Ist $F$ der $\mathbb {R} ^{2}$ oder die Einheitssphäre $S^{2}$, so gibt es keine Landkarte mit fünf paarweise benachbarten Ländern.
• Zweifarbensatz: Ist $F$ ein Rechteck und sind darüber hinaus die Grenzlinien einer gegebenen topologischen Landkarte ${\mathfrak {K}}$ so beschaffen, dass jede von ihnen nur zwischen Randpunkten des Rechtecks verläuft oder eine innerhalb des Rechtecks verlaufene geschlossene Jordankurve darstellt, so existiert zu einer solchen topologischen Landkarte ${\mathfrak {K}}$ stets eine zulässige $2$-Färbung.
• Vier-Farben-Satz: Ist $F$ der $\mathbb {R} ^{2}$ oder die Einheitssphäre $S^{2}$, so existiert zu jeder topologischen Landkarte auf $F$ eine zulässige $4$-Färbung.
• Fünf-Farben-Satz: Ist $M$ der $\mathbb {R} ^{2}$ oder die Einheitssphäre $S^{2}$, so existiert zu jeder topologischen Landkarte auf $F$ eine zulässige $5$-Färbung.
• Sechsfarbensatz für das Möbiusband: Das Möbiusband $M$ hat die chromatische Zahl ${\chi }(M)=6$ und es besitzt auf ihm jede topologische Landkarte eine zulässige $6$-Färbung, wobei es unter diesen auch mindestens eine gibt, die nicht mit fünf Farben auskommt.
• Heawoodsche Ungleichung: Ist für eine ganze Zahl $p>0$   $H_{p}$ eine geschlossene orientierbare Fläche vom Geschlecht $p$ und ist dabei $m_{p}=\lfloor {\frac {7+{\sqrt {1+48p}}}{2}}\rfloor$, so existiert zu jeder topologischen Landkarte auf $H_{p}$ eine zulässige $m_{p}$-Färbung. Mit anderen Worten: Für jede derartige Fläche $H_{p}$ erfüllt die chromatische Zahl ${\chi }(H_{p})$ die Ungleichung ${\chi }(H_{p})\leq m_{p}$.
  • Es gilt sogar für ein solches $H_{p}$ stets die Identitätsgleichung ${\chi }(H_{p})=m_{p}$.
  • Insbesondere hat der Volltorus $H_{1}$ die chromatische Zahl ${\chi }(H_{1})=7$ und es besitzt auf ihm jede topologische Landkarte eine zulässige $7$-Färbung, wobei unter diesen auch solche vorkommen, die nicht mit sechs Farben auskommen.

Anmerkungen zu den Lehrsätzen

• Der Satz von Weiske geht auf den Philologen Benjamin Gotthold Weiske (1783–1836), einen Freund des Mathematikers August Ferdinand Möbius, zurück. Die Urheberschaft für dieses Resultat wurde von dem Geometer Richard Baltzer bei Durchsicht des Nachlasses von Möbius herausgefunden. Als Baltzer über den Satz von Weiske und seine Geschichte in einem Vortrag im Jahre 1885 berichtete, setzte er dann jedoch den Irrtum in die Welt, dass sich mit Weiskes Satz bereits der Vierfarbensatz als leichte Folgerung ergibt. Richtig ist dagegen, dass im Gegensatz zu der Darstellung von Baltzer Weiskes Satz allein eine leichte Herleitung des Fünffarbensatzes ermöglicht. Der Irrtum von Baltzer wurde erst im Jahre 1959 von dem Geometer Harold Scott MacDonald Coxeter abschließend beseitigt.
• Der Vierfarbensatz wird heute zwar von vielen, jedoch keineswegs von allen Mathematikern als bewiesen angesehen.
• Dass in der heawoodschen Ungleichung sogar das Gleichheitszeichen zu gelten hat, wurde schon von Percy John Heawood vermutet und konnte dann im Jahre 1968 von den beiden Mathematikern Gerhard Ringel und John William Theodore Youngs abschließend bewiesen werden.

Das Fadenproblem

Das Fadenproblem besteht in der Frage nach der Lösung folgender Aufgabe:

Es soll - wenn möglich - für eine gegebene natürliche Zahl $m\geq 3$ diejenige kleinste natürliche Zahl $\gamma (m)$ bestimmt werden, für welche auf einer geschlossenen orientierbaren Fläche $H_{\gamma (m)}$ des Geschlechtes $\gamma (m)$ beliebig ausgewählte unterschiedliche Punkte $p_{1},p_{2},\ldots ,p_{m}\in H_{\gamma (m)}$ immer paarweise durch einfache Jordankurven in der Weise verbunden werden können, dass all diese Jordankurven einander nie überkreuzen und höchstens in den ausgewählten Punkten $p_{1},p_{2},\ldots ,p_{m}$ treffen.

Wie sich zeigt, ist das Fadenproblem lösbar und dabei ergibt sich die Formel

$\gamma (m)=\lceil {\frac {(m-3)(m-4)}{12}}\rceil \;(m\in \mathbb {N} \;,\;m\geq 3)$.

Dabei zeigt sich weiter, dass die Gültigkeit dieser Formel auch die Gültigkeit der heawoodschen Identitätsgleichung ${\chi }(H_{p})=m_{p}\;(p\in \mathbb {N} \;,\;p>0)$ nach sich zieht.

Literatur

• Rudolf Fritsch: Der Vierfarbensatz. Geschichte, topologische Grundlagen und Beweisidee. Unter Mitarbeit von Gerda Fritsch. BI Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich 1994, ISBN 3-411-15141-2 (MR1270673). 
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1. 
• K. P. Müller, H. Wölpert: Anschauliche Topologie. Eine Einführung in die elementare Topologie und Graphentheorie (= Mathematik für die Lehrerausbildung). B. G. Teubner Verlag, Stuttgart 1976, ISBN 3-519-02709-7. 
• Gerhard Ringel: Das Kartenfärbungsproblem. In: Selecta Mathematica III (Hrsg. Konrad Jacobs) (= Heidelberger Taschenbücher. Band 86). Springer Verlag, Berlin, Heidelberg, New York 1971, ISBN 3-540-05333-6 (MR0543809). 
• Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag, Wien, New York 1996, ISBN 3-211-82774-9 (MR1392955). 
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4. 

Einzelnachweise

Kreferences />

KKKategorie:Topologische Graphentheorie]]

Einzelnachweise und Fußnoten