Schon wieder Graphen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:38 Fr 24.02.2006 | | Autor: | dump_0 |
Hallo nochmal, ich schon wieder.
Ich hänge leider bei einer Aufgabe fest die folgendermaßen lautet:
Es sei G ein einfacher Graph, in dem der kleinste vorkommende Knotengrad
[tex]\delta (G) \ge k[/tex] ist ([tex]k \in IN[/tex], und es sei T ein Baum mit [tex]k[/tex] vielen Kanten.
Zeigen Sie: G hat einen zu T isomorphen Teilgraphen.
Damit der Teilgraph isomorph zu T ist, müssen Kantenzahl, Knotenzahl und Gradsequenzen übereinstimmen.
Da [tex]\delta (G) \ge k[/tex] ist, muss es weitere Knoten in G geben mit mind. dem selbsten Knotengrad, die Kantenzahl und Knotenzahl ist damit ja schonmal erfüllt. Bei den Gradsequenzen weiß ich nicht so ganz wie ich das zeigen kann. Ich denke aber das der Lösungsweg ein anderer ist, auf den ich leider nicht komme :(
Ich würd mich über eure Hilfe freuen.
Mfg
[mm] dump_0
[/mm]
|
|
| |
|
Hallo Freunde gepflegter karnevalistischer Graphentheorie,
nimm doch einfach einen Beweis via Induktion nach k:
Ind.Anfang ist klar, also von k nach k+1:
Nimm einen Knoten von G, mappe ihn auf ein Blatt von T und einen bel. Nachbarn auf seinen Nachbarn in T. Dann loesche den Knoten und die entspr. Kante aus G, der verbleibende Restgraph hat Knotengrad [mm] \geq [/mm] k-1, und wir sehen, dass wir uber Induktion eigentlich folgende staerkere Aussage zeigen (typischerweise merkt man sowas erst waehrend des Beweises):
Geg. G und T wie in der Aufgabenstellung sowie ein Blatt t von T und ein Knoten v von G, dann gibt es einen zu T isom. Teilgraphen von G, bei dem
v auf t gemappt wird.
Närrische Grüsse und
bis Dienstag in alter Frische,
Mathias
|
|
|
|
