Wege, induzierter Untergraph < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:16 Di 24.11.2009 | | Autor: | Drechen |
| Aufgabe | Sei G = (E,K) ein beliebiger Graph, und seien u,v,w [mm] \in [/mm] E. Für die folgenden Aufgabenteile sind ausführliche Begründungen erforderlich
a) Seien v,w [mm] \in Z_G(u). [/mm] Beweise [mm] vV_G [/mm] w.
b) Sei v [mm] \in Z_G(u) [/mm] und gelte [mm] wV_G [/mm] v. Beweise: w [mm] \in Z_G(u)
[/mm]
c) Beweise, dass der induzierte Untergraph [mm] N_G(u) [/mm] von G zusammenhängend ist.
d) Beweise: Ist H ein zusammenhängender Untergraph von G mit [mm] Z_G(u)\subseteq [/mm] E(H), so folgt H = [mm] Z_G(u) [/mm] |
a) bei a habe ich mir überlegt, das mit der Symmetrie und der Transitivität zu lösen
Vor: v,w [mm] \in Z_G(u) [/mm] es gilt also [mm] vV_G [/mm] u und [mm] wV_G [/mm] u nach der Symmetrie auch uVG w
Wegen der Transititvität gibt es also einen Weg von v nach u und von u nach w somit auch von v nach w also [mm] vV_G [/mm] w
(hinter dem G muss eigentlich immer genau das w aber ich bekomme das nicht hin, sodass das G dann weiter nach unten versetzt wird.. tut mir leid)
[mm] vV_G [/mm] u bedeutet -> Weg zwischen v und u
b) Da hätte ich auch mit der Transitivität bewiesen... meine Frage ist jedoch ob das hier überhaupt geht???
c) Leider versteh ich c gar nicht.. [mm] N_G(u) [/mm] ist ja der Nachbarschaftsgraph, der alle zu u adjazenten Ecken enthält, da er induziert ist bleiben alle Kanten zwischen diesen Ecken bestehen. Für mich ist dieser Graph aber nur zusammenhängend wenn G eine Schlinge hat und das ist ja nirgendwo vorgegeben? Oder mache ich da einen Denkfehler?
d) Hier bräuchte ich einen Tipp wie ich überhaupt anfangen kann, weil ich gar nicht vorankomme!
Über Hilfe wäre ich sehr dankbar!!!
Ich habe diese Frage in keinem anderem Forum gestellt!
Liebe Grüße
Andrea
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Fr 27.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
