Äquivalenzklasse

Neue Frage »

ChristianIN Auf diesen Beitrag antworten »
Äquivalenzklasse
Ich brauche ein Beispiel für eine Äquivalenzklasse.
Gegeben:
Ein Graph mit 4 Knoten (Menge M).
Sei R eine Äquivalenzrelation auf einer Menge M und x Element von R. Die Menge aller Elemente, die zu x in Relation stehen, bezeichnen wir als die Äquivalenzklasse von x und schreiben dafür [x].

[x] = {}

Welche Elemente gehören dann zur Äquivalenzklasse?
Mazze Auf diesen Beitrag antworten »

Die Äquivalenzlasse [x] bezüglich der Äq.Relation R ist also gleich der Menge {}. Nun, die Äquivalenzklasse [x] besitzt dann gar keine Elemente da die leere Menge keine Elemente besitzt.
ChristianIN Auf diesen Beitrag antworten »

ähm, nein

x spoll einfach nur einer der 4 Knoten des Graphen sein.
Zum Beispiel 2.
Welche Elemente gehören dann zur Äquivalenzklasse von 2?
haktar Auf diesen Beitrag antworten »

Ich bin mir nicht ganz sicher was Du wissen willst:

Suchst Du ein Beispiel, oder ist das eine Aufgabe?

Die Aussage [x] = {} ist sicherlich falsch, da ja x in Relation zu sich selbst stehen muß (Reflexivität)
Tobias Auf diesen Beitrag antworten »

Die Realtion ist durch den Graph definiert. Da wir den Graph nicht kennen, kennen wir auch nicht die [x] gehörigen Elemente.

Besteht zwischen den Knoten a und b des (ungerichteten) Graphen eine Kante, so stehen a und b in Relation. Seien weiterhin b und c in Relation, so auch a und c (Transitivität). Die Symmetrie ist in einem ungerichteten Graphen immer gegeben.

Nichts desto weniger trotz müsstest du schon mit mehr Infos rüberkommen.
ChristianIN Auf diesen Beitrag antworten »

sry war vielleicht ein wenig verwirrend.
eigentlich suche ich ein beispiel. ich versteh noch nicht wozu Äquivalenzklassen gut sind.
Da sich eine Äquivalenzklasse auf ein Element einer Äquivalenzrelation bezieht
muss der Graph reflexiv, symmetrisch und transitiv sein wenn ich mich nicht irre.
Zu welchen Knoten müsste dann Knoten 2 in Relation stehen (4 Knoten rechteckig angeordnet)?

1 2
4 3
 
 
Tobias Auf diesen Beitrag antworten »

Das macht meines Erachtens immer noch keinen Sinn.

Wenn du uns einen Graph gibst und nur die Ecken erwähnst, so könntest du uns genausogut eine beliebige Menge {1,2,3,4} angeben. Das wichtige für die Relation sind jedoch die Kanten.

Die Frage zu welchen Knoten dann Knoten 2 in Relation stehen müsste ist also so nicht zu beantworten.

Gäbest du uns einen gescheiten Graphen (also mit Kanten) so müsste 2 in einer Zusammenhangskomponente des Graphen liegen, die für sich vollständig ist. Dann lägen alle Knoten der Zusammenhangskomponente in der Äquivalenzklasse [2].
ChristianIN Auf diesen Beitrag antworten »

http://de.geocities.com/gynec2003/graph.jpg
Tobias Auf diesen Beitrag antworten »

Aha, jetzt machts Sinn. Man sieht:

1.) Jeder Knoten hat eine Kante zu sich selbst: Refelxiv
2.) Der Graph ist ungerichtet: Symmetrisch
3.) Der Graph ist vollständig (d.h. jeder Knoten ist über nur eine Kante mit jedem anderen Knoten verbunden) ; Transitiv.

Es liegt also eine Äquivalenzrelation vor. Die Vollständigkeit des Graphen impliziert auch sofort, dass nur eine Äquivalenzklasse der Knotenmenge M = {1,2,3,4} existiert. Es gilt also hier:

[1] = [2] = [3] = [4] = M
Anno Nym Auf diesen Beitrag antworten »

