Proseminar: Wege und Kreise in Graphen Eric Hambuch Eric.Hambuch@fernuni-hagen.de 5. Mai 2002 1   Abstract Dieser Seminarvortrag stellt einige grundlegende Begri e der Graphentheorie und stellt einige Eigenschaften einschließlich Beweisen vor. 2   Einf¨uhrung in Graphen Definition 2.1 (Graph)  Sei E  eine  endliche  Menge  von Ecken und K   eine Menge von Kanten {u, v}, u 6 = v. Wir bezeichnen das Tupel G(E, K) als unseren Graphen G. Sei nun z.B. E = {1, 2, 3, 4, 5}, K = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}. Stellen wir G graphisch dar: 5 4 3 1 2 Abbildung 1: Unser Graph G Wir nehmen im weitern Verlauf an, daß in unseren Graphen keine Schlin- gen uu und Mehrfachkanten enthalten. Andernfalls nennen wir einen solchen Graphen explizit Multigraph. 1