Kreise und besondere Graphen
Im Kreis laufen
Joelle und Hannah laufen ebenfalls durch den Park zur Schule. Sie möchten aber nicht unnötig lange im Park herumlaufen und betrachten deshalb nur einfache Wege: Der Weg soll nicht im Kreis verlaufen, also keine Stelle mehrmals besuchen.
Merke: besondere Wege
Die Länge eines Weges ist die Anzahl seiner Kanten – also die Anzahl der Knoten im Wort minus 1. BESTA hat die Länge 4.
Ein Weg heißt einfach, wenn kein Knoten zweimal vorkommt (z. B. BESTA).
Ein Weg heißt Zyklus, wenn Start- und Endknoten gleich sind und dabei keine Kante doppelt benutzt wird (z. B. SHKSMTS – S kommt mehrfach vor, aber keine Kante).
Ein besonderer Zyklus ist der Kreis: Start- und Endknoten sind gleich, sonst kommt kein Knoten zweimal vor (z. B. SMTS). Man spricht auch von einem „einfachen Zyklus“.
Zeige auf die fett gedruckten Begriffe.
G = (V, E)
V = {B, E, S, H, T, M, A, K}
E = {{B,E}, {E,S}, {E,H}, {H,S}, {S,T}, {S,M}, {S,K}, {T,M}, {T,A}, {M,A}, {H,K}, {K,A}}
Besondere Graphen
Merke: schlichter Graph
Ein ungerichteter Graph ohne Mehrfachkanten zwischen zwei Knoten und ohne Schlingen (Kanten von einem Knoten zu sich selbst) heißt einfacher oder schlichter Graph.
Merke: vollständiger Graph
Ein schlichter Graph heißt vollständig, wenn jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist – sonst unvollständig. Zeige auf „unvollständig“: Gestrichelt erscheinen die Kanten, die zum vollständigen Graphen fehlen.
Aufgabe 5: Zeichne einen vollständigen Graphen mit fünf Knoten.
Aufgabe 5: Zeichne einen vollständigen Graphen mit fünf Knoten.
Merke: zusammenhängender Graph
Ein ungerichteter Graph heißt zusammenhängend, wenn es zwischen je zwei Knoten einen Weg gibt – sonst nicht zusammenhängend. Zeige darauf: Gestrichelt erscheint eine Kante, die den Graphen zusammenhängend machen würde.
Aufgabe 7: Zeichne einen Graphen mit sechs Knoten, in dem jeder Knoten mindestens eine Kante hat, der aber nicht zusammenhängend ist.
Aufgabe 7: Zeichne einen Graphen mit sechs Knoten, in dem jeder Knoten mindestens eine Kante hat, der aber nicht zusammenhängend ist.