TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 277

Aus VoWi
Wechseln zu: Navigation, Suche

Man bestimme die kleinste transitive Relation R, die G_3 (als Relation aufgefaßt) enthält.

Anm: Angabe ist nicht eindeutig, siehe Alternativen.

Anm 071123: Angabe wurde im WS07 offenbar auf "umfasst" umgeändert, was aber nicht wirklich klarer ist.

Bsp174 g3.png

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[Bearbeiten]

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[Bearbeiten]

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)

Links[Bearbeiten]

f.thread:49394