Graphentheorie: Eine Einführung aus dem 4-Farben Problem by Martin Aigner

By Martin Aigner

Es kommt nicht oft vor, dass ein einzelnes challenge ein ganzes mathematisches Gebiet hervorruft. Das allseits bekannte 4-Farben challenge battle solch ein singuläres Ereignis: Aus den Lösungsversuchen entwickelte sich die Graphentheorie, die heute zu den unverzichtbaren Grundlagen der Diskreten Mathematik und Informatik und weiterer angewandter Wissenschaften gehört. Das Buch versucht zweierlei: Es will erstens alle wichtigen Begriffe, Ideen und Sätze für eine Einführung in die Graphentheorie im Bachelorstudium bereitstellen, und zweitens ein tieferes Verständnis für dieses wunderbare Gebiet vermitteln, durch einen Rückblick, wie alles mit dem 4-Farben challenge begann, und einen Ausblick auf die erstaunliche Lösung und den damit aufgeworfenen Fragen.

Show description

Read or Download Graphentheorie: Eine Einführung aus dem 4-Farben Problem PDF

Similar german_15 books

Erfolgreich in der Vorsorgeberatung: Wie Sie durch Konzeptverkauf Ihre Kunden überzeugen und Ihr Einkommen signifikant erhöhen

Im gegenwärtigen Markt der Vorsorgeberatung findet ganz überwiegend keine ganzheitliche, nachhaltige und bedarfsgerechte Beratung statt, sondern Versicherer wie Agenturen und Vermittler verfolgen einen produktorientierten Beratungsansatz - dies sowohl mit großem kundenspezifischen als auch volkswirtschaftlichen Schaden.

Überlegene Geschäftsmodelle: Wertgenese und Wertabschöpfung in turbulenten Umwelten

Mit Hilfe einer profunden Bestandsaufnahme und stichhaltigen examine zeigt Andreas Schmidt drei „Ko“-Kriterien zur Optimierung der Wettbewerbswirkung von Geschäftsmodellen auf: Kontingenz zur Umwelt, Konsistenz seiner Bestandteile und eine kohärente Implementierung über die Entscheidungsebenen hinweg.

Vorsatzanfechtung: Mit Rechtsprechungsregeln Ansprüche vermeiden, abwehren und verfolgen

Tobias Hirte und Karsten Kiesel stellen Rechtsprechungsregeln für Vorsatzanfechtungsfälle gemäß § 133 InsO unter Nennung der jeweils wesentlichen Entscheidungen des Bundesgerichtshofs dar, die im Zusammenhang mit Vorsatzanfechtungssachverhalten stehen. Dabei wird besonderes Augenmerk auf Indizien, Beweisanzeichen sowie Beweiserleichterungen gelegt.

Additional info for Graphentheorie: Eine Einführung aus dem 4-Farben Problem

Example text

Eine Menge S ⊆ Rn heißt konvex, falls mit je zwei Punkten P , Q ∈ S stets die ganze Verbindungsstrecke in S liegt. Anschaulich gesprochen bedeutet Konvexität also, dass von jedem Punkt einer konvexen Menge jeder weitere Punkt „gesehen“ werden kann – ein natürliches ästhetisches Prinzip. 1-dimensionale konvexe Mengen sind offenbar genau die Intervalle. 16 zeigt drei 2-dimensionale und eine 3-dimensionale konvexe Menge. 16 Alle vier Mengen sind abgeschlossen (d. h. enthalten ihre Randpunkte), aber die zweite bis vierte weisen einen wesentlichen Unterschied zur ersten Menge auf: Sie enthalten Punkte, die wir rein optisch sofort als Ecken bezeichnen würden.

Für den Moment wollen wir, um den Zusammenhang zum Färbungsproblem durchsichtiger zu machen, Veblens Vorgangsweise sozusagen dualisieren. 3 Beginn der Graphentheorie 35 Kehren wir zurück zu den Matrizen A und B. A und B mögen die von den Zeilen von A bzw. B erzeugten Unterräume des Vektorraumes Vq aller 0, 1-Tupel der Länge q über GF(2) bezeichnen. Wir wissen bereits: dim A = q − r + 1, dim B = r − 1. Ferner wissen wir, dass B genau aus den Vektoren b besteht, die senkrecht zu allen a ∈ A stehen, d.

Ap−t sind alle = 0 und haben abwechselndes Vorzeichen, wobei t die Anzahl der Komponenten von G ist. (iii) a0 = 1, a1 = −q, ai = 0 für i > p − t. (iv) Hat G die Komponenten G1 , . . , Gt , so gilt p(G; λ) = t p(Gi ; λ). i=1 Beweis. Besitzt G eine Schlinge, so ist p(G; λ) ≡ 0 und es ist nichts zu beweisen. Sei also G schlingenlos. Wir führen Induktion nach der Kantenzahl. Ist |E| = 0 und p |V | = p, so können die Ecken beliebig gefärbt werden, so dass p(G; λ) = λ resultiert. Es sei nun e = uv ∈ E.

Download PDF sample

Rated 4.58 of 5 – based on 32 votes