Schon gesagt wurde (gerade eben):
Die Relation, die durch diesen Graphen dargestellt wird, ist eine Äquivalenzrelation, die genau eine Äquivalenzklasse hat. Sie besteht aus allen vier Knoten, d.h. egal welchen Knoten x ais {1,2,3,4} du nimmst, seine Äquivalenzklasse ist [x] = {1,2,3,4}.

Noch nicht gesagt wurde (Augenzwinkern )

Äquivalenzklassen dienen z.B. dazu, eine Menge zu unterteilen (genauer: partitionieren) in Teilmengen, deren Elemente alle ein bestimmte Eigenschaft gemeinsam haben.

Ein Beispiel:

Du kannst die Menge aller ganzen Zahlen nehmen, und darauf folgende Relation definieren:
x ~ y :<=> (x - y) ist gerade

Du kannst (solltest) prüfen, dass dies eine Äquivalenzrelation ist. Die Äquivalenzklassen sind
die Menge der geraden ganzen Zahlen, geschrieben als 2Z
die Menge der ungeraden ganzen Zahlen, geschrieben als 2Z+1

Was kann man nun mit diesen Äquivalenzklassen machen? Man kann diese z.B. addieren:
Sind x und y ganze Zahlen, dann definieren wir die Summe ihrer Äquivalenzklassen so:
[x] + [y] := [x+y]
Man kann dann prüfen, dass diese Summe tatsächlich nur von den beiden Äquivalenzklassen abhängt, d.h. wenn du x' und y' nimmst, die dieselben Äquivalenzklassen wie x bzw. y haben,
[x'] = [x] und [y'] = [y]
dann ergibt sich dieselbe Summe:
[x'+y'] = [x+y]
Dasselbe funktioniert mit der Multiplikation:
[x] * [y] := [x*y]

Auf diese Weise erhältst du eine neue mathematische Struktur, die man Z/2Z schreibt und "Restklassenring modulo 2" nennt.

Für fast jede Konstruktion einer neuen mathematischen Struktur verwendet man Äquivalenzklassen (was man nur meistens nicht mehr sieht, wenn man diese Struktur dann verwendet).
ChristianIN Auf diesen Beitrag antworten »

Was ich nicht verstehe.
Die Voraussetzung für eine Äquivalenzklasse ist eine Äquivalenzrelation. Aber eine Äquivalenzrelation ist ja immer reflexiv, transitiv und symmetrisch. Befindet sich dann nicht immer die Menge aller Elemente der Äquivalenzrelation in der Äquivalenzklasse jedes Elements wenn wir mal von einem Graphen ausgehen?
Mazze Auf diesen Beitrag antworten »

Nö, sei die Menge {1,2,3,4} = M gegeben und der Graph der Äquivalenzrelation R mit

Graph(R) = {(1,2),(2,1),(3,4),(4,3),(1,1),(2,2),(3,3),(4,4)}

ICh bilde die Quotientenmenge M/R

M/R ={[1],[3]} wobei

[1] = {1,2}
[3] = {3,4}

Ich hoffe das war das was Du meintest da ich in Deinem letzten Satz nicht wirklich was verstehen konnte.
ChristianIN Auf diesen Beitrag antworten »

aso, ja genau das meinte ich.
also 1 und 4 stehen nicht in Relation und 2 und 3 auch nicht?
Das ist dann auch eine Äquivalenzrelation? Ich dachte dafür müsste jedes Element mit jedem in Relation stehen.
Zu deiner Erklärung:
Als Äquivalenzklasse von 1 sind also einfach alle Elemente gemeint, die zu 1 in Relation stehen (bzw wo eine Kante hingeht).

Und warum bildest du diese Quotientenmenge?
Mazze Auf diesen Beitrag antworten »

Nein, in einer Äquivalenzrelation müssen nicht alle Elemente mit einander in Verbindung stehen, weil sonst gäbe es nach dieser Definition immer nur genau eine Äquivalenzklasse, was diesen Begriff dann als sehr sinnlos darstehen lässt. Das was Du meinst ist eine totale Relation , die aber nicht zwingend Äquivalenzrelation ist.
Schau dir meine Relation an, sie ist symmetrisch, reflexiv und transitiv.

Die Quotientenmenge besteht aus Äquivalenzklassen habs nur beispielhalber gemacht.

Die Äquivalenzklassen hast du richtig gedeutet.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »