Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Neuer Abschnitt in Das 4-Farben Problem

Impulse

Das ungelöste Vier-Farben-Problem war für etliche Mathematiker der Anlass sich mit Graphentheorie zu befassen. Aus den vielen gewonnenen Erkenntnissen habe ich zwei Beispiele ausgewählt.

Plättbarkeit

Das Vier-Farben-Problem führt zu der Frage, was ein ebener Graph denn genau sei. Einer Zeichnung mit Kreuzungen sieht man oft nicht an, ob der Graph plättbar ist oder nicht. Die Untersuchungen zur Plättbarkeit führten zum bekannten "Satz von Kuratowski" (1930). Er besagt, dass ein Graph genau dann planar ist, wenn er gewisse Graphen nicht als Untergraphen enthält. (Genauer müsste es heissen: Enthält keine Unterteilung dieser Untergraphen, also auch nicht mit zusätzlichen Ecken. Ich wollte aber nicht zu viele Begriffe einführen.) Die nicht planaren Untergraphen heissen K_5 und K_{3,3}. \begin{tikzpicture} \coordinate (A2) at (2,0); \coordinate (B2) at (4,0); \coordinate (C2) at (4.8,1.4); \coordinate (D2) at (3,2.8); \coordinate (E2) at (1.2,1.4); \coordinate (F2) at (7,0); \coordinate (G2) at (9,0); \coordinate (H2) at (11,0); \coordinate (I2) at (7,3); \coordinate (K2) at (9,3); \coordinate (L2) at (11,3); \draw (A2)--(B2) circle(0.1); \draw (A2)--(C2) circle(0.1); \draw (A2)--(D2) circle(0.1); \draw (A2)--(E2) circle(0.1); \draw (B2)--(C2); \draw (B2)--(D2); \draw (B2)--(E2); \draw (C2)--(D2); \draw (C2)--(E2); \draw (D2)--(E2); \draw (A2) circle (0.1); \draw (F2)--(I2) circle (0.1); \draw (F2)--(K2) circle (0.1); \draw (F2)--(L2) circle (0.1); \draw (G2)--(I2); \draw (G2)--(K2); \draw (G2)--(L2); \draw (H2)--(I2); \draw (H2)--(K2); \draw (H2)--(L2); \draw (F2) circle (0.1); \draw (G2) circle (0.1); \draw (H2) circle (0.1); \end{tikzpicture} K_5 und K_{3,3} Oft sind diese Untergraphen "versteckt" und nicht gut zu erkennen. In der nächsten Graphik sind einige zusätzliche Ecken und Kanten zu einem K_{3,3} eingezeichnet. Diese ändern aber nichts daran, dass der Graph nicht planar ist. \begin{tikzpicture} \coordinate (A2) at (2,0); \coordinate (B2) at (4,0); \coordinate (C2) at (4.8,1.4); \coordinate (D2) at (3,2.8); \coordinate (E2) at (1.2,1.4); \coordinate (F2) at (7,0); \coordinate (G2) at (9,0); \coordinate (H2) at (11,0); \coordinate (I2) at (7,3); \coordinate (K2) at (9,3); \coordinate (L2) at (11,3); \draw (F2)--(I2) circle (0.1); \draw (F2)--(K2) circle (0.1); \draw (F2)--(L2) circle (0.1); \draw (G2)--(I2); \draw (G2)--(K2); \draw (G2)--(L2); \draw (H2)--(I2); \draw (H2)--(K2); \draw (H2)--(L2); \draw (F2) circle (0.1); \draw (G2) circle (0.1); \draw (H2) circle (0.1); \filldraw[blue] (7.8,0.6) circle (0.1); \filldraw[blue] (10.2,1.8) circle (0.1); \filldraw[blue] (10.2,0.6) circle (0.1); \draw[blue] (7.8,0.6)--(10.2,1.8); \draw[blue] (7.8,0.6)--(I2); \draw[blue] (10.2,0.6)--(10.2,1.8); \end{tikzpicture} Enthält K_{3,3} Man darf natürlich keine Ecken auf Kreuzungen, d.h. auf mehr als eine Kante legen und somit diese entfernen. Beim Beweis des Fünf-Farben-Satzes durch Zusammenlegen von Ecken könnte man versuchen nochmals zwei Ecken zusammenzulegen, um den Vierfarbensatz zu beweisen. Dabei erhält man aber die von Kuratowski beschriebenen nicht planaren Graphen. Es handelt sich also um ein topologisches Argument, wieso eine Ecke vom Grad 5 nicht reduziert werden kann.

Hamiltonkreise

Es wurden nach Kempe viele weitere Versuche unternommen die Vierfarben-Vermutung zu beweisen. Einen sehr schönen, aber leider nicht in jedem Fall zutreffenden "Beweis" für die Vier-Farben-Vermutung wird mit Hilfe von Hamilton-Kreisen konstruiert (Tait 1883). Die Bezeichnung "Hamiltonscher Graph" geht auf ein Spiel Hamiltons (1856) zurück, dem "Icosian Game". Im Spiel geht es darum auf einem Dodekaeder die Ecken mit einer geschlossenen Linie so zu verbinden, dass jede Ecke einmal besucht wird. "Icosian Game" Wir betrachten den Gerüstgraphen einer Landkarte, also den Graphen, dessen Kanten aus den Landesgrenzen bestehen. Ein Kreis, der alle Ecken genau einmal enthält ist ein Hamilton-Kreis. Durch einen Hamilton-Kreis wird der Graph in zwei disjunkte Kempe Ketten aufgeteilt. Die Färbung ist damit trivial. Im Bild sind die beiden Kempe-Ketten gestrichelt eingezeichnet.
Hamilton-Kreis
Anders, als in Taits Vermutung, hat nicht jeder ebene Graph (Genauer: jeder 3-reguläre polyedrische Graph) einen Hamilton-Kreis. Nach längeren Diskussionen brachte Tutte 1946 ein Gegenbeispiel: Tutte Graph. Damit wurde wieder ein neues Kapitel in der Graphentheorie aufgeschlagen, die Vier-Farben-Vermutung blieb aber nach wie vor ungelöst.
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]