Mathematik: Warum wohnt der Nikolaus nicht im Bungalow?
Released by matroid on Mo. 06. März 2006 21:59:02 [Statistics]
Written by jannna - 9190 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Warum wohnt der Nikolaus nicht im Bungalow?

Etwas über Graphentheorie

Ich stehe mal wieder kurz vor einer Prüfung (Graphentheorie natürlich) und versuche, wenn ich mich schon vom Lernen abhalten muß, wenigstens etwas Produktives zu tun. Dabei soll dieser Artikel hier kein Lehrbuch ersetzen (auch nicht zum Teil). Es wird sehr wenig Beweise geben, unter anderem weil dieser Artikel auch ohne Beweise schon sehr lang ist. Im Prinzip stellt das hier eigentlich "nur" eine Übersicht für mich zur Prüfungsvorbereitung dar, ich hoffe aber, daß es vielleicht den einen oder anderen trotzdem interessiert. Ich halte mich dabei (ausschließlich?) an R.Diestel, Graphentheorie (ganz frisch die 3. Auflage). Ich möchte hier vor allem Zusammenhänge zwischen einzelnen Gebieten der Graphentheorie betrachten und zeigen, worauf das Ganze hinsichtlich eines (computerfreien) Beweises des Vierfarbensatzes wohl hinauslaufen wird... Ich hoffe meine kleine Einleitung gefällt euch, es ist mal nicht das Königsberger Brückenproblem ;-)

Eine kleine Geschichte

Jeder kennt sicherlich das Haus vom Nikolaus. Der Nikolaus ist sehr stolz auf sein Haus. Zugegebenermaßen war er am Anfang nicht sehr begeistert: klick Aber die anfängliche Skepsis wich schnell der Begeisterung. Sein Haus ist nämlich ganz was Besonderes. Es steht am Nordpol und ist somit wohl das am nördlichsten gelegene Haus der Welt. Außerdem hat es der Architekt ohne abzusetzen gezeichnet (niemand sonst hat wohl solch eine Zeichnung seines Hauses..) und erst das besonders schöne Fachwerk... Aber warum, fragen wir uns, wohnt der Nikolaus nicht im Bungalow? Nun eigentlich hätte er ja diese moderne Art der Wohnform sogar vorgezogen aber der Architekt spielte einfach nicht mit... Ein Bungalow mit Fachwerk läßt sich nämlich nicht zeichnen ohne den Stift abzusetzen. (Natürlich muß der Architekt Geld sparen wo er nur kann und zeichnet deswegen jede Linie nur einmal) Was genau unterscheidet also das Haus vom Nikolaus vom Bungalow vom Nikolaus? \geoon p(1,4) p(4,4) p(1,1) p(4,1) nolabel() s(p1,p2) s(p1,p3) s(p3,p4) s(p4,p2) s(p1,p4) s(p2,p3) \geooff Der Bungalow vom Nikolaus geoprint(,,0.5,0.5,4.5,4.5,) Das Haus hat ein Dach, der Bungalow nicht. Das is auch schon der gravierende Unterschied. Ohne Dach besitzen nämlich, wenn man den Bungalow mal als Graph auffast, alle Ecken einen ungeraden Grad. (Der Grad einer Ecke ist die Anzahl der Kanten, die diese Ecke treffen.) Wollte man den Bungalow jedoch, wie das Haus, in einem durchzeichnen, müßte man ja in eine Ecke reinzeichnen - und wieder raus. Und zwar bei jeder Ecke außer evtl. der Anfangs- und Endecke, die können ungeraden Grad haben, wenn sie nicht übereinstimmen, da man in die Anfangsecke ja nur heraus- und in die Endecke nur hineinzeichnen muß. Genau das kann man beim Haus beobachten. Dort haben bis auf zwei Ecken, alle Ecken geraden Grad. Der Bungalow hat also zwei Ecken mit ungeradem Grad zuviel.
Kommen wir nun zu etwas völlig Anderem.

Sammlung

In einigen Artikeln zur Graphentheorie, die hier erschienen sind, wurde ja schon fleißig definiert. Ich wiederhol nur kurz der Übersicht halber: Ein Graph ist ein Paar G=(V,E) von disjunkten Mengen mit E \subsetequal\ [V]^2, wobei [V]^2=(V;2)=\menge(2-elementige Teilmengen von V) ist. Die Elemente von V heißen Ecken, und die Elemente von E heißen Kanten (eine Kante ist also ein Eckenpaar). Für eine Kante \menge(x,y) \el E schreiben wir auch xy, oder wir geben der Kante einen Namen, z.B. e=\menge(x,y). Eine Ecke v heißt mit einer Kante e inzident, wenn v \el e ist. Zwei Ecken x,y \el V heißen adjazent oder benachbart, wenn xy \el E ist. N(v) ist die Menge der Nachbarn einer Ecke v. d(v)=\abs(E(v)), der Grad einer Ecke, ist die Anzahl der mit v inzidenten Kanten \d(G):=min{d(v): v\el V} heißt Minimalgrad von G. \D(G):=max{d(v): v\el V} heißt Maximalgrad von G. \d(Bungalow vom Nikolaus) = \D(Bungalow vom Nikolaus)=3, \d(Haus vom Nikolaus) = 2 und \D(Haus vom Nikolaus) =4 \frameon \stress array(Ein erstes Ergebnis:)__ Die Anzahl der Ecken ungeraden Grades in G ist stets gerade. array(Beweis)__ Wir summieren alle Eckengrade auf. Dabei zählen wir jedoch für eine Kante e=\menge(x,y) einmal von x und einmal von y aus, also die Kante e doppelt. Es gilt: \abs(E)=1/2 sum(d(v), v\el V). Da \abs(E) eine natürliche Zahl (oder 0) ist, ist sum(d(v))eine gerade Zahl. Es müssen in der Summe also gerade viele ungerade Summanden vorkommen. q.e.d. \frameoff Ein Graph G heißt vollständig, wenn je zwei Ecken benachbart sind. Den vollständigen Graphen auf n Ecken nennen wir K^n. Ein K^3 ist ein Dreieck. Hat jede Ecke von G den gleichen Grad, heißt G regulär. Ein 3-regulärer Graph (also jede Ecke hat Grad 3) heißt kubisch. Der Bungalow des Nikolaus ist kubisch. Der K^n ist (n-1)-regulär. Ein Weg ist ein nichtleerer Graph P=(V,E) mit V=\menge(x_0 , x_1 , ..., x_k ) und E=\menge(x_0 x_1 , x_1 x_2 , ... , x_(k-1) x_k ). Ist P ein Weg mit k>=3 dann ist C:=P+x_k x_0 ein Kreis. (+: Ist F eine Teilmenge von [V]^2 dann ist G+F:=(V, E\union\ F )) Die Länge eines Kreises\/Weges ist die Anzahl seiner Kanten.

Färbungen

