Graphen, Verbindbarkeit
-
Kann mir einer sagen was das heisst??
Die Relation ”verbindbar mit“ für Graphen ist eine Aquivalenzrelation.
Was genau bedeutet das und gibt es dafür einen beweis??
Grüsse
-
also verbindbar heisst meines erachtens in dem sinne erreichbar. also punkt a kann mit punkt b verbunden werden, wenn es einen weg von a nach b gibt. das ist dann eine äqui'relation, denn wenn a mit b verbindbar ist, so auch b mit a (den beweis dieser tatsache überlassen wir dem interessierten leser).
-
meinereiner_unreg schrieb:
das ist dann eine äqui'relation, denn wenn a mit b verbindbar ist, so auch b mit a (den beweis dieser tatsache überlassen wir dem interessierten leser).
Das fehlt noch was:
Äquivalenzrelation heißt: Reflexivität, Symmetrie und Transitivität:
x ~ x für alle x. Das ist hier klar, denn von jedem Knoten kann ich durch nichts tun zu sich selbst gelangen.
x~y => es gibt einen Weg von x nach y
wenn der Graph ungerichtet ist kann ich genau diesen Weg auch von y nach x nehmen, also y ~ x. Damit Symmetrie
zuletzt noch die Transitivität:
x~y, y~z => ... => x~z
und das überlasse ich jetzt dem interessierten Leser
-
Joa das wars ..... der hat mich angemeckert letzes mal das das z in der Beweisführung fehlte ...
Vielen dank :p