Fundamente der Graphentheorie

Frontmatter

Kapitel 1. Zusammenhang und Abstand

Zusammenfassung

Es seien E und K zwei disjunkte, nicht leere Mengen. Weiter setzen wir

$${{P}_{2}}(E) = \left\{ X \right.{\text{|}}X \subseteq Emit1 \leqslant \left| X \right| \leqslant \left. 2 \right\}$$

wobei |X| die Kardinalzahl von X bedeutet. Ist g : K → P₂(E) eine Abbildung, so nennen wir das Tripel (E, K, g)einen Graphen oder ungerichteten Graphen G. Im Fall E = K = ø sprechen wir vom leeren Graphen und im Fall K = ø und E ≠ ø von einem Nullgraphen. Für Graphen benutzen wir folgende Schreibweisen:

$$G = (E,k,g) = (E(G),K(G)) = (E,K)$$

E = E(G) heißt Eckenmenge und die Elemente aus E Ecken des Graphen G. K = K(G) heißt Kantenmenge und die Elemente aus K Kanten von G. Ist k ∈ K mit g(k) = {x,y} (x,y nicht notwendig verschieden), so heißen x, y Endpunkte der Kante k; man sagt auch, die Kante k inzidiert mit den Ecken x und y, oder x und y sind durch die Kante k verbunden; im Fall x = y heißt k Schlinge oder Loop. Verschiedene Ecken, die durch eine Kante verbunden sind, heißen benachbart oder adjazent. Inzidieren zwei verschiedene Kanten mit einer gemeinsamen Ecke, so nennt man die Kanten inzident. Eine Ecke, die mit keiner Kante inzidiert, heißt isolierte Ecke. Sind k₁ und k₂ zwei verschiedene Kanten mit g(k₁) = g(k₂) = {x, y}, so nennt man k₁ und k ₂ Mehrfachkanten oder parallele Kanten. Ein Graph ohne Schlingen heißt Multigraph. Hat ein Multigraph keine Mehrfachkanten, so spricht man von einem schlichten Graphen. Ein Nullgraph, der nur aus einer einzigen Ecke besteht, wird auch trivialer Graph genannt.

Lutz Volkmann

Kapitel 2. Wälder, Kreise und Gerüste

Zusammenfassung

Ein Graph ohne Kreise heißt Wald. Ein Wald, der nur aus einer Komponente besteht, heißt Baum.

Lutz Volkmann

Kapitel 3. Eulersche Graphen

Zusammenfassung

Es sei G ein zusammenhängender und nicht trivialer Graph. Existiert in G ein Kantenzug Z mit K(Z) = K(G), also enthält Z alle Kanten des Graphen, so heißt G semi-Eulerscher Graph und Z Eulerscher Kantenzug. Ist ein solcher Kantenzug Z zusätzlich geschlossen, so nennen wir Z Eulertour, und der Graph G heißt dann Eulerscher Graph.

Lutz Volkmann

Kapitel 4. Hamiltonsche Graphen

Zusammenfassung

Im Jahre 1859 hat Sir William Hamilton (1805 – 1865), der in der reinen Mathematik durch die Einführung der Quaternionen bekannt geworden ist, ein Spiel herausgegeben, das auf dem unten skizzierten Dodekaeder beruht. Eine der von ihm gestellten Aufgaben besteht im Auffinden eines Kreises, der alle Ecken des Dodekaeders enthält (man vgl. Aufgabe 4.1).

Lutz Volkmann

Kapitel 5. Turniertheorie

Zusammenfassung

Eine beliebige Orientierung des vollständigen Graphen K _n mit n ≥ 2 heißt n-Turnier oder Turnier. Ein n-Turnier bezeichnen wir im allgemeinen mit T _n .

Lutz Volkmann

Kapitel 6. Matchingtheorie

Zusammenfassung

Ist G ein Graph, so nennt man eine Kantenmenge M aus G ein Matching von G, wenn M keine Schlingen enthält und keine zwei Kanten aus M inzident sind. Ein Matching M₀ von G heißt gesättigt, wenn es in G kein Matching M gibt mit |M*| und M₀ ≠ M. Ein Matching M* von G nennt man maximal, wenn es in G kein Matching M gibt mit |M*| < |M|. Ist G[M] = (E(M), M) der von M erzeugte Teilgraph, so heißt das Matching M perfekt bzw. fast-perfekt, falls E(M) = E(G) bzw. |E(M)| = |E(G)| − 1 gilt.

Lutz Volkmann

Kapitel 7. Faktortheorie

Zusammenfassung

Ein Teilgraph H eines Graphen G mit E(H) = E(G) heißt Faktor von G. Ist f: E(G) → N₀ eine Funktion und H ein Faktor von G mit d(x, H) = f (x) für alle x ∈ E(G),so nennen wir H einen f-Faktor von G. Im Fall, f (x) ≡ r sprechen wir auch von einem r-Faktor.

Lutz Volkmann

Kapitel 8. Blöcke, Line-Graphen und Graphenoperationen

Zusammenfassung

Es sei G ein zusammenhängender Multigraph. Eine Ecke x aus G heißt Schnittecke von G, wenn k(G−x) > 1 ist. Ein zusammenhängender Teilgraph B von G,der bezüglich B keine Schnittecke besitzt, ist ein Block von G,wenn es keinen zusammenhängenden Teilgraphen B′ ⊆ G ohne Schnittecke gibt mit B ⊆ B′ und B ≠ B′. Damit ist ein Block eines Multigraphen G ein maximaler zusammenhängender Teilgraph ohne Schnittecke. Besitzt ein zusammenhängender Multigraph G keine Schnittecke, so bezeichnet man G auch als Block (damit ist der K₁ ein Block). Man nennt einen Block B von G Endblock,wenn es in B höchstens eine Ecke gibt, die Schnittecke von G ist.

