Graphen < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 23:16 So 12.12.2004 | | Autor: | srg84 |
Hallo Leute,
kann mir jemand ein paar Hinweise geben, wie ich folgende Aufgaben lösen könnte, denn ich habe irgendwie kein Schema.
1) Sei G = (E, K) ein Graph.
z.z.: a) Ist G zusammenhängend, so sind je zwei (verschiedene) Ecken durch einen Weg verbindbar.
z.z.: b) Besitzt G keine Schleifen, so gilt: G ist genau dann ein Baum, wenn je zwei (verschiedene) Ecken durch genau einen Weg verbindbar sind.
2) Sei G = (E, K) ein zusammenhängender Graph.
z.z.: Je zwei Wege von maximaler Länge haben mindestens eine Ecke gemeinsam.
3) Sei G = (E, K) ein schlichter Graph. und |E| [mm] \ge [/mm] 2.
z.z. durch Induktion nach |E| , dass es Ecken [mm] u_{1}, u_{2} \in [/mm] E, [mm] u_{1}\not=u_{2}, [/mm] gibt , so dass [mm] d(u_{1})=d(u_{2} [/mm] ) gilt.
Ich bedanke mich im Voraus für jede Hilfe.
MfG Stephan.
p.s. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:31 Mo 13.12.2004 | | Autor: | Marc |
Hallo Stephan,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich möchte dich bitten, ein paar eigene Ideen beizusteuern, siehe unsere Forenregeln.
> 1) Sei G = (E, K) ein Graph.
> z.z.: a) Ist G zusammenhängend, so sind je zwei
> (verschiedene) Ecken durch einen Weg verbindbar.
Da fragt man sich doch, wie Ihr wohl zusammenhängend definiert habt?
> z.z.: b) Besitzt G keine Schleifen, so gilt: G ist genau
> dann ein Baum, wenn je zwei (verschiedene) Ecken durch
> genau einen Weg verbindbar sind.
Auch hier: Wie lautet Eure Definition von Baum?
> 2) Sei G = (E, K) ein zusammenhängender Graph.
> z.z.: Je zwei Wege von maximaler Länge haben mindestens
> eine Ecke gemeinsam.
Tipp: Indirekter Beweis. Angenommen, zwei Wege maximaler Länge haben keine Ecke gemainsam. Dann kann man wegen des Zusammenhangs des Graphen einen der Wege... Widerspruch.
> 3) Sei G = (E, K) ein schlichter Graph. und |E| [mm]\ge[/mm] 2.
> z.z. durch Induktion nach |E| , dass es Ecken [mm]u_{1}, u_{2} \in[/mm]
> E, [mm]u_{1}\not=u_{2},[/mm] gibt , so dass [mm]d(u_{1})=d(u_{2}[/mm] )
> gilt.
Wo du gerade dabei bist, Definitionen abzutippen: Was ist denn ein schlichter Graph?
Viele grüße,
Marc
|
|
|
|