Über Färbungen gab es schon einige Artikel hier auf dem MP. Ich möchte in diesem Abschnitt Färbungen klar definieren, ein paar Ergebnisse aufschreiben und den Zusammenhang zwischen Ecken- und Kantenfärbungen zeigen.

Eckenfärbungen

Eine Eckenfärbung eines Graphen G=(V,E) ist eine Abbildung: c: V-> S mit c(v)!=c(w) für je zwei benachbarte Ecken v und w. Die Menge S enthält die zur Verfügung stehenden Farben. Man wird hauptsächlich nach dem kleinsten k \el \IN fragen, so daß G eine k-Färbung hat, also c:V->\menge(1,..., k) eine Eckenfärbung ist. Dieses k heißt (ecken-) chromatische Zahl von G und wird mit \chi(G) bezeichnet. Ein Graph G mit \chi(G)=k heißt k-chromatisch. Ein Graph G mit \chi(G)<= k heißt k-färbbar. Eine k-Färbung ist natürlich nichts anderes als eine Eckenpartition in k unabhängige Mengen. \(zwei Ecken heißen unabhängig, wenn sie nicht benachbart sind, eine Eckenmenge ist unabhängig, wenn ihre Elemente paarweise nicht benachbart sind\) array(Folgende Frage läßt sich als Eckenfärbungsproblem formulieren)__: Wieviele Tage muß ein Parlament für Ausschusssitzungen anberaumen, wenn jeder Ausschuss einen Tag tagen will und einige Parlamentsmitglieder in mehreren Ausschüssen sitzen? (zum selbst überlegen) Auch der bekannte Vierfarbensatz__ ist ein Eckenfärbungsproblem (für ebene Graphen), aber dazu später. Der Fünffarbensatz__ wurde bereits von Fabi und Kobe vorgestellt (siehe Linksammlung am Ende). Nun einige Abschätzungen für \chi \frameon \stress array(Proposition)__\normal Für jeden Graphen G mit m Kanten gilt: \chi(G) <= 1/2 + sqrt(2m +1/4) array(Beweis)__ \chi(G)=k, G hat zwischen je zwei Farbklassen mindestens eine Kante, da sonst beide Farbklassen gleich gefärbt werden könnten. (Eine Farbklasse ist eine der k unabhängigen Eckenmengen aus der Eckenpartition.) Also gilt m>=1/2 k(k-1) Umstellen nach k ergibt die Behauptung. q.e.d. \frameoff G ist stets mit \D(G)+1 Farben färbbar. Jede Ecke v in G hat höchstens \D(G) Nachbarn. Die sind im schlimmsten Fall alle miteinander benachbart, brauchen also alle eine eigene Farbe. Hinzu kommt noch v, die ja auch eine eigene Farbe braucht. Ist G vollständig oder ein Kreis ungerader Länge, ist dies bestmöglich. Andernfalls ist die Abschätzung \chi(G)<= \D(G)+1 zu grob. Nach einem Satz von Brooks ist \chi(G)<= \D(G) für zusammenhängende Graphen, die nicht vollständig oder Kreise ungerader Länge sind. (Ein Graph heißt zusammenhängend, wenn es zwischen je zwei Ecken einen Weg gibt) Der Satz wird mit Induktion nach Anzahl der Ecken bewiesen (relativ lang). Zum Schluß noch einen Satz: \frameon \stress array(SATZ (Erdös 1959))__\normal Für jedes k\el \IN existiert ein Graph G mit Taillenweite g(G)>k und chromatischer Zahl \chi(G)>k. (Taillenweite = Länge eines kürzesten Kreises) \frameoff Den Satz habe ich aufgeschrieben, weil er recht erstaunlich ist. Hohe Taillenweite heißt ja, daß die kürzesten Kreise im Graphen lang sind \(aus vielen Kanten bestehen\). Das heißt also, der Graph sieht lokal aus wie ein Baum \(Bäume sind Graphen ohne Kreise [naja eigentlich heißen Graphen ohne Kreise Wälder und zusammenhängende Wälder nennt man Bäume...]\) Bäume sind bipartit \(die Eckenmenge eines Baumes läßt sich in zwei Partitionen teilen so, daß die Kanten des Baumes nur zwischen den zwei Mengen verlaufen aber nicht innerhalb\), lassen sich also mit zwei Farben färben. Trotzdem braucht der Graph aber global viele Farben. Intuitiv scheinen sich hohe Chromatische Zahl und hohe Taillenweite auszuschließen. Erdös hat aber gezeigt, daß es Graphen mit hoher Taillenweite und gleichzeitig hoher chromatischer Zahl gibt. Der Beweis dieses Satzes ist ebenfalls interessant. Wie würde man sowas wohl beweisen? Man würde versuchen einen entsprechenden Graphen zu konstruieren. Allerdings macht die Forderung, daß der Graph hohe Chromatische Zahl haben soll, aber lokal nicht dicht sein darf, eine Konstruktion sehr schwierig. \(Um nicht dichte Graphen zu konstruieren fängt man irgendwie baumartig an. Um hohe Chromatische Zahl zu provozieren muß man allerdings irgendwann Kreise produzieren. Diese dürfen nicht zu kurz sein... Ich hoffe die Schwierigkeit kommt hier ein bisschen raus.\) Erdös benutze eine völlig neue Beweismethode. Er begründete die sogenannte probabilistische Methode, die sich, nicht nur in der Graphentheorie, zu einer der wichtigsten Beweistechniken entwickelte. array(Grundlegender Ansatz der probabilistischen Methode)__ Um die Existenz eines Objektes (mit bestimmten Eigenschaften) zu zeigen, dessen explizite Konstruktion schwierig oder unmöglich ist, wird ein geeignetes Wahrscheinlichkeitsmaß auf der Klasse aller zulässigen Objekte betrachtet. Nun wird gezeigt, daß die Wahrscheinlichkeit, daß ein zufällig ausgewähltes Objekt die gewünschte Eigenschaft hat, positiv ist. Die Theorie der Zufallsgraphen entwickelte sich zu einem eigenen Zweig der Graphentheorie. Mehr dazu vielleich in einem anderen Artikel.

Kantenfärbungen

