Vollständige Graph, Teilgraph < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:49 Mi 24.10.2012 | | Autor: | Lu- |
| Aufgabe | | Zeige dass jeder induzierte Teilgraph eines vollständigen Graphen wieder ein vollständiger Graph ist. |
Hallo
Unsere Definitionen:
vollständiger Graph: [mm] \forall [/mm] v,w [mm] \in [/mm] V [mm] \exists [/mm] Kante [mm] \{v,w\} \in [/mm] E.
induzierte Teilgraph: Sei G(V,E) ein Graph.
[mm] H=H(V_H [/mm] , [mm] E_H [/mm] ) defeniert einen Teilgraph wenn alle Knoten, die zu kanten aus [mm] E_H [/mm] gehören in [mm] V_H [/mm] enthalten sind. , wobei [mm] V_H \subseteq [/mm] V und [mm] E_H \subseteq [/mm] E
Wenn übderdies alle Kanten in E(G), die beide Knoten in [mm] V_H [/mm] haben, auch zu [mm] E_H [/mm] gehören, dann nennt man H einen induzierten Teilgraphen.
Für mich klingt die zubeweisende Aussage logisch, jedoch scheitere ich das als Beweis auzuschreiben..
Vlt könnt ihr mir da helfen
LG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:32 Mi 24.10.2012 | | Autor: | tobit09 |
Hallo Lu,
zu zeigen ist:
[mm] $\forall$ [/mm] vollständigen Graphen G(V,E):
[mm] $\forall$ [/mm] von G induzierten Teilgraphen [mm] $H(V_H,E_H)$:
[/mm]
[mm] $H(V_H,E_H)$ [/mm] vollständig.
Zu zeigen ist also eine "für alle"-Aussage. Dazu gibt es ein Standardverfahren:
Man nimmt sich hier einen nicht weiter spezifizierten Graphen G(V,E) her. ("Sei G(V,E) ein beliebiger vollständiger Graph.")
Zu zeigen ist:
[mm] $\forall$ [/mm] von G induzierten Teilgraphen [mm] $H(V_H,E_H)$:
[/mm]
[mm] $H(V_H,E_H)$ [/mm] vollständig.
Wieder also eine "für alle"-Aussage zu zeigen. Standardverfahren:
"Sei [mm] H(V_H,E_H) [/mm] ein von G induzierter Teilgraph."
Zu zeigen ist:
[mm] $H(V_H,E_H)$ [/mm] vollständig.
Das heißt zu zeigen ist:
[mm] $\forall [/mm] v,w [mm] \in V_H\colon \quad \{v,w\} \in E_H$.
[/mm]
Wieder eine "für alle"-Aussage! Du ahnst schon, was jetzt kommt: Standardverfahren:
"Sei ..."
Zu zeigen ist: ...
Ergänze dies und zeige danach das zu Zeigende, indem du zunächst die Vollständigkeit von G ins Spiel bringst und danach ausnutzt, dass H ein von G induzierter Teilgraph ist.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:25 Mi 24.10.2012 | | Autor: | Lu- |
Danke, das hat richtig gut geholfen es so aufzuschreiben.
Vielen lieben dank ;)
|
|
|
|
