 |
 |
 |
 |
 |
 |
Startseite » Forum » Komplement eines Baumes
Komplement eines Baumes
Universität / Fachhochschule
Algebraische Topologie
Tags: Algebraische Topologie, Baum, Graphentheorie, Komplement, zusammenhängender Graph
 
|
  |
|---|
|
Hallihallo, ich sitze jetzt schon einige Zeit bei einer Aufgabe, wo ich einfach nicht mehr weiterkomme und würde mich daher sehr freuen, wenn mir jemand von euch auf die Sprünge helfen könnte. Die Aufgabe lautet: Man bestimme (bis auf Isomorphie) alle Bäume, deren Komplement nicht zusammenhängend ist. - ich weiß, dass ein Baum mit Knoten immer Kanten hat - das Komplement hat somit immer Knoten und über Kanten Kann man aus dieser Information irgendwie schließen, wann das Komplement zusammenhängend ist und wann nicht, oder bin ich da ganz falsch? Weiters ist mir auch klar, dass, wenn beim Baum alle Kanten aus einem Punkt herauslaufen, das Komplement nicht zusammenhängend ist, aber das ist ja wahrscheinlich nur einer von vielen Fällen. Danke für die Mithilfe :-) Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, folgende Idee sollte dich weiterbringen: Sei ein Baum und der Komplementärgraph von . Nun sei nicht zusammenhängend und es seien und zwei Zusammenhangskomponenten von . Behauptung: eine der beiden Zusammenhangskomponenten besteht nur aus einem isolierten Knoten. Beweis: nehmen wir an, sowohl in als auch in gäbe es jeweils mindestens zwei Knoten, etwa und . Dann liegen die Kanten in . Diese vier Kanten bilden dann aber einen Kreis und somit wäre kein Baum: Widerspruch! Folgerung: wenn also der Komplementärgraph nicht zusammenhängend ist, bestehen alle seine Zusammenhangskomponenten bis auf eine aus jeweils nur einem isolierten Knoten. Hätte der Komplementärgraph nun mehr als 2 Komponenten, etwa und wären (i=1,2,3), dann lägen die Kanten in , wäre dann kein Baum. Wir konstatieren: besitzt genau 2 Zusammenhangskomponenten, deren eine nur aus einem Knoten besteht und die andere alle übrigen Knoten enthält. Damit kannst du alle Typen der gesuchten Bäume herleiten. Gruß ermanus |
 |
|
Vielen Dank für diese so ausführliche Antwort!! Nach meinem Verständnis muss der Baum dann so aussehen, dass es einen Knoten gibt, von dem aus lauter Blätter weggehen. Also zum Beispiel eine “Sonne“ wenn man sich die als Graphen vorstellt :-D) Ist das so richtig oder gibts noch andere Möglichkeiten? Gruß, Lisa |
|
|
|
Hallo Lisaa23, deine Strahlensonnen sind die einzigen Graphen, die die geforderte Eigenschaft haben: Denn da im Komplementärgraphen ja alle Kanten der isolierten Einknotenkomponente zu den Knoten der anderen Zusammenhangskomponente fehlen, sind diese Kanten alle Bestandteil des Baumes, der daher eine "Sonne" enthält. Mehr Kanten kann er aber auch nicht enthalten, da er sonst kein Baum mehr wäre. Damit ist deine Ursprungsvermutung voll und ganz bewiesen :-) |
 |
|
Vielen Dank!!! |
1454398
1454013