Transitive Relationenen bilden

30.10.2015, 11:40

EE_WIIN

Transitive Relationenen bilden

Hallo zusammen,

ich brauche mal Hilfe bei transitiven Relationen.

1. Problem:
Gegeben ist die Menge $\begin{eqnarray*} \left\{g,o,r,t\right\} \end{eqnarray*}$ .

Nun muss ich eine transitive Relation bilden mit mindestens 8 Elementen.
Meine erste Lösung: $\begin{eqnarray*} {(g,o) ; (o,r) ; (g,r) ; (r,t) ; (g,t) ; (g,g) ; (o,o) ; (r,r) ; (t,t)} \end{eqnarray*}$ ist leider falsch. Gut, ich habe 9 Elemente, aber das kann nicht der Fehler sein. Da MIND. 8 auch 9 sein kann Augenzwinkern

2. Problem:
Es ist diese transitive Relation gegeben: $\begin{eqnarray*} A= \left\{ (i,q) ; (i,y) ; (b,i) ; (q,y) ; (y,r)\right\} \end{eqnarray*}$

Nun soll ich dazu eine minimale Liste mit Elementen hinzufügen, damit die Relation transitiv wird.
Meine Lösung: $\begin{eqnarray*} (i,r) ; (b,y) \end{eqnarray*}$
Leider ist sie auch falsch.

Wie muss ich hier vorgehen? Ich lese seit Tagen in Foren, hab mir sogar in Form eines Chats Nachhilfe geben lassen. Aber ich raff es einfach nicht verwirrt

Welcher Buchstabe muss mit welchem? Und in welcher Reihenfolge? Was überhaupt ist hier x, y und z???
traurig

DANKE für Hilfe!!

30.10.2015, 12:04

Math1986

Auf diesen Beitrag antworten »

RE: Transitive Relationenen bilden

Zitat:

Original von EE_WIIN
1. Problem:
Gegeben ist die Menge $\begin{eqnarray*} \left\{g,o,r,t\right\} \end{eqnarray*}$ .

Nun muss ich eine transitive Relation bilden mit mindestens 8 Elementen.
Meine erste Lösung: $\begin{eqnarray*} {(g,o) ; (o,r) ; (g,r) ; (r,t) ; (g,t) ; (g,g) ; (o,o) ; (r,r) ; (t,t)} \end{eqnarray*}$ ist leider falsch. Gut, ich habe 9 Elemente, aber das kann nicht der Fehler sein. Da MIND. 8 auch 9 sein kann Augenzwinkern

Bei dir ist $\begin{eqnarray*} (o,r),(r,t) \end{eqnarray*}$ in der Relation, also muss auch $\begin{eqnarray*} (o,t) \end{eqnarray*}$ drin sein. Der Rest stimmt. Wenn du auf genau 8 Elemente kommen willst dann kannst du auch Elemente, die zu sich selbst in Relation stehen, streichen.

Zitat:

Original von EE_WIIN
2. Problem:
Es ist diese transitive Relation gegeben: $\begin{eqnarray*} A= \left\{ (i,q) ; (i,y) ; (b,i) ; (q,y) ; (y,r)\right\} \end{eqnarray*}$

Nun soll ich dazu eine minimale Liste mit Elementen hinzufügen, damit die Relation transitiv wird.
Meine Lösung: $\begin{eqnarray*} (i,r) ; (b,y) \end{eqnarray*}$
Leider ist sie auch falsch.

$\begin{eqnarray*} (b,y) \end{eqnarray*}$ stimmt schonmal, aber wie kommst du auf $\begin{eqnarray*} (i,r) \end{eqnarray*}$ ? verwirrt

Nachtrag: $\begin{eqnarray*} (i,r) \end{eqnarray*}$ stimmt. Es fehlen aber noch welche. Du musst jede Zweierkombination an Tupeln prüfen.

PS Gemeint ist wohl: "Es ist diese nicht transitive Relation gegeben:"

