 |
 |
 |
 |
 |
 |
Startseite » Forum » Frage zu planare Graphen
Frage zu planare Graphen
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Hallo ich habe eine Frage zu planare Graphen, also ein Graph ist ja planar, wenn man ihn in der Ebene, ohne dass sich Kanten überschneiden, zeichnen kann. Ok ich soll beweisen, dass jeder Baum ein planarer Graph ist. Also eigentlich ist das offensichtlich, aber wie argumentiert man das am besten? Und... Was ist die kleinste nötige Anzahl von Farben zum gültigen Färben eines planaren Graphen? Warum? Hmm, ist ein Graph mit einem Knoten kein planarer Graph? Falls doch, brauch ich doch nur eine Farbe oder? LG Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, ich müsste mir eine geeignete Formalisierung für "planar" noch anschauen, aber mir erscheint eine Induktion sehr geeignet. Bedenke, entfernst du ein Blatt (Grad 1), so bleibt ja immer noch ein Baum übrig. Mfg MIchael |
 |
|
Mir ist grad noch was anderes eingefallen zur ersten Frage. Ein Graph ist ja genau dann planar wenn er keinen Teilgraph enthält der isomorph zu einem Unterteilungsgraph von K5 oder oder K3,3 ist. Ein Baum kann nie einen K5 oder K3,3 als Teilgraphen enthalten, sonst wäre der Baum zyklisch. Daraus folgt, dass jeder Baum planar ist. Oder? |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1316312
1316309