zurück zu Grundbegriffe II

8. Kreis, Abstand

Def.: Ein Kreis ist ein geschl. Kantenzug, bei dem die Knoten x1,x2,…xn-1 alle verschieden sind (geschlossener Weg).

Die Anzahl der Kanten in einer Kantenfolge heißt die Länge der Kantenfolge. (|KF(x,y|)

Der Abstand d(x,y) zweier Knoten ist die kleinste Länge eines Weges von x nach y, falls es solche Wege gibt.

d(x,y) = min | W(x,y)|
Andernfalls setzt man d(x,y) = ∞

d(x,y) = d(x,y) für alle x,y ∈ V(X)

d(x,y) ≤ d(x,z) + d(z,y) Dreiecksungleichung

In jedem Graphen mit X = (V,E) gilt:

Die Anzahl der Knoten bei einem Graphen ist gerade, wenn die Knotengrade ungerade sind. Jede Kantenfolge von x₁ nach x_n enthält einen Weg von x₁ nach x_n.

Beispiel:

1. [1,2],[2,5],[5,3],[3,2][2,1] …………kein Weg, kein Zug, geschl. KF
2. [1,6],[6,7],[7,8],[8,4][4,8] ……………….“-”
3. [2,3],[3,4],[4,8],[8,9] ……………..kein Kantenzug; Kante 89 nicht vorhanden
4. [1,2],[2,5],[5,3],[3,2] ……………..Kantenzug; kein Weg; Knoten 2 2mal vorh.
5. [3,5],[5,8],[8,4],[4,3] ……………..Kreis
6. [6,7],[7,9],[9,0],[0,8],[8,4] ………..Weg
7. [7,8],[0,8],[0,9] …………………..Weg
8. [6,7],[7,6],[6,7],[7,6] ……………..geschl. KF

Distanz:
d(3,7) = 3
d(4,4) = 0
d(1,0) = 4
d(1,11) = ∞
d(7,0) = 2
d(3,0) = 3

Aus Kantenfolgen einen Weg erstellen:

1. x₁ = x_n Jeder Knoten ist ein Weg zu sich selbst
2. x₁ ¬ x_n solange alle Kanten zwischen dem 1. und dem 2. Erreichen eines Knoten entfernen, dadurch entsteht ein Weg, die direkte Verbindung zwischen x₁ und x_n.

8. 1 Das Bauer, Krautkopf, Ziege, Wolf Problem

Ein Bauer hat einen Wolf, eine Ziege, einen Krautkopf und ein Boot. Sie stehen vor einem Fluss und müssen ihn überqueren. Das Boot kann maximal 2 gleichzeitig befördern (großer Krautkopf!) und es ist zu bedenken, dass der Wolf die Ziege frisst und die Ziege den Krautkopf, wenn man sie alleine lässt. Nur Wolf und Kraut dürfen alleine auf einem Ufer bleiben.
Es gibt dafür mehrere Lösungen, z.B.: Ziege mitnehmen – leer zurück – Kohl mitnehmen – Ziege zurück – Wolf mitnehmen – leer zurück – Ziege mitnehemen, oder eine andere Möglichkeit wäre: Ziege mit – leer zurück – Wolf mit – Ziege zurück – Kraut mit – leer zurück -leer hin und her, so oft es Spaß macht – Ziege mit…
der kürzeste Weg ist zu ermitteln.

mögliche Zustände an einem Ufer:

B,Z,W,K – B,W,Z – B,W,K – B,Z,K – B,Z und am anderen Ufer
– -{} —- K —– Z —– W —- W,K

1.1.1 Lösung zum Beispiel “Der Wolf, die Ziege und der Krautkopf”

1. Man betrachte alle möglichen Zustände auf einem Ufer. Bei 4 Beteiligten ergibt das 4² Möglichkeiten. ({}, B, W, K, Z, BW, BZ,BK,WZ, WK, KZ, BWZ, BWK, BKZ, WKZ, BWKZ) Da jeder Zustand eines Ufers den Komplimentärzustand des anderen Ufers darstellt, braucht man nur ein Ufer darstellen.
2. man streiche laut den Nebenbedingungen alle Zustände, welche nicht möglich sind
3. übrig bleiben ({}, W, K, Z, BZ, WK, BWK, BKZ, BWZ, BWKZ)
   und diese restlichen Zustände ergeben je einen Knoten im Graphen
4. jeder Knoten wird überprüft, ob er mit einem anderen Knoten adjazent sein kann aufgrund der Nebenbedingungen. Somit kann kein Knoten, bei dem der Bauer beteiligt ist mit einem Knoten adjazent sein, bei dem der Bauer auch beteiligt ist, sonst würde das Boot ohne Bauer alleine fahren. Man ziehe alle möglichen Kanten der Reihe nach
5. man suche die kürzesten Wege bzw. den kürzesten Weg in der Kantenfolge vom Ausgangzustand bis zum deffektiven Endzustand.

Sowohl die gestrichelte Linie, als auch die fette Linie stellen einen Weg vom Zustand B,W,Z,K zum Zustand {} dar, wobei die Wege jeweils eine Kantenlänge von 7 haben.
Ufer A: (B,W,K,Z) – (K,W) – (K) – (Z) – {}
Ufer B: {} – (Z) – (W) – (K,W) – (B,W,K,Z) oder
Ufer A: (B,W,K,Z) – (K,W) – (W) – (Z) – {}
Ufer B: {}- (Z) – (K) – (K,W) – (B,W,K,Z)

Potenzmenge – Summe aller Möglichkeiten in einer Menge.

nach oben