Graphen und Äquivalenzrelation < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:05 Do 21.11.2013 | | Autor: | kRAITOS |
| Aufgabe | Es sei A eine Menge. Wir definieren
[mm] A^{(2)}:= \{ {a,b} \in \mathcal{P}(A) | a,b \in A \}
[/mm]
als Menge der ein- und zweielementigen Teilmengen von A.
Ein Graph ist ein Paar (S,K), das aus einer endlichen Menge S und einer Teilmenge K ⊂ [mm] S^{(2)} [/mm] besteht. Die Elemente von S heißen Scheitelpunkte und die von K Kanten.
Einen Graphen visualisieren wir, indem wir die Scheitelpunkte in der Ebene aufmalen und eine Kante [mm] {s_1, s_2 } [/mm] als Verbindungslinie der Punkte [mm] s_1 [/mm] und [mm] s_2.
[/mm]
So führen S := {1,2,3,4,5,6,7} und K := {1},{1,2},{1,3},{2,3},{4,5},{4,6},{4,7}
zum Bild (siehe Anhang 1)
a) Bestimmen Sie die Mengen S und K, die zu Abbildung 2 führen. (siehe Anhang 2)
b) Zeichnen Sie das Bild des Graphen (S,K) mit S := {1,2,3,4,5,6,7,8,9,10} und
K := {1,2},{3,4},{3,5},{4,5},{6,7},{6,10},{7,8},{8,9},{9,10}.
c) Es seien (S,K) ein Graph und s, t [mm] \in [/mm] S. Ein Weg von s nach t ist ein Tupel [mm] (s_0, [/mm] ..., [mm] s_k)
[/mm]
mit [mm] s_0 [/mm] = s, [mm] s_k [/mm] = t und [mm] {s_i_−_1, si } \in [/mm] K, i = 1, ..., [mm] k^3. [/mm]
Wir sagen s, t [mm] \in [/mm] S sind verbindbar, wenn es einen Weg von s nach t gibt, und definieren die Relation
”∼“ auf S durch
s ∼ t : [mm] \gdw [/mm] (s = t) ∨ (s und t sind verbindbar).
Weisen Sie nach, dass ”∼“ eine ¨Aquivalenzrelation ist.
d) Bestimmen Sie die Menge der Äquivalenzklassen für Abbildung 1 und die Beispiele
aus a) und b). Welches ”Bild“ vermuten Sie im Allgemeinen? |
Ich verstehe vom Anfang bis zum Ende der Aufgabe gar nichts.
Kann mir das jemand übersetzen?
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
Anhang Nr. 2 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:20 Do 21.11.2013 | | Autor: | leduart |
Hallo
Das Bsp und die Beschreibung sind doch eigentlich klar, was verstehst du denn erst mal bei a,b,c nicht?
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:25 Fr 22.11.2013 | | Autor: | kRAITOS |
hmm...
Also bei a muss ich zeigen, dass aus gewissen Mengen aus S und K die Abbildung 2 (Anhang 2) entsteht.
Bei b soll ich das Bild des Graphen (S,K) zeichnen, mit S:= [mm] \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} [/mm] und K:= [mm] \{ \{1,2\},\{3,4\},\{3,5\},\{4,5\},\{6,7\},\{6,10\},\{7,8\},\{8,9\},\{9,10\} \}
[/mm]
c ist ein Nachweis einer Äquivalenzrelation.
Und bei d soll ich Äquivalenzklassen für Abbildung 1 und Beispiele a und b bestimmen.
Aber was fange ich mit den mir gegebenen Graphen an? Wie entstehen diese? Was sagen diese aus?
|
|
|
| |
|
Hallo,
> hmm...
>
> Also bei a muss ich zeigen, dass aus gewissen Mengen aus S
> und K die Abbildung 2 (Anhang 2) entsteht.
Du sollst Mengen $S$ und $K$ angeben, die der gegebene Graph repäsentiert.
Welche Knoten (Scheitelpunkte) sind da?
Welche Kanten?
>
> Bei b soll ich das Bild des Graphen (S,K) zeichnen, mit S:=
> [mm]\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}[/mm] und K:= [mm]\{ \{1,2\},\{3,4\},\{3,5\},\{4,5\},\{6,7\},\{6,10\},\{7,8\},\{8,9\},\{9,10\} \}[/mm]
Na, dann man tau:
10 Knoten irgendwie aufmalen, mit 1 bis 10 benennen und dann die entsprechenden Kanten einzeichnen.
Du hast unendlich viele Möglichkeiten 
Such dir eine aus ...
>
> c ist ein Nachweis einer Äquivalenzrelation.
Ja, ist ein Knoten mit sich selbst verbindbar?
Was sagt die Definition?
Wenn zwei Knoten $u,v$ verbindbar sind, sind dann auch $v,u$ verbindbar?
Analog für die Transitivität ...
Du hast 3 Knoten $u,v,w$, wobei $u,v$ verbindbar sind durch einen Weg [mm] $W_1$ [/mm] und $v,w$ verbndbar durch einen Weg [mm] $W_2$.
[/mm]
Sind dann auch $u,w$ verbindbar? Gib konkret einen Weg an!
>
> Und bei d soll ich Äquivalenzklassen für Abbildung 1 und
> Beispiele a und b bestimmen.
Ja, was sind denn die Äquivalenzklassen der Relation "Verbindbarkeit" ?
Das musst du zuerst mal überlegen ...
>
>
> Aber was fange ich mit den mir gegebenen Graphen an? Wie
> entstehen diese? Was sagen diese aus?
Spielt das eine Rolle? Die repräsentieren irgendwas oder auch nicht. Du kannst sie abstrakt als Repräsentation von Knoten und Kanten in der Ebene betrachten ...
Gruß
schachuzipus
|
|
|
|
