TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 170

Man bestimme die kleinste transitive Relation $R$, die $G_{3}$ (als Relation aufgefaßt) enthält.

Anm: Angabe ist nicht eindeutig, siehe Alternativen.

Wäre dann nach der Definiton aRb und bRc => aRc jede Verbindung dreier durch gerichtete Kanten verbundene Knoten:

z.b. (4,1,7), (1,7,6), (7,6,1), (4,3,2), (3,2,1), ...

Hapi

PS: Die Lösung bei Urbanek war dieselbe wie von jurewitsch. Habe die Definition der transitiven Relation nicht vollständig berücksichtigt.

---

Andere Meinung: Transitiv bedeutet: aRb und bRc => aRc

also müsste doch anhand des obigen Bsps zum Beispiel von 4 nach 7 ein Pfeil sein. Ist aber nicht. ein Beispiel für eine transitive Relations wäre meiner Meinung nach zum Beispiel (2,4,1). Weil 2R4 und 4R1 ABER AUCH: 2R1 und somit wäre das dann transitiv. Wenn wer weitere findet, bitte posten, ich kann nur die eine entdecken.

poseidon

Lösung von jurewitsch

Transitive Relation: $\forall x,y,z:xRy\wedge yRz\Rightarrow xRz$.

Der Graph $G_{3}$ als Relation: Die Menge $G$ ={1,2,3,4,5,6,7} und mit ($x\in G$, $y\in G$) $\in$ R:

(1,7),(1,5)
(2,1),(2,4)
(3,2)
(4,3)(4,1)
(6,1)
(7,6)

also (x,y) $\in$ R, wenn es eine gerichtete Kante von x nach y gibt.

Diese Paare sollen jetzt alle schon in der gesuchten transitiven Relation sein. Natürlich muss man aber dann einige dazu geben, damit das transitiv wird.

Zum Beispiel: Da (1,7) und (7,6) Element aus der neuen Relation muss auch (1,6) Element der neuen Relation sein.

Gesamt ergibt das folgende Relation: M: {1,2,3,4,5,6,7}, R:

{(1,7),(1,5),(1,6),(1,1)
 (2,1),(2,7),(2,5),(2,6),(2,4),(2,3),(2,2)
 (3,2),(3,1),(3,7),(3,5),(3,6),(3,4),(3,3)
 (4,3),(4,1),(4,2),(4,7),(4,5),(4,6),(4,7)
 (6,1),(6,7),(6,5),(6,6)
 (7,6),(7,1),(7,5),(7,7)}

Alternativen

Die Angabe kann auf zwei verschiedene Arten aufgefaßt werden:

• Man bestimme die kleinste transitive Relation $R$, die den Graphen $G_{3}$ enthält, also $G_{3}\subseteq R$.
• Man bestimme die kleinste transitive Relation $R$, die in $G_{3}$ enthalten ist, also $R\subseteq G_{3}$.

Die Lösung für Ersteres ist die Lösung von jurewitsch oben. Die Lösung für Zweiteres ist (2,4,1), siehe Diskussion im Info-Forum.

Unser UE-Leiter bevorzugte die zweite Lösung!

--Baccus 01:01, 8. Dez 2006 (CET)