Minor, Unterteilungen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1) Sei G ein Graph, sodass [mm] K_{5} [/mm] ein Minor von G ist. Zeigen Sie, dass G dann eine Unterteilung von [mm] K_{5} [/mm] oder von [mm] K_{3,3} [/mm] enthält
2) Sei G ein Graph und H ein Minor von G mit [mm] \Delta(H)\le3 [/mm]
Zeigen Sie, dass G eine Unterteilung von H enthält. |
Hallo!
Also irgendwie weiß ich ja nicht so genau, wie ich an diese Aufgaben rangehen soll...
Mmmh, ein Minor entsteht ja durch Kantenkontraktion aus einem Teilgraphen. Ist es etwa so, dass ein [mm] K_{5} [/mm] nur aus einer Unterteilung des [mm] K_{5} [/mm] oder des [mm] K_{3,3} [/mm] entstehen kann? Wenn H weder Unterteilung vom einen noch vom anderen ist, warum kann [mm] K_{5} [/mm] kein Minor sein?
Wie ist das bei 2)? Wenn der Maximalgrad kleiner gleich drei ist, könnte man zunächst ja auch denken, dass H aus einer Unterteilung von H entsteht, aber das ist nicht so, wenn man mal ein Beispiel betrachtet, der [mm] K_{4} [/mm] ist Minor von so einem 3x3-Gittergraph, man kontrahiert den ganzen Graphen Stück für Stück, aber eine Unterteilung vom [mm] K_{4} [/mm] ist es, wenn man so eine mittlere Kante rauslässt...
Wie also findet man da eine Unterteilung von H? Indem man vielleicht Kanten entfernt aus dem Teilgraphen von G aus dem H entsteht?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Fr 08.07.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