Eine Kantenfärbung von G=(V,E) ist eine Abbildung c:E->S mit c(e)!=c(f) für benachbarte Kanten e und f. Das kleinste k, für das eine Kantenfärbung existiert, heißt kantenchromatische Zahl \chi '(G) array(Folgende Frage läßt sich als Kantenfärbungsproblem formulieren)__: Wie findet man einen Stundenplan minimaler Gesamtlänge für eine Schule, wenn bekannt ist, welcher Lehrer welche Klasse wie häufig unterrichtet? (zum selbst überlegen) Es gilt offensichtlich \chi '(G) >= \D(G), denn alle Kanten, die eine gemeinsame Ecke haben, müssen unterschiedlich gefärbt sein. König bewies (Induktion nach Kantenzahl von G), daß für bipartite Graphen Gleichheit gilt. Und nach Vizing gilt \D(G)<= \chi '(G) <= \D(G)+1 für alle Graphen. Man kann Graphen also hinsichtlich ihrer kantenchromatischen Zahl in zwei Klassen einteilen. In solche mit \chi '(G) = \D(G) und in solche mit \chi '(G) = \D(G)+1. Der Kantengraph L(G) von G ist der Graph auf E (das bedeutet, die Kanten aus G sind die Ecken in L(G)) in dem x,y \el E genau dann benachbart sind, wenn sie es als Ecken in G sind. Jede Kantenfärbung von G ist also offenbar eine Eckenfärbung in L(G) und umgekehrt. Die Bestimmung der kantenchromatischen Zahl ist also ein Spezialfall der Bestimmung der eckenchromatischen Zahl.

Flüsse

Fabi hat ja in seinem Artikel über Gruppenwertige Flüsse schon einiges über Flüsse geschrieben. Seine Einleitung kann ich quasi übernehmen ;-): Also wir stellen uns einen Graphen als ein Netzwerk vor, durch dessen Kanten etwas fließt (Strom, Wasser, Verkehr, ...) \ Wesentliche Eigenschaften dieses Flusses: 1) wieviel fließt durch eine Kante e=xy 2) in welche Richtung fließt es (von x nach y oder von y nach x)? Fließt durch die Kante e=xy ein Fluss der Stärke k von x nach y, so wird dem Eckenpaar (x,y) die Zahl k zugeordnet, fließt der Fluss umgekehrt von y nach x so wird dem Paar (x,y) die Zahl -k zugeordnet: Eine Abbildung f:V^2 -> \IZ mit f(x,y)=-f(y,x) und summe(f(x,y),y \el N(x))=0 (Kirchhoffsche Knotenregel) heißt array(Fluss auf G)__.

Flüsse und Rundflüsse

Dieser Abschnitt ist auf den ersten Blick recht technisch und stellenweise auch verwirrend (ich mußte am Anfang ständig die Definitionen neu mit aufschreiben bis ich eine Aussage verstanden hatte). \ Wir werden im Folgenden Multigraphen betrachten, das heißt Mehrfachkanten und Schlingen sind nun erlaubt. \(Dabei ist zu beachten, daß Mehrfachkanten und Schlingen auch Kreise darstellen.\) Da wir nun von Multigraphen reden, ist eine Kante e=xy nicht mehr eindeutig durch das Paar (x,y) festgelegt. Es kann ja eine weitere Kante f von x nach y geben. Um dieser Schwierigkeit aus dem Weg zu gehen definieren wir uns nun Kantenrichtungen: E^> := \menge((e,x,y): e \el E; x,y \el V ; e=xy) Jede Kante e=xy (x!=y) hat also zwei Richtungen: (e,x,y) und (e,y,x) Schlingen, also Tripel (e,x,x), haben nur eine Richtung. Zu e^> = (e,x,y) \el E^> schreiben wir e^< := (e,y,x) und für F^> \subsetequal\ E^> setzen wir F^< :=\menge(e^< : e^> \el F^>) G, der Graph selbst, ist weiterhin ein ungerichteter Multigraph. Seine Kanten sind nicht auf eine Richtung festgelegt. Das ist flexibler und erleichtert die Begriffsbildung (auch wenn es auf den ersten Blick technisch und kompliziert wirkt). \ Für Eckenmengen X, Y \subsetequal\ V \(nicht notwendig disjunkt\) schreiben wir F^> (X,Y) :=\menge((e,x,y) \el F^> : x \el X; y \el Y; x != y) Wir haben also zwei Eckenmengen X und Y und vielleicht auch Kanten dazwischen. F^> ist nun also die Menge der Kantenrichtungen zwischen diesen beiden Eckenmengen. F^>(x,Y) := F^>(\menge(x),Y) und zur Abkürzung: F^>(x) := F^>(x,V)=F^>(\menge(x), \menge(x)^-) Dabei bezeichnet X^- das Komplement V \\ X einer Eckenmenge X \subsetequal\ V. Für Eckenmengen X,Y \subsetequal\ V \(nicht notwendig disjunkt\) und eine Abbildung f: E^> -> H \(wobei H kommutative Halbgruppe ist\) setzen wir f(X,Y):=summe(f(e^>),e^> \el E^>(X,Y)) hier muß man sich jetzt die Definitionen klar machen, also E^>(X,Y)=\menge((e,x,y) \el E^> : x \el X; y \el Y; x != y). Die Abbildung f ordnet einer Kantenrichtung einen Wert aus der abelschen Halbgruppe zu. Nun wird über die Werte der Kantenrichtungen zwischen den Eckenmengen X und Y summiert. Sei nun H eine abelsche Gruppe. f heißt Rundfluss auf G mit Werten in H oder array(H-Rundfluss auf G)__, wenn f den folgenden Bedingungen genügt: F1) f(e,x,y)=-f(e,y,x) für alle (e,x,y) \el E^> mit x!=y F2) f(v,V) = 0 für alle v \el V F1) ist wieder die Symmetrie, die wir auch schon für Flüsse gefordert hatten. F2) muß man sich wieder klar machen: f(v,V)=summe(f(e^>),e^> \el E^>(v,V)) wobei E^>(v,V) die Menge der Kantenrichtungen ist, die von einer festen Ecke v \el V ausgehen. f(v,V) ist also die Summe über die Werte dieser Kantenrichtungen. Daß diese Summe wieder 0 sein soll, bedeutet also, daß alles, was in eine Ecke hereinfließt, auch wieder herausfließt. F2) ist also die Kirchhoffsche Knotenregel, die auch schon für Flüsse gefordert wurde. array(Es gilt)__: f(X,X)= 0 f(X,X) ist die Summe der Werte der Kantenrichtungen von Kanten innerhalb einer Eckenmenge X \subsetequal\ V, und zwar aller Kantenrichtungen. Für eine Kante e=xy ist sowohl f(e,x,y) als auch f(e,y,x) ein Summand. Wegen F1) gilt die Behauptung. array(außerdem gilt)__: f(X,V)=summe(f(x,V),x\el X) =0 Für jedes x \el X wird f(x,V) summiert. f(x,V) wiederum ist jedoch die Summe der Werte der Kantenrichtungen der von x ausgehenden Kanten. Diese Summe ist laut F2) 0. Deswegen werden hier nur Nullen aufsummiert... Aus diesen beiden Dingen folgt nun: \frameon \stress array(Proposition)__ Ist f ein Rundfluss, so gilt f(X,X^-)=0 für jede Eckenmenge X \subsetequal\ V. array(Beweis)__ f(X,X^-) = f(X,V)-f(X,X)=0-0 =0 q.e.d. \frameoff array(Ein paar Definitionen)__ Eine Kante e=xy heißt Brücke, wenn sie x und y trennt, d.h. wenn es ohne xy keinen Weg mehr von x nach y gibt. Der Graph wird also durch Entfernen von e in zwei unabhängige Teile geteilt. Ist \menge(V_1 , V_2 ) eine Partition von V, so nennen wir die Menge E(V_1 , V_2), aller Kanten zwischen V_1 und V_2, einen Schnitt E(X,X^-) ist ein Schnitt und f(X,X^-), die Summe der Kantenrichtungen von X in den Rest, also die Summe der Kantenrichtungen des Schnittes, ist Null. Da Brücken einen Schnitt bilden, haben Rundflüsse auf Brücken den Wert Null. Sei G=(V,E) ein Multigraph und H eine abelsche Gruppe. Sind f und g zwei H-Rundflüsse auf G, so sind auch f+g: e^> |-> f(e^>) +g(e^>) und -f: e^> |-> -f(e^>) H-Rundflüsse. Die H-Rundflüsse auf G bilden also selbst eine Gruppe. Ein H-Rundfluss, der nirgends Null ist heißt array(H-Fluss)__. Beachte: Die Menge der H-Flüsse ist nicht unter Addition abgeschlossen. [Hier passt jetzt Fabis Artikel über Gruppenwertige Flüsse wunderbar rein]

