Transitive Hülle einer Relation bestimmen

Question

weiß jemand wie ich den transitiven Abschluss einer Relation z.B.

Es sei eine Relation r auf [0,9] gegeben.

r = { (7,4),(1,0),(4,9),(6,9),(5,1),(9,3),(1,2),(5,0),(8,9),(6,8) } bestimme?

Es gilt ja: Wenn x r y und y r z => x r z

Also zum Beispiel:

(7,4) und (4,9) => (7,9)

Also müsste die Menge schon einmal um (7,9) ergänzt werden.

Meine Frage ist, was ist zum Beispiel im Fall

(1,0) und (da gibt es nichts) => ?????????

Oder was mache ich mit der neuen (7,9)? Damit kann ich ja auch transitive Abschlüsse bilden.

zB. (7,9) und (9,3) => (7,3) also müsste das hier auch ergänzt werden?`
Jemand eine Idee?

Answer 1

Es sei eine Relation r auf [0,9] gegeben.

r = { (7,4),(1,0),(4,9),(6,9),(5,1),(9,3),(1,2),(5,0),(8,9),(6,8) } bestimme?

Es gilt ja: Wenn x r y und y r z => x r z

Also zum Beispiel:

(7,4) und (4,9) => (7,9)

Also müsste die Menge schon einmal um (7,9) ergänzt werden. richtig.

Meine Frage ist, was ist zum Beispiel im Fall

(1,0) und (da gibt es nichts) => ????????? dann brauchst du auch nichts zu ergänzen. 

Aber (5,1) und (1,0) ==> (5,0)

Oder was mache ich mit der neuen (7,9)? Damit kann ich ja auch transitive Abschlüsse bilden.

zB. (7,9) und (9,3) => (7,3) also müsste das hier auch ergänzt werden?` richtig.

Tipp: Es wird übersichtlicher, wenn du das in einer 10 x 10 - Tabelle ausfüllst. 

Comments

Habe den Vorgang mit der Tabelle mal gemacht und dann folgende neue Relation:

s sei der transitive Abschluss von r:

s = {(7,4), (1,0), (4,9), (6,9), (5,1), (9,3), (1,2), (5,0), (8,9), (6,8), (ab hier die neuen) (7,9), (4,3), (6,3), (5,0), (5,2), (8,3), (6,9) }

Die neuen wurden anhand einer Tabelle ermittelt, jetzt kann ich zunächst mal die doppelten Streichen:

s = {(7,4), (1,0), (4,9), (6,9), (5,1), (9,3), (1,2), (5,0), (8,9), (6,8), (7,9), (4,3), (6,3), (8,3), (6,9) }

Muss ich jetzt eine neue Tabelle machen mit der neuen Relation oder ist das hier nun der transitive Abschluss von r?

---

Wenn du von deinem s nun wieder den Abschluss bildest und nichts mehr dazu kommt, bist du fertig. D.h. du musst so lange weitermachen , bis nichts mehr dazukommt. 

Du brauchst aber nichts doppelt einzufügen. Das sollte in der Tabelle auch nicht passieren. 

---

Hm, ich weiß nicht ob ich das Prinzip der Tabelle richtig angewendet habe.

Ich habe halt alle Tupel untereinander und nebeneinander aufgeschrieben.

Dann halt beim ersten

           (7,4) [...] (4,9)

(7,4)     X           (7,9)

usw. Da kamen halt doppelte werte raus die ich dann gestrichen hab.

Hättest du sonst eventuell eine Referenz wie diese Tabelle auszusehen hat?