Ist die Relation R eine Äquivalenzrelation? (Adjazenzmatrix)

Question

Aufgabe:

Sei R eine Relation auf der Menge 5={1,2,3,4,5}, welche durch die folgende Adjazenzmatrix gegeben ist:

\( \left(\begin{array}{lllll}1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1\end{array}\right) \)

Ist die Relation R eine Äquivalenzrelation? Zeichne den zugehörigen Digraphen und gib die kleinste R enthaltene Äquivalzenzrelation durch Angabe der Elemente an.

Also natürlich habe ich bereits geschaut, was man unter Äquivalenzrelation usw. versteht, aber ich weiß nicht, wie ich da jatzt was aus der Adjazenzmatrix genau schlau werden sollte.

Answer 1

die gegebene Relation R ist keine Äquivalenzrelation denn es gilt nicht 3 ~ 3 (verletzte Reflexivität). Außerdem gilt 1 ~ 5, aber nicht 5 ~ 1 (verletzte Symmetrie).

Nimmt man diese beiden Elemente jedoch heraus aus der Menge, so bildet die Menge {1, 2, 4}, die man dadurch erhält, mit der Adjazenzmatrix eine Äquivalenzrelation, da gilt

1 ~ 1, 2 ~ 2, 4 ~ 4 (Reflexivität),

1 ~ 2 und 2 ~ 1, 2 ~ 4 und 4 ~ 2, 4 ~ 1 und 1 ~ 4 (Symmetrie),

sowie 1 ~ 2 ~ 4 (Assoziativität).

Die Äquivalenzrelation impliziert also nur eine einzige Äquivalenzklasse.

Die Adjazenzmatrix, die im obigen Sinne eine Äquivalenzrelation darstellen soll, muss symmetrisch sein, da sonst die Symmetrie der Relation verletzt ist. Und genau dann wenn die Matrix symmetrisch ist, beschreibt sie eine Äquivalenzrelation im obigen Sinne.

Entfernst du nun die Spalten 3 und 5, sowie die Zeilen 3 und 5, so ergibt sich schließlich eine symmetrische Matrix, von der wir ja schon wissen, dass sie eine Äquivalenzrelation in obigem Sinne impliziert.

MfG

Mister

Comments

es heißt transitiv, nicht assoziativ.

Äquivalenzklassen sind hier nicht gefragt.

Eine symmetrische Matrix reicht als Beweis nicht aus, das sie trotzdem gegen Transitivität verstoßen kann.

Es wird eine Relation gesucht, die \(R\) enthält, nicht in \(R\) enthalten ist (Letzteres wäre auch witzlos, da z.B. (1,1) bereits eine Äquivalenzrelation darstellt.) Es muss also erweitert, nicht gekürzt werden.

Grüße,

M.B.