k-Flüsse

Fabi hat bereits gezeigt, daß es bei der Frage, ob ein Graph einen H-Fluss hat, nur auf die Mächtigkeit der Gruppe H ankommt. \ Sei k>= 1 \el \IZ und G=(V,E) ein Multigraph. Einen \IZ-Fluss f auf G mit 0< \abs(f(e^>)) \el E^> nennt man array(k-Fluss)__. Jeder k-Fluss ist auch ein m-Fluss für m>k. Man fragt also nach dem kleinsten k, für das G einen k-Fluss hat. So ein k heißt Flusszahl von G und wird mit \phi(G) bezeichnet. Hat G keinen Fluss, so setzt man \phi(G):=\infty Zwischen k-Flüssen und \IZ_k-Flüssen gibt es eine enge Beziehung. Sei \sigma_k :\IZ -> \IZ_k , i|->i^- kanonischer Homomorph. Jeder k-Fluss definiert durch Komposition mit \s_k einen \IZ_k-Fluss. Die Umkehrung gilt auch. Und aufgrund der Tatsache, daß es nur auf die Mächtigkeit der Gruppe ankommt, reduziert sich die Frage nach der Existenz von H-Flüssen auf die Frage nach der Existenz von k-Flüssen. Bei der Frage, ob ein gegebener Graph einen k-Fluss hat, ist der folgende Satz eine große Hilfe: \frameon \stress array(Satz (Tutte 1950))__ Ein Multigraph hat genau dann einen k-Fluss, wenn er einen \IZ_k-Fluss hat. \frameoff \IZ_k-Flüsse sind meistens einfacher zu konstruieren als k-Flüsse. Für kleine k wollen wir nun mal schauen, welche Graphen einen k-Fluss haben. \stress array(1-Fluss)__ Ein Graph hat genau dann einen 1-Fluss, wenn er keine Kanten hat. \stress array(2-Fluss)__ Ein Graph hat genau dann einen 2-Fluss, wenn alle seine Eckengrade gerade sind. \(Insbesondere gilt für die vollständigen Graphen K^n für n>1 , n ungerade \phi(K^n)=2.\) array(Beweis)__ Ein Graph hat genau dann einen 2-Fluss, wenn er einen \IZ_2-Fluss hat. Da bei Flüssen die Kantenrichtungen den Wert Null nicht annehmen, muß die konstante Abbildung E^> ->\IZ_2 , e^> |-> 1^- der Kirchhoffregel genügen. Das geht nur, wenn alle Eckengrade gerade sind. q.e.d. Ein Graph heißt gerade, wenn alle seine Eckengrade gerade sind. \stress array(3-Fluss)__ Ein kubischer Graph hat genau dann einen 3-Fluss, wenn er bipartit ist. Und, für alle geraden n>4 gilt \phi(K^n)=3. \( \phi(K^2) = \infty (warum?), n=4 s.u.\) \stress array(4-Fluss)__ K^4 ist der einzige vollständige Graph mit 4-Fluss. Jeder 4-kantenzusammenhängende Graph hat einen 4-Fluss. G mit \abs(G)>1 heißt l-kantenzusammenhängend, wenn G-F für jede Kantenmenge F \subsetequal\ E der Mächtigkeit \ \frameon \stress array(Proposition)__ (i) Ein Graph hat genau dann einen 4-Fluss, wenn er die Vereinigung zweier gerader Teilgraphen ist. \(Vereinigung: G=(V,E), G'=(V',E'), G\union\ G' := (E\union\ E', V\union\ V')\) (ii) Ein kubischer Graph hat genau dann einen 4-Fluss, wenn er 3-kantenfärbbar ist. array(Beweis von (ii))__ Sei G=(V,E) ein kubischer Graph. Ein Graph hat einen 4-Fluss, wenn er einen (\IZ^2)_2 = \IZ_2 \times\ \IZ_2 -Fluss hat. Zuerst habe G also einen (\IZ^2)_2 -Fluss f. Wir definieren nun eine Kantenfärbung c:E->(\IZ^2)_2 \\ \menge(0): Wegen a=-a für alle a \el (\IZ^2)_2 gilt f(e^>) = f(e^<) für jedes e^> \el\ E^>. Die Kante e wird nun mit der Farbe f(e^>) gefärbt. Wir müssen nun überprüfen, ob das eine zulässige Färbung ist, ob also benachbarte Kanten auch unterschiedlich gefärbt sind. Angenommen zwei Kanten mit gemeinsamer Ecke v trügen die gleiche Farbe, so würden sich die Werte von f auf diesen beiden Kanten zu Null summieren und die dritte Kante an v hätte dann den Wert 0 (Kirchhoff muß ja gelten). f ist aber ein (\IZ^2)_2-Fluss, hat also nirgends den Wert 0, unser Färbung ist also korrekt. Umgekehrt definiert jede 3-Kantenfärbung c:E->(\IZ^2)_2 \\ \menge(0) vermöge f(e^>)=f(e^<)=c(e) für alle e^> \el\E^> einen (\IZ^2)_2-Fluss auf G, da sich die drei Elemente von (\IZ^2)_2 zu Null addieren. q.e.d. \frameoff Da alle kubischen 3-kantenfärbbaren Graphen einen 4-Fluss haben, haben sie keine Brücke, denn Brücken bilden einen Schnitt und Rundflüsse auf Schnitten haben den Wert Null, Also gibt es keinen k-Fluss auf Graphen mit Brücken.

Farb-Fluss-Dualität