30.10.2015, 12:11

EE_WIIN

Auf diesen Beitrag antworten »

Ah, mir dämmert was Augenzwinkern

$\begin{eqnarray*} (o,t) \end{eqnarray*}$ musste mit rein, weil ich mit jedem neuen Element/Paar in der Menge die Relation neu prüfen muss... oder so..., richtig?

Auf $\begin{eqnarray*} (i,r) \end{eqnarray*}$ komme ich, weil $\begin{eqnarray*} (i,q) ; (q,y) ; (y,r) \end{eqnarray*}$ eine Kette bilden und das erste Glied (=i) und das letzte (=r) somit auch eine Relation haben, oder nicht?!

30.10.2015, 12:16

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von EE_WIIN
Ah, mir dämmert was Augenzwinkern

$\begin{eqnarray*} (o,t) \end{eqnarray*}$ musste mit rein, weil ich mit jedem neuen Element/Paar in der Menge die Relation neu prüfen muss... oder so..., richtig?

Richtig.

Zitat:

Original von EE_WIIN
Auf $\begin{eqnarray*} (i,r) \end{eqnarray*}$ komme ich, weil $\begin{eqnarray*} (i,q) ; (q,y) ; (y,r) \end{eqnarray*}$ eine Kette bilden und das erste Glied (=i) und das letzte (=r) somit auch eine Relation haben, oder nicht?!

Richtig. Nun musst du jede Kette, die du aus zwei Gliedern bilden kannst, darauf überprüfen, ob deren Verknüpfung auch in der Menge liegt.

So schlecht war das ja gar nicht, es fehlen halt nur ein paar Elemente.

30.10.2015, 13:00

EE_WIIN

Auf diesen Beitrag antworten »

Ah ok. Also sind folgende Ketten möglich:

iq -> qy -> yr -> ir

iy -> yr -> rb -> bi

bi -> iy -> yr -> br

qy -> yr -> rb -> qb

yr -> rb -> bi -> yi

Die roten sind die, die noch fehlen. Zusammenfassend würde ich ergänzen:

$\begin{eqnarray*} (i,r) ; (r,b) ; (b,r) ; (q,b) ; (y,i) \end{eqnarray*}$

aber wenn ich mir das so anschaue, scheint es mir eher eine äquivalente Relation zu sein und keine transitive... oder??

30.10.2015, 13:14

EE_WIIN

Auf diesen Beitrag antworten »

Oh, Fehler! In der zweiten Kette muss das letzte Element so aussehen:

iy -> yr -> rb -> ib

Und diese beiden Ketten sind auch noch möglich:

bi -> iq -> qy -> by

qy -> yr -> rb-> qb

Zusammenfassend würde ich jetzt ergänzen:

$\begin{eqnarray*} (i,r) ; (r,b) ; (b,r) ; (q,b) ; (y,i) ; (i,b) ; (by) \end{eqnarray*}$

Aber unsicher bin ich mir trotzdem...

30.10.2015, 13:34

Math1986

Auf diesen Beitrag antworten »

Also
$\begin{eqnarray*} A= \left\{ (i,q) ; (i,y) ; (b,i) ; (q,y) ; (y,r)\right\} \end{eqnarray*}$
und
$\begin{eqnarray*} (i,r) ; (r,b) ; (b,r) ; (q,b) ; (y,i) ; (i,b) ; (b,y) \end{eqnarray*}$

Das ist richtig. Freude

30.10.2015, 13:38

EE_WIIN

Auf diesen Beitrag antworten »

Auch meiner Meinung nach ist das richtig.
ABER trotzdem ist da irgendwo noch der Wurm drin... denn ich hab eben wieder ein "falsch" bekommen. Es handelt sich hier um Online-Übungsaufgaben meiner Uni. Jede Aufg. kann man mit 3 Versuchen lösen. Einen hab ich noch...
verwirrt

30.10.2015, 13:51

Math1986