Lutz Volkmann

Kapitel 9. Unabhängige Mengen und Cliquen

Zusammenfassung

Es sei G ein Multigraph.

Lutz Volkmann

Kapitel 10. Dominanz und Irredundanz

Zusammenfassung

Ist G ein Graph, so heißt eine Teilmenge D ⊆ E(G) Dominanzmenge von G oder dominant in G, wenn N[D, G] = E(G) gilt. Eine Dominanzmenge D von G heißt minimale Dominanzmenge von G, wenn es keine Dominanzmenge D′ von G gibt mit D′ < D. Ist D eine minimale Dominanzmenge von G, so nennt man D = γ(G) = γ Dominanzzahl von G.

Lutz Volkmann

Kapitel 11. Planare Graphen

Zusammenfassung

In diesem Kapitel beschäftigen wir uns mit einem Teil der topologischen Graphentheorie. Dabei steht die Frage im Vordergrund, welche Graphen man so in die Ebene einbetten kann, daß sich keine zwei Kanten schneiden, und welche Eigenschaften solche Graphen besitzen. Zur Präzisierung dieser Probleme benötigen wir einige neue Begriffe.

Lutz Volkmann

Kapitel 12. Eckenfärbung

Zusammenfassung

Ist G ein Multigraph, so nennt man eine Abbildung h : E(G) → 1,..., q Eckenfärbung, q-Eckenfärbung oder q-Färbung von G. Ist E _i die Menge aller Ecken von G mit der Farbe i, so nennen wir E _i Farbenklasse.

Lutz Volkmann

Kapitel 13. Kanten- und Totalfärbung

Zusammenfassung

Ist G ein Multigraph, so nennt man eine Abbildung h: K(G) → p {1, ..., q} Kantenfärbung oder q-Kantenfärbung, wenn h(k ₁) ≠ h(k ₂) für alle inzidenten Kanten k ₁, k ₂ aus K(G) gilt. Die Werte 1, ..., q heißen Farben, und der Graph G heißt q-kantenfärbbar. Besitzt der Graph G eine q-Kantenfärbung aber keine (q−1)-Kantenfärbung, so nennt man q den chromatischen Index von G, in Zeichen q = x′ (G) = x′. Ist h eine Kantenfärbung von G und K _i die Menge aller Kanten von G mit der Farbe i, so nennen wir K _i Farbenklasse.

Lutz Volkmann

Kapitel 14. Mehrfacher Zusammenhang

Zusammenfassung

Ein nicht trivialer, zusammenhängender Multigraph G heißt q-fach eckenzusammenhängend oder q-fach zusammenhängend (q ∈ N), wenn |E(G)| ≥ q + 1 gilt, und G − E′ für alle E′ ⊆ E(G) mit |E′| ≤ q − 1 zusammenhängend ist. Ist G q-fach eckenzusammenhängend, aber nicht (q + 1)-fach eckenzusammenhängend, so heißt q =σ(G) = σ Eckenzusammenhangszahl oder Zusammenhangszahl von G. Ist der Multigraph G nicht zusammenhängend, oder ist G der triviale Graph, so heißt G 0-fach zusammenhängend, und wir setzen σ(G) = 0. Ein nicht trivialer, zusammenhängender Multigraph G heißt q-fach kantenzusammenhängend (q ∈ N), wenn G − K′ für alle K′ ⊆ K(G) mit |K′| ≤ q − 1 zusammenhängend ist. Ist G q-fach kantenzusammenhängend, aber nicht (q+1)-fach kantenzusammenhängend, so heißt q = λ(G)= λ Kantenzusammenhangszahl von G. Ist der Multigraph G nicht zusammenhängend, oder ist G der triviale Graph, so heißt G 0-fach kantenzusammenhängend, und wir setzen λ(G)= 0.

Lutz Volkmann

Kapitel 15. Netzwerke

Zusammenfassung

Ein zusammenhängender Multidigraph N = (E,B) heißt Netzwerk, wenn folgende Bedingungen erfüllt sind:

i)

In N existiert genau eine Ecke u mit d⁻ (u, N) = O. Die Ecke u nennt man Quelle des Netzwerkes.

In N existiert genau eine Ecke u mit d⁺; (u,N) = O. Die Ecke u nennt man Senke des Netzwerkes.

 

ii)

Es existiert eine Funktion c : B → R mit c(k) ≥ 0 für alle k ∈ B. Man nennt c Kapazitätsfunktion und c(k) Kapazität des Bogens k.

 

Lutz Volkmann

Kapitel 16. Ramsey-Theorie

Zusammenfassung

Unser erstes Ergebnis stellt eine Lösung der Aufgabe 6.11 dar.

Lutz Volkmann

Kapitel 17. Lokal semi-vollständige Digraphen

Zusammenfassung

Im Jahre 1990 hat Bang-Jensen [1] eine hochinteressante Verallgemeinerung des Turnierbegriffes entwickelt, mit dem wir uns im letzten Kapitel dieses Buches ausführlich beschäftigen wollen.

Lutz Volkmann

Backmatter