Zusammenhang und Abstand
Waelder, Kreise, Faktoren und Gerueste
Eulersche Graphen
Hamilton Kreise
Turniere und multiparate Turniere
Matchingtheorie
Faktortheorie
...
Graphenoperationen
Cliquen
Planare Graphen
Eckenfaerbung
Kanten und Totalfaerbung
Ramsey Theorie
Wald
Kreis
Faktor
Geruest
Eulersche Graphen
Hamiltonkreise
Turniere
Planare Graphen
Eckenfaerbung
Kanten und Totalfaerbung
Matchingtheorie
Faktortheorie
Ramsey Theory
Lutz Volkmann
Graphen an allen Ecken und Kanten
2011
RWTH AACHEN UNIVERSITY
Haus vom Nikolaus
Reihenhaeuser, Kapitel 3 Eulersche Graphen
Eulersches Brueckenproblem 1736
Euler 1707 bis 1783
Wirkliches Leben: Familien A1, A2, A3 und B1, B2, B3
Besitzen grundstueck
Jede Familie Ai ist mit Bj befreundet
Aber jede Familie A1, A2, A3 untereinander verfeindet
Ebenso B1, B2, B3
Loesung: Tunnel Bauen
Kreuzungsfreie Tunnel
Stammbaeume
Turnier
Heiratssatz von Koenig Hall
Partyproblem
1931 und 1935 Koenig und Hall
Alternative Schreibweise
V, E
K, E
bzw
E, K
E: Ecken
K: Kanten
Knoten
Kanten
Ecken
Kanten
Geometrie:
Ecken
Kanten
Knoten = Ecken
x1, x2, x3, ...: Ecken
Kanten: k1, k2, k3, ...
Gerichtete und Ungerichtete Graphen
Digraphen: D
Handschlaglemma: Euler 1736
Kanten, die eine Ecke indizyieren
d(x)
d(x): Eckengrad
Grad
Valenz
Eckengrad
Digraph
d^-
d^+
Je nachdem ob rein oder raus
Digraph: Boegen statt Kanten
Adjanzenzmatrix bei mehrere Kanten zwischen Knoten
Adjanzenzmatrix: 1 fuer jede Kante
3 Kanten: 3
5 Kanten zwischen Knoten 5
Hier kommt Matrizenrechnung
Nachbarschaftsgleichung
Algorithmen
Algorithmen zur bestimmung der Komponenten
Gradsequenz und Gradmengen
Havel 1955
Hakimi 1962
schlichter Graph
Meirling und Volkmann 2009
Kapoor, Polimeni, Wall 1977
Exentritaet: Durchmessesr und Radius
Ringel 1963
Haray, Robinson 1985
Stefan C. Carlson
Bewertete Graphen: Abstandsbegriff erweitern
Problem des kuerzesten Weges
Dantzig und Dijkstra: Algorithmus
starker Zusammenhang
Bruecken
Ein zusammenhaengender Graph besitzt genau dnan einen stark zusammenhaengenden Graphen, wenn er keine Bruecken hat
Namen:
Euler
Havel
Hakimi
Meirling
Volkmann
Kapoor
Polimeni
Wall
Douglas B. West
Kasimir Kuratowski
Good: Rotating Drum Problem
Amithaba Tripathi
Venugoplan
Erdoes es Gallai
Boruvka
C. ...
Ringel 1963
Haray, Robinson 1985
Stefan C. Carlson
Benhocine und Wojda 1985
Clapham und Kleitman 1976
Rao 1979
H. Zhang 1992
Entringer
Jackson
Snyder 1976
Dantzig und Dijkstra: Algorithmus
Robbins 1939
20240804
Turnier, Volleyballtournier
Jede Mannschaft tritt genau ein Mal gegen jede Mannschaft an
Es gibt
(10*9)/2 = 45 Begegnungen
Spielplan erstellen, der immer 5 Paarungen zulaesst
Sehr wahrscheinliche Situation:
Mannschaft A gewinnt gegen Mannschaft B
Mannschaft B gewinnt gegen Mannschaft C
Mannschaft C gewinnt gegen Mannschaft A
Heiratssatz von Koenig Hall
Moechten nicht heiraten?
Heiratssatz und damit verbundenes Problem: Partyproblem
Party:
m Damen
m+n Herren
Jahre 1931 und 1934
Kooenig und Hall unabhaengig voneinander notwendige und hinreichende Bedingungen
Satz: Heiratssatz Kooenig 1931 und Hall 1935: Notwendig und hinreichend dafuer dass alle m Damen gleichzeitig mit einem ihrer Freunde tanzen koennen ist dass alle k mit 1 <= k <= m Damen insgesamt k Freunde haben
Tripel
(E, K, g): Graph oder ungerichteter Graph
Nullgraph
G = (E, K, g) = (E(G), K(G)) = (E, K)
E = E(G) Eckenmenge
Die Elemente aus E Ecken des Graphen
g
