Graph G od. G' zusammenhängend < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G = (V,E) ein endlicher Graph, n= [mm] $\vmat{V}$ [/mm] und
G' = (V, [mm] $\{$ X $\subseteq$ V: $\vmat{V}$ = 2 $\}$ [/mm] \ E)
a)Zeige, dass G oder G' zusammenhängend ist. |
Annahme G ist zusammenhängend.
Nun ich wähle E' = {$ X [mm] $\subseteq$ [/mm] V: [mm] $\vmat{V}$ [/mm] = 2 [mm] $\}$ [/mm] \ E
Damit nun G' zusammenhängend ist muss [mm] V$\subseteq$V' [/mm] und [mm] E$\subseteq$E' [/mm] gelten. Da V = V' ist ist dies erfüllt, also ist G' ein Teilgraph von G.
Für die Umkehrung: ich weiss nicht wie ich das anstellen soll, da ich nicht genau weiss wie E aussieht, also welche Elemente noch in E' vorhanden sind..
Vielen Dank für die Antworten!
SA
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:46 So 21.10.2012 | | Autor: | hippias |
> Sei G = (V,E) ein endlicher Graph, n= [mm]\vmat{V}[/mm] und
>
> G' = (V, [mm]\{[/mm] X [mm]\subseteq[/mm] V: [mm]\vmat{V}[/mm] = 2 [mm]\}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
\ E)
>
> a)Zeige, dass G oder G' zusammenhängend ist.
> Annahme G ist zusammenhängend.
Fuer die zu zeigende Behauptung ist diese Annahme unguenstig, da in diesem Fall nichts mehr zu zeigen waere. Besser ist es anzunehmen, dass z.B. $G$ nicht zusammenhaengend ist, um dann zu schlussfolgern, dass $G'$ dann zus. sein muss. Lassen sich also $x,y\in V$ nicht durch eine Weg in $E$ verbinden, so betrachte die Menge $\{ x,y\}$ und zeige, dass sie in $E'$ liegt (wenn ich Deine Definition richtig verstanden habe).
>
> Nun ich wähle E' = {$ X [mm]$\subseteq$[/mm] V: [mm]$\vmat{V}$[/mm] = 2 [mm]$\}$[/mm]
> \ E
>
> Damit nun G' zusammenhängend ist muss V[mm]\subseteq[/mm]V' und
> E[mm]\subseteq[/mm]E' gelten. Da V = V' ist ist dies erfüllt, also
> ist G' ein Teilgraph von G.
>
> Für die Umkehrung: ich weiss nicht wie ich das anstellen
> soll, da ich nicht genau weiss wie E aussieht, also welche
> Elemente noch in E' vorhanden sind..
>
> Vielen Dank für die Antworten!
> SA
>
>
|
|
|
|
