Äquivalenzrelation < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:56 Do 05.11.2009 | | Autor: | Ayame |
| Aufgabe | 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},...,s_{k}) [/mm] mit [mm] s_{0}=s, s_{k}=t [/mm] und [mm] (s_{i-1},s_{i}) \in [/mm] K, i=1,...,k. 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) [mm] \vee [/mm] (s und t sind verbindbar)
Weisen sie nach dass ~ eine Äquivalenzrelation ist. |
ich weiß ja wie man feststellt ob eine relation eine äuivalenzrelation ist : reflexiv, symmetrisch, transitiv.
Aber wie soll ich es an diesem beispiel machen ?
Könnte mir da jemand helfen ??
|
|
| |
|
Hiho,
Reflexivität überlass ich dir, das ist ein Zweizeiler 
ÄR zeigen ist meistens gar nicht so schwer, wenn man stupide die Definitionen anwendet.
Mal als Beispiel die Transitivität:
Sei [mm] $a\sim [/mm] b$ und $b [mm] \sim [/mm] c$, z.z. [mm] $a\sim [/mm] c$.
Nun können ja drei Fälle auftreten.
1.) a=b, b=c
2.) a=b, b und c sind verbindbar
3.) a und b sind verbindbar, b und c sind verbindbar
Ich mach mal den dritten, die beiden anderen überlasse ich dir:
i) a und b sind verbindbar, d.h es gibt Tupel [mm] $(s_0=a, [/mm] ... , [mm] s_n=b)$ [/mm] mit [mm] $(s_{j-1},s_j) \in [/mm] K$
ii) b und c sind verbindbar, d.h. es gibt Tupel [mm] $(t_0=b, [/mm] ... , [mm] t_m=c)$ [/mm] und [mm] $(t_{j-1},t_j) \in [/mm] K$
Nun nehmen wir das Tupel:
[mm] $(h_0=s_0=a,...,h_n=s_n=b=t_0,...,h_{n+m}=t_m)$ [/mm] und hierfür gilt nun natürlich, dass jeweils [mm] $(h_{j-1},h_j) \in [/mm] K$ (warum?), d.h. [mm] $a\sim [/mm] c$ => transitiv.
Nun mach mal weiter.
MFG,
Gono
|
|
|
|