Auf diesen Beitrag antworten »

Hm, dann ist die Menge zwar transitiv, aber zu groß...
Wie kommst du von der Ausgangsmenge auf $\begin{eqnarray*} (r,b) \end{eqnarray*}$ ? Du hast in der Ausgangsmenge nirgens ein Tupel wo r links steht. Genauso $\begin{eqnarray*} (i,b) \end{eqnarray*}$ und $\begin{eqnarray*} (q,b) \end{eqnarray*}$ und $\begin{eqnarray*} (y,r) \end{eqnarray*}$

30.10.2015, 13:59

EE_WIIN

Auf diesen Beitrag antworten »

$\begin{eqnarray*} (y,r) \end{eqnarray*}$ ist Element der Menge A, war also schon von vornherein da.
Die anderen (r,b) (i,b) und (q,b) habe ich durch die o.g. Ketten gebildet.
Meinst du, ich "darf" beim Kettenbilden nur von den links in den Tupeln stehenden Buchstaben ausgehen?
Und wieso zweifelst du dann (r,b) (i,b) und (q,b) an und nicht die anderen?
Ich kann dir leider nicht folgen traurig

30.10.2015, 14:10

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von EE_WIIN
$\begin{eqnarray*} (y,r) \end{eqnarray*}$ ist Element der Menge A, war also schon von vornherein da.

Okay, das war mein Fehler.

Durch welche Kette bist du auf $\begin{eqnarray*} (r,b) \end{eqnarray*}$ gekommen?

30.10.2015, 14:16

EE_WIIN

Auf diesen Beitrag antworten »

Steht oben, Beitrag von 13:00.
das $\begin{eqnarray*} (r,b) \end{eqnarray*}$ "fehlt" also in drei Ketten, um diese zu vervollständigen. Ich meine damit, jede Kette muss ja gleich lang sein --> 4 Elemente enthalten. Und um dies zu erhalten, muss hier und da ein r,b ergänzt werden, da das jeweils nachfolgende Element mit b beginnt.
Ich habe die Relationen willkürlich gewählt.

30.10.2015, 14:20

Math1986

Auf diesen Beitrag antworten »

Achso, nein, das darfst du so nicht machen.

Du musst nur Folgendes überprüfen:
$\begin{eqnarray*} (a,b),(b,c)\in R\Rightarrow (a,c)\in R \end{eqnarray*}$
Du darfst nur die Kettenglieder hintereinanderhängen, du darfst aber nicht "fehlende" Glieder ergänzen.

Also
$\begin{eqnarray*} (a,b),(a,c)\in R\not\Rightarrow (b,c)\in R \end{eqnarray*}$

30.10.2015, 14:26

EE_WIIN

Auf diesen Beitrag antworten »

Ok, also sind alle in der Menge A vorhandenen Elemente dann $\begin{eqnarray*} (a,b) ; (b,c) \end{eqnarray*}$ . Indem ich diese Elemente dann jeweils in Beziehung stelle, kann ich also $\begin{eqnarray*} (a,c) \end{eqnarray*}$ ermitteln.
Demnach wären die fehlenden Elemente: $\begin{eqnarray*} (b,q) ; (b,y) ; (b,r) ; (i,r) ; (q,r) \end{eqnarray*}$ .
Habe ich das jetzt ENDLICH verstanden?? Hammer

ich glaubs nicht... smile

30.10.2015, 14:44

Math1986

Auf diesen Beitrag antworten »

Also
$\begin{eqnarray*} A= \left\{ (i,q) ; (i,y) ; (b,i) ; (q,y) ; (y,r)\right\} \end{eqnarray*}$
$\begin{eqnarray*} (b,q) ; (b,y) ; (b,r) ; (i,r) ; (q,r) \end{eqnarray*}$ .

Das sieht richtig aus. Bitte selbst nochmal alles nachrechnen.

Neue Frage »

Antworten »

Transitive Relationenen bilden

Verwandte Themen