Einfache Graphen
Wir betrachten zunächst nur besonders einfache Graphen. Sie sind
(1) | endlich: die Menge der Ecken ist endlich, |
(2) | ungerichtet: die Kanten sind keine Pfeile, sondern richtungslose Verbindungslinien, |
(3) | ungewichtet: die Kanten tragen kein individuelles Gewicht (oder anders: alle Kanten haben das Gewicht 1), |
(4) | einfach: es sind keine Mehrfachverbindungen vorhanden, sodass je zwei Ecken entweder durch eine Kante verbunden sind oder nicht, |
(5) | schlingenfrei: es gibt keine Kanten von einer Ecke zu sich selbst. |
Später werden wir diesen Grundtyp verallgemeinern und gewichtete Kanten zulassen. Noch allgemeinere Graphen werden für diese Einführung nicht benötigt.
Unser Basistyp lässt sich wie folgt definieren:
Definition (Graph)
Ein (endlicher, ungerichteter, einfacher) Graph ist ein Paar G = (E, K) mit:
(a) | E ist eine endliche nichtleere Menge. |
(b) | K ist eine Menge von ungeordneten Paaren { a, b } mit a, b ∈ E und a ≠ b. |
Die Elemente von E heißen die Ecken, die Elemente von K die Kanten des Graphen G.
Gilt { a, b } ∈ K, so sagen wir, dass die Ecken a und b in G durch eine Kante verbunden sind oder dass in G eine Kante von a nach b führt. Weiter heißen a und b die an der Kante beteiligten oder die die Kante definierenden Ecken.
Die Menge der Kanten ist also eine Teilmenge der Menge der zweielementigen Teilmengen der Eckenmenge E:
K ⊆ { { a, b } | a, b ∈ E, a ≠ b }.
Dass wir mit Mengen { a, b } statt mit geordneten Paaren (a, b) arbeiten entspricht unserem Wunsch nach ungerichteten Kanten. Führt eine Kante von a nach b, so führt immer auch eine Kante von b nach a. Anschaulich können unsere Kanten in beiden Richtungen durchlaufen werden. Dass wir zudem a ≠ b fordern sichert die Schlingenfreiheit des Graphen: Es führt keine Kante von einer Ecke a nach a. Explizit erlaubt ist die Existenz von Ecken, die an keiner Kante beteiligt sind. Wenn wir möchten, können wir diese Ecken aus dem Graphen durch Verkleinerung der Eckenmenge unter Beibehaltung der Kantenmenge K entfernen.
Beispiele
(1) | Sei G = (E, K) mit E = { 1, 2, 3 }, K = { { 1, 2 }, { 1, 3 }, { 2, 3 } }. Der Graph G hat drei Ecken und drei Kanten. Jede Ecke ist mit den beiden anderen Ecken durch eine Kante verbunden. In graphischer Darstellung hat der Graph die Form eines Dreiecks: |
(2) | Sei G = (E, K) mit E = { 1, 2, 3, 4, 5, 6 }, K = { { 1, 2 }, { 1, 3 }, { 2, 3 }, { 4, 5 } }. Der Graph besitzt eine Ecke (nämlich 6), die mit keiner anderen Ecke verbunden ist. Zudem sind die Eckenmengen { 1, 2, 3 } und { 4, 5 } und { 6 } anschaulich voneinander abgetrennt. Wir werden diese Zusammenhangsbegriffe später genauer untersuchen. |
(3) | Sei G = (E, K) mit E = { 1, …, 12 } und K = { { 1, 2 }, …, { 1, 6 }, { 2, 7 }, …, { 2, 10 }, { 6, 11 }, { 6, 12 } }. Dieser Graph lässt als ein (nach unten wachsender) Baum zeichnen: |