Teil (ii) der letzten Proposition läßt ja schon einen Zusammenhang zwischen Flüssen und Färbungen erahnen. Und tatsächlich gibt es einen sehr erstaunlichen Zusammenhang zwischen Flüssen und Färbungen: \ Jeder k-Eckenfärbung eines ebenen Multigraphen entspricht ein k-Fluss auf seinem Dual, und umgekehrt. In dieser Aussage stecken einige Begriffe, die wir bisher nicht geklärt haben: Deswegen kommt nun ein Einschub über ebene Graphen und Dualität:

Ebene Graphen und Dualität

Bisher haben wir abstrakte Graphen betrachtet. Ein abstrakter Graphen, den man auf ein Blatt Papier zeichnen kann, ohne daß sich Kanten überschneiden, heißt plättbar. Ein in diesem Sinne gezeichneter Graph heißt eben. Ebene Graphen sind also die Zeichnungen plättbarer Graphen. Etwas formaler: \ Eine Zeichnung bildet die Ecken des (abstrakten) Graphen auf Punkte, und die Kanten auf Polygonzüge, stückweise geradlinige Kurven, der euklidischen Ebene \IR^2 ab. Dabei schneiden sich die Kurven nur in ihren gemeinsamen Endecken. Dabei ist ein Polygonzug (Polygon) eine Vereinigung endlich vieler Strecken im \IR^2, die zum Einheitsintervall (Einheitskreis) homöomorph ist und eine Strecke in der euklidischen Ebene ist eine Punktmenge der Form \menge(p+\l(q-p) : 0<= \l <= 1), wobei p und q (p!= q) die Endpunkte sind. Sei O \subsetequal \IR^2 offen. Durch einen Polygonzug in O verbunden zu sein definiert eine Äquivalenzrelation auf O. Die zugehörigen Äquivalenzklassen sind offen heißen Gebiete von O. Ist X \subsetequal O abgeschlossen, und sind y_1, y_2 zwei Punkte aus verschiedenen Gebieten von O\\X, so trennt X die Punkte y_1 und y_2 in O. Der Rand einer Menge X\subsetequal \IR^2 ist die Menge Y aller Punkte y\el \IR^2, für die jede Umgebung von y sowohl X als auch \IR^2 \\ X trifft. Ist X offen, so liegt sein Rand ganz in \IR^2 \\X. Ein array(ebener Multigraph)__ ist ein Paar (V,E) endl. Mengen mit den folgenden Eigenschaten: (i) V \subsetequal \IR^2; (ii) Jede Kante ist Polygonzug zwischen zwei Ecken oder ein Polygon, das genau eine Ecke (seine Endecke) enthält; (iii) das Innere einer jeden Kante enthält weder eine Ecke noch einen Punkt einer anderen Kante; Für jeden ebenen Graphen G ist \IR^2 \\ G offen. Die Gebiete von \IR^2 \\ G werden Gebiete von G genannt. Ein ebener Graph heißt maximal eben, wenn man keine neue "Kante" hinzufügen kann ohne die Eigenschaft eben zu sein zu verletzen.\(Das ist formal nicht ganz geschickt formuliert aber ich denke es ist klar was gemeint ist.\) \frameon \stress array(Satz (Eulersche Polyederformel für die Ebene))__ Ist G ein zusammenhängender ebener Graph mit n>= 1 Ecken, m Kanten und l Gebieten, so gilt: n-m+l=2 \frameoff Diese Formel zeigt oft, daß ein bestimmter Graph nicht als ebener Graph auftreten kann. Ein K^5 etwa kann kein ebener Graph sein. Ein Graph (abstrakt) heißt plättbar, wenn er in die Ebene einbettbar ist. Ein plättbarer Graph G heißt maximal plättbar, wenn G plättbar ist, G+e für jede neue Kante e aber nicht mehr. Ein plättbarer Graph mit n>=3 Ecken ist genau dann maximal plättbar wenn er 3n-6 Kanten hat. Graphentheoretiker fragen sich an der Stelle natürlich, welche Graphen plättbar sind und welche nicht. Einen K5 als "Minor" zu enthalten ist zum Beispiel ein Kriterium für Nichtplättbarkeit. \ Betrachten wir nun mal einen ebenen Multigraphen G. Nun setzen wir in jedes Gebiet von G eine neue Ecke und verbinden diese Ecken wie folgt miteinander: Für jede Kante e von G werden die neuen Ecken in den beiden Gebieten von G, auf deren Rand e liegt durch eine neue Kante e^\* verbunden, und zwar so, daß sich e und e^\* nur in einem Punkt schneiden. Liegt e auf dem Rand nur eines Gebietes, so legen wir an dessen neue Ecke eine Schlinge e^\* durch e. Auf diese Weise haben wir einen neuen Multigraphen G^\* :=(V^\*, E^\*) konstruiert. Dieser heißt array(dual zu G)__ und zwar in folgendem Sinne: Konstruieren wir aus G^\* in gleicher Weise einen Dual G^\*\*, so ist G^\*\* topologisch isomorph zu G. \(was auch immer ein topologischer Isomorphismus ist...\) Ganz formal: Seien G=(V,E) und G^\*:=(V^\*, E^\* ) zwei bel. ebene Multigraphen und F(G)=:F \(F^\* analog\) die Menge der Gebiete von G, dann heißt G^\* \(topologisch\) dual zu G, wenn Bijektionen existieren: F->V^\*, f|->v^\*(f) E->E^\*, e|->e^\* V->F^\*, v|->f^\*(v) mit (i) v^\*(f) \el f für alle f \el F (ii) \abs(e^\* \cut\ G)=\abs( e^°^\* \cut\ e^°)=\abs(e \cut\ G) =1, dabei bedeutet e^°: das Innere der Kante e, also der Polygonzug ohne seine Endecken. (iii) v \el f^\*(v) für alle v \el V. Jeder zusammenhängende ebene Multigraph hat einen Dual. Dabei ist der Zusammenhang hinreichend und notwendig. Wir wissen also nun was ein Dual ist und was ein ebener Multigraph ist. \frameon \stress array(Satz (Tutte 1954))__ Für jedes Paar dualer ebener Multigraphen G und G^\* gilt \chi(G)=\phi(G^\*) \frameoff Ich werde diesen Satz nicht beweisen, da dazu Lemmas benötigt werden, die ich hier nicht erwähne. Abgesehen davon würde das den Artikel sprengen denke ich. Bemerkenswert zu diesem Beweis ist noch, daß es der erste Induktionsbeweis ist, der mir vor die Augen gekommen ist, bei dem die eigentliche Arbeit im Induktionsanfang steckt.

Flussvermutungen, Snarks und der Vierfarbensatz

\frameon \stress array(Vierfarbensatz)__\normal Jeder ebene Graph hat eine Eckenfärbung mit höchstens vier Farben. \frameoff Der Vierfarbensatz trifft eine Aussage über ebene Graphen. Wie wir eben gesehen haben, lassen sich ebene Graphen nicht so einfach behandeln wie abstrakte Graphen. Ich habe zum Beispiel mal in einem Seminar den Fehler gemacht und habe versucht eine Kante eines ebenen Graphen zu kontrahieren (zur Kantenkontraktion siehe auch Fabis Artikel über gruppenwertige Flüsse). Berechtigterweise kam dann die Frage zurück: "Was passiert denn mit der Ebene, wenn Sie zwei Punkte einfach zusammenziehen?" Ist das dann überhaupt noch eine Ebene? Habe ich dann noch einen ebenen Graphen? Man sieht, wenn man sich am Vierfarbensatz probiert, hat man es immer auch mit Topologie zu tun. Das macht dieses Problem so schwierig.

Die Tutteschen Flussvermutungen

Da wir uns weiter oben bereits mit k-Flüssen beschäftigt haben, kann man sich die Frage nach der Charakterisierung von Graphen mit einem k-Fluss stellen. Wir wissen, daß Graphen mit Brücken keinen k-Fluss haben können (da Brücken einen Schnitt bilden und Rundflüsse auf Schnitten den Wert Null haben...). Haben aber alle brückenlosen Graphen einen k-Fluss? Nun, Seymour hat 1981 bewiesen, daß jeder brückenlose Graph einen 6-Fluss hat. Die Frage der Charakterisierung stellt sich nun also nur noch für k< 6 , und da wir ganz genau wissen, wie es mit 1- und 2-Flüssen aussieht, stellt sich die Frage konkret für k=3,4,5 . Tutte, der als der Begründer der algebraischen Flusstheorie gilt, hat die folgenden Vermutungen aufgestellt: \frameon \stress array(Fünfflussvermutung (Tutte 1954))__\normal Jeder brückenlose Multigraph hat einen 5-Fluss. \frameoff Wie sieht es mit 4-Flüssen aus? Haben alle brückenlosen Multigraphen einen 4-Fluss? Zumindest die 4-kantenzusammenhängenden Graphen haben einen. Der Petersengraph jedoch hat keinen 4-Fluss, da er kubisch aber nicht 3-kantenfärbbar ist. \(Diese Stelle hier hat die entsprechende Proposition oben motiviert.\) Die folgende Vermutung sagt nun, daß der Petersengraph in jedem Graphen ohne Vierfluss auftreten muss.
Bild Der Petersengraph
\frameon \stress array(Vierflussvermutung (Tutte 1966))__\normal Jeder brückenlose Multigraph, der nicht den Petersengraphen als Minor enthält, hat einen 4-Fluss. \frameoff Kubische brückenlose Multigraphen ohne 4-Fluss werden Snarks genannt. Das geht wohl \(laut mathworld.wolfram\) auf Martin Gardner (1976) zurück. Bis 1946 war der Petersengraph der einzige bekannte Snark. 1946 veröffentlichte Blanusa zwei weiter Snarks:
Bild Blanusa Snarks
Die Blanusa Snarks finden sich auch im Logo der Kroatischen Mathematischen Gesellschaft. Tutte schrieb über Blanusas Paper: "I saw Blanusa's paper soon after it appeared. Alas, I did not understand the language, but the diagram made all clear!" ... Tutte entdeckte den nächsten Snark, der nach Blanche Descartes benannt wurde und von dem ich kein Bild gefunden habe. Der fünfte Snark wurde 1973 von Szekeres gefunden:
Bild Szekeres Snark
Isaacs bewies 1975, daß es eine unendl. Familie von Snarks gibt. Hier habe ich noch zwei schöne Snarks:
Bild Bild Flower Snark und Double Star Snark
Der Begriff Snark geht übrigens auf Lewis Carroll zurück: The Hunting of The Snark Die Vierflussvermutung für kubische Graphen sagt nun also, daß jeder Snark den Petersengraphen als Minor hat. Der Petersengraph ist in diesem Sinne also der kleinste Snark. Der Vierfarbensatz ist äquivalent zu der Aussage, daß es keine plättbaren Snarks gibt. Man kann auch zeigen, daß die Fünfflussvermutung gilt, wenn sie für alle Snarks gilt. Obwohl Snarks eine recht spezielle Klasse von Graphen sind, machen sie die Probleme nicht leichter. Zum Schluss noch die Dreiflussvermutung: \frameon \stress array(Dreiflussvermutung (Tutte 1972))__\normal Jeder brückenlose Multigraph ohne einen Schnitt aus genau einer oder genau drei Kanten hat einen 3-Fluss. \frameoff Die drei Flussvermutungen sind wahr für plättbare Graphen. Die Vierflussvermutung für plättbare Graphen ist äquivalent zum Vierfarbensatz und die Fünfflussvermutung ist äquivalent zum Fünffarbensatz. Kommen wir nun nocheinmal auf den Vierfarbensatz zurück, speziell auf das Finden eines computerfreien Beweises. Wenn die Vierflussvermutung bewiesen werden kann, folgt der Vierfarbensatz. Das schöne an der Vierflussvermutung ist, daß sie eine Aussage über abstrakte Graphen macht. Man muß sich also nicht mehr mit Topologie rumschlagen.

Übersicht über Graphentheorieartikel

Ich hoffe, daß dieser Artikel auch gefällt, obwohl er mehr eine Zusammentragung von Wissen (oder Vermutungen) ist, als ein normaler Artikel. Die meisten Sachen, die erwähnt werden, habe ich (hoffe ich) erklärt. Die Bilder der Snarks mit den roten Ecken (und die Infos dazu) habe ich von http://mathworld.wolfram.com/ Viel Spaß mit der Graphentheorie Jana Zum Schluss habe ich noch eine Übersicht aller Artikel, die sich ansatzweise mit Graphentheorie beschäftigen und die ich gefunden habe: Mathematik: kleine mathematische Hilfe für potentielle Schwiegermütter Mathematik: Die Graphen Sir O. Rigami und S. von Onobe Mathematik: Graphentheorie: Hamiltonkreise Teil 1 Mathematik: 5-Farben-Satz Mathematik: Listenfärbung Mathematik: Gruppenwertige Flüsse Mathematik: Der Fünffarbensatz Mathematik: Was ist ein Matroid? Professor E.W. Dijkstra 1930-2002 Das Königsberger Brückenproblem - Beweistechnik+Graphentheorie
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Graphentheorie :: Vier-Farben-Satz :: Kantenfärbungen auf Graphen :: Interessierte Studenten :
Warum wohnt der Nikolaus nicht im Bungalow? [von jannna]  
Etwas über Graphentheorie - Vier-Farben-Satz, Kantenfärbungen, Snarks, Petersen-Graphen und die Äquivalenz gewisser Färbungs- und Flußprobleme auf kubischen Graphen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 9190
 
Aufrufstatistik des Artikels
Insgesamt 494 externe Seitenaufrufe zwischen 2012.01 und 2022.07 [Anzeigen]
DomainAnzahlProz
http://google.de43487.9%87.9 %
http://google.hr163.2%3.2 %
https://google.de81.6%1.6 %
https://google.com71.4%1.4 %
http://google.com51%1 %
https://www.bing.com20.4%0.4 %
http://search.sweetim.com20.4%0.4 %
https://www.ecosia.org20.4%0.4 %
http://www.bing.com71.4%1.4 %
https://duckduckgo.com10.2%0.2 %
http://www.search.ask.com10.2%0.2 %
http://www.ecosia.org10.2%0.2 %
http://www.metacrawler.com10.2%0.2 %
http://images.google.de10.2%0.2 %
http://search.conduit.com10.2%0.2 %
https://metager.de10.2%0.2 %
http://isearch.babylon.com10.2%0.2 %
http://google.at10.2%0.2 %
https://yandex.ru10.2%0.2 %
http://ecosia.org10.2%0.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 456 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2017 (77x)http://google.de/url?sa=t&rct=j&q=
201303-03 (61x)http://google.de/url?sa=t&rct=j&q=jede farbe mindestens "chi(g)-1" kanten...
201302-02 (55x)http://google.de/url?sa=t&rct=j&q=rundfluss graphentheorie
201304-04 (30x)http://google.de/url?sa=t&rct=j&q=petersengraph symmetriegruppe
201301-01 (30x)http://google.de/url?sa=t&rct=j&q=mathe topologie nikolaus
201306-07 (24x)http://google.de/url?sa=t&rct=j&q=rund fluss graphentheorie
201210-10 (22x)http://google.de/url?sa=t&rct=j&q=warum kann man das haus vom nikolaus ohne d...
201201-01 (21x)http://google.de/url?sa=t&rct=j&q=wie sieht das haus vom nikolaus aus am nord...
201212-12 (21x)http://google.de/url?sa=t&rct=j&q=wie viele möglichkeiten gibt es, ohne de...
201211-11 (17x)http://google.de/url?sa=t&rct=j&q=some citizens of Koenigsberg
201206-06 (16x)http://google.hr/imgres?um=1&biw=1364&bih=643&tbm=isch&tbnid=URRxLoQG-mdfWM:
201407-07 (11x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB4QFjAA
201202-02 (11x)http://google.de/url?sa=t&rct=j&q=some citizens of königsberg
201305-05 (10x)http://google.de/url?sa=t&rct=j&q=maximal plättbar 3 zusammenhängend
201204-04 (7x)http://google.de/url?sa=t&rct=j&q=seminar probabilistische methode zufallsgra...
2021-2022 (7x)https://google.de/
201403-03 (6x)http://google.de/imgres?sa=X&biw=1525&bih=704&tbm=isch&tbnid=URRxLoQG-mdfWM:
2020-2021 (6x)https://google.com/
201208-08 (5x)http://google.de/url?sa=t&source=web&cd=11&ved=0CEYQFjAK
201406-06 (5x)http://google.com/url?sa=t&rct=j&q=
201402-02 (5x)http://google.de/url?sa=t&rct=j&q=haus vom nikolaus ohne dach
201207-07 (5x)http://google.de/url?sa=t&rct=j&q=vollständige eckenfärbung
201203-03 (4x)http://google.de/url?sa=t&rct=j&q=vierfarbensatz kubische karte

[Top of page]

"Mathematik: Warum wohnt der Nikolaus nicht im Bungalow?" | 19 Comments
The authors of the comments are responsible for the content.

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Soral am: Di. 07. März 2006 06:49:40
\(\begingroup\)Hallo! Sieht gut aus der Artikel. (Zumindest vom Äußeren her, von der Theorie versteh ich eh nichts ;-)) Zum Thema Snark: Geht die Begriffsdefinition usw. wirklich auf Lewis Carroll zurück, oder hat man sich wiedereinmal nur den Namen ausgeborgt? (also wie bei Quarks, was Murray Gellman ja von James Joyce 'klaute') Mfg Martin.\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Rebecca am: Di. 07. März 2006 08:18:55
\(\begingroup\)Hi Martin, Martin Gardner hat sich den Namen von Lewis Carroll ausgeborgt. „The Hunting of the Snark” von Lewis Carroll hat nicht nur zur Namensgebung in der Mathematik beigetragen, auch Physiker und Biologen haben sich hier bedient. Zitat aus Wiki: The word "snark" has since been used in graph theory, as has "boojum", and was also used, some say with chilling aptness, as the name of the SM-62 Snark nuclear cruise missile. The term "boojum" has also been used in physics to describe a phenomenon originally found in superfluid helium-3, and also in liquid crystals, and for the boojum tree. Gruß Rebecca PS: Hier kann man sich übrigens das Gedicht als Text oder Hörbuch (macht echt Spaß) runterladen: librivox.org/the-hunting-of-the-snark-by-lewis-carroll/ PPS: Bild boojum tree \(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: matroid am: Di. 07. März 2006 22:53:20
\(\begingroup\)Hi Jannna, ein sehr langer, dennoch weitgehend sehr lesenswerter Artikel, in dem Du - auch mit durchdachten Überleitungen - interessante Querbezüge und Verwandtschaften unter sehr verschiedenen graphentheoretischen Problemen aufzeigst und die Genese solcher Ideen aufscheinen läßt. Gut zu lesen sind die Abschnitte zu Ecken- und Kantenfärbungen. Der für mich interessanteste Abschnitt ist der mit den Flüssen und der folgende über die Snarks. Dazu zwei Anmerkungen (oder Fragen?): Wenn die Vierflußvermutung für plättbare Graphen äquivalent zum Vierfarbensatz ist, dann ist es schon keine Vermutung mehr. Richtig? In der Einleitung Deines Artikels sagst Du "... zeigen worauf das Ganze hinsichtlich eines (computerfreien) Beweises des Vierfarbensatzes wohl hinauslaufen wird...". Du glaubst also, daß über einen unabhängigen Beweis der Vierflußvermutung umgekehrt der Vierfarbensatz endlich ohne einen Computerbeweis erwiesen sein wird. Ja, das wäre ein Ding! Zu den Snarks und dem Petersen-Minor: Man sieht gleich, daß die Blanusa-Snarks einen Petersen-Minor enthalten (nur ein paar Kanten kontrahieren und fertig). Die anderen gezeigten Snarks enthalten den Petersen-Graph sicherlich auch. Man kann schnell weitere Snarks konstruieren, wenn man ausgehend vom Petersen-Graph ein paar Ecken und Kanten 'ergänzt'. Eigentlich wichtig ist aber, ob jemand ein Snark findet, daß den Petersen-Graph nicht enthält. Das kann aber nicht der Fall sein, denn der Vierfarbensatz gilt ja. Insofern ist die Suche nach weiteren Snarks heutzutage höchstens ästhetisch interessant, bzw. ist bereits historisch. Richtig? Ich danke Dir für den reichhaltigen Artikel, und nicht zuletzt auch für die Bündelung aller bisherigen Graphentheorie-Artikel in einer Übersicht. Viele Grüße Matroid\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: jannna am: Di. 07. März 2006 23:27:01
\(\begingroup\)Hallo Die Drei Flussvermutungen stimmen für plättbare Graphen. Das ich das nicht geschrieben habe ist mir grad erst aufgefallen... Zu den Snarks, ja weitere Snarks zu finden ist denke ich nicht weiter förderlich (es sei denn die Suche nach weiteren wirft anderweitige nützliche Ergebnisse ab...) Aber Snarks sind quasi der harte Kern der Vier- und Fünfflussvermutung. Deswegen sind sie interessant. Ich weiß leider nicht, wie realistisch das Warten auf einen Beweis der Vierflussvermutung ist, also ob es da schon was konkretes gibt. Flüsse sind auch bisher mein erklärtes Lieblingsthema. Leider ,bis auf einen Satz, stoff der Graphentheorie 2 und deswegen für mich nicht Prüfungsrelevant... Grüße jana \(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: abc am: Mi. 08. März 2006 17:02:19
\(\begingroup\)Hallo Jana, mir hat Dein Artikel sehr viel Freude bereitet! Viele Grüße Jörg\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Daeladus am: Mi. 08. März 2006 18:54:04
\(\begingroup\)Ich kann mich nur anschließen: Ein sehr schön geschriebener Artikel, zu einem meiner Lieblingsthemen. Nur die anfänglichen Definitionen sind mir selbst ein Graus. Ecken statt Knoten..hmpf!! Liegt aber nicht in deiner Hand, wenn du dich an ein Buch angelehnt hast. Ecke ist für einen Erstleser nur sehr verwirrend, habe ich selbst die Erfahrung gemacht, da ein Knoten (Ecke) in einem Graph keine Ecke sein muss, nach unserem Verständnis :-). Aber das nur als kleiner Einschub!! Greetings, Florian\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: jannna am: Do. 09. März 2006 23:02:55
\(\begingroup\)Hallo Florian, "da ein Knoten (Ecke) in einem Graph keine Ecke sein muss, nach unserem Verständnis" Das versteh ich nicht. Kannst du das näher erklären? Grüße jana\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Gockel am: Fr. 10. März 2006 14:31:48
\(\begingroup\)Hi Jana. Vielleicht ist mit "Ecke" ein Randknoten gemeint. mfg Gockel.\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: jannna am: Fr. 10. März 2006 16:29:57
\(\begingroup\)Hmmm Mein Prof hatte mich mal, nachdem ich Knoten statt Ecken sagte, mit einem Zahnschmerzengesicht angesehen und deuete irgendwie sowas an, daß es da einen Unterschied gibt.... leider hab ich damals nicht drauf reagiert und nachgefragt... Würde mich aber nun doch mal interessieren... Grüße Jana\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Daeladus am: Di. 14. März 2006 19:22:19
\(\begingroup\)Na vielleicht bilde ich mir das didaktische Problem auch einfach ein 😄 Eine Ecke sagt für mich aus, dass ich zwei Strecken beispielsweise habe, welche einen Winkel ZWISCHEN 0 und 180 Grad einschließen. Allerdings kann ich auch folgendes haben: -------o-------- Dabei ist "o" die Ecke (Knoten) und der Winkel beträge 180 Grad. Das sieht für mich nicht wie eine Ecke aus 😄 Aber wollte niemanden damit verwirren. Greetings, Florian\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Gockel am: Di. 14. März 2006 19:38:06
\(\begingroup\)Hi Florian. Das ist nun etwas ganz anderes und viel unwichtigeres ... Ob man die Striche nämlich gerade oder schräg oder wie auch immer zeichnet, ist vollkommen egal. Daher ist dieser Winkel auch vollkommen egal. mfg Gockel.\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Daeladus am: Di. 14. März 2006 23:51:00
\(\begingroup\)Hey Gockel, ich weiss was Graphenisomorphismen sind etc. War wohl ein Fehler das Thema anzusprechen. War nur eine "kleine" Meinung von mir, was das Verstehen angeht. Ich nehme somit alles zurück und behaupte das Gegenteil. Grüße, Florian \(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Martin_Infinite am: Mi. 15. März 2006 01:22:43
\(\begingroup\)Hi Florian, deine Kritik zum Begriff "Ecke" ist vollkommen gerechtfertigt. Lass' dich da mal nicht verunsichern (Gockel vergisst mal wieder die Subjektivität in der Mathematik). Gruß Martin\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: matroid am: Mi. 15. März 2006 07:01:36
\(\begingroup\)Ein Graph hat Ecken und Kanten, dagegen ist 'Knoten' ein Begriff aus der Topologie. Jeder der etwas anderes behauptet, hatte einen anderen Prof. 😉 Gruß Matroid\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: jannna am: Do. 16. März 2006 16:20:31
\(\begingroup\)Grad hab ich was von knotless embeddings (von Graphen in eine Fläche) gelesen, bzw. überflogen. Knoten ist also wirkleich keine geschickte Bezeichnung für die Ecken eines Graphen 😉 Grüße Jana\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Daeladus am: Do. 16. März 2006 23:07:28
\(\begingroup\)Scho recht 😉\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: Morris am: Fr. 17. März 2006 08:46:42
\(\begingroup\)Hm, nun ja, Doppeldeutigkeit von Begriffen ist ja nun keine Seltenheit. Wenn man nicht komplett neue Wörter erfinden will, was ja nun mal auch seine Nachteile hat, läßt sie sich auch kaum vermeiden. Und meines Wissens ist Knoten auch in der Graphentheorie ein gebräuchlicher Begriff für das, was andere als Ecken bezeichnen. Man muß halt klarstellen, wovon man redet, dann ist alles in Butter. Gruß Morris\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: fschumann am: Mi. 07. Juni 2006 20:02:49
\(\begingroup\)was spricht für die einführung der graphentheorie in der schule und wie weit sollte man es mit einem solchen exkurs im rahmen der allgemeinbildung "treiben"? wer hat erfahrungen auf diesem gebiet gesammelt?\(\endgroup\)
 

Re: Warum wohnt der Nikolaus nicht im Bungalow?
von: jannna am: Mi. 28. März 2007 17:05:49
\(\begingroup\)Whaaa, "...Tutte entdeckte den nächsten Snark, der nach Blanche Descartes benannt wurde..." Ich hab grad rausgefunden, daß Blanche Descartes ein Pseudonym von Tutte war... auch nett: “The Expanding Unicurse” by Blanche Descartes Some citizens of Königsberg Were walking on the strand Beside the river Pregel With its seven bridges spanned. “O Euler, come and walk with us,” Thos burghers did beseech. “We’ll roam the seven bridges o’er, And pass but once by each.” “It can’t be done,” thus Euler cried. “Here comes the Q. E. D. Your islands are but vertices, And four have odd degree.” From Königsberg to König’s book, So runs the graphic tale, And still it grows more colorful, In Michigan and Yale. Grüße Jana\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 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]