Kanten in einem Baum |
11.01.2010, 22:08 | Maria9988 | Auf diesen Beitrag antworten » | ||
Kanten in einem Baum also würde gern wissen ob ich bei folgender Aufgabe richtig liege: Sei G=(V,E) ein Baum. Zeigen sie:Für jede Kante e € E ist G \ e nicht zusammenhängend. Meine Lösung: E ist eine bestimmte menge genau so groß wie V.. wenn jedoch ein e € E nicht in G ist ist ein V nicht mit den anderen verbunden deswegen sollte es nicht zusammenhängend sein |
||||
11.01.2010, 22:11 | kiste | Auf diesen Beitrag antworten » | ||
Deine Lösung hört sich für mich an wie "weil es gilt, gilt es". Wie habt ihr Bäume definiert? |
||||
11.01.2010, 22:58 | Maria9988 | Auf diesen Beitrag antworten » | ||
also laut Definition im Skript: Ein Baum ist ein kreisfreier Graph. mehr steht da nicht wirklich Dann kommt nur noch die Definition eines Waldes und von Blättern. |
||||
11.01.2010, 23:06 | kiste | Auf diesen Beitrag antworten » | ||
Wirklich? Nicht irgendwie noch was mit zusammenhängend? |
||||
11.01.2010, 23:13 | papahuhn | Auf diesen Beitrag antworten » | ||
Spielt hier ja keine Rolle, oder? Wenn ers vorher nicht war, issers nachher auch nicht. |
||||
11.01.2010, 23:16 | Mystic | Auf diesen Beitrag antworten » | ||
Ich glaub, du siehst hier den Wald vor lauter Bäumen nicht... |
||||
Anzeige | ||||
|
||||
11.01.2010, 23:25 | kiste | Auf diesen Beitrag antworten » | ||
Naja egal, ignorieren wir die Tatsache gemäß papahuhn und machen eine Fallunterscheidung: 1.) Der "Baum" ist unzusammenhängend trivial 2.) Der Baum ist zusammenhängend: Wenn er nach dem Entfernen einer Kante uv immer noch zusammenhängend ist, so existiert ein Weg von u nach v. Damit hat davon ein ... existiert |
||||
12.01.2010, 10:25 | Maria9988 | Auf diesen Beitrag antworten » | ||
"Damit hat davon ein ... existiert" was meinst du damit? |
||||
12.01.2010, 11:13 | Mystic | Auf diesen Beitrag antworten » | ||
Er meint: Damit hat davor ein ... existiert. |
||||
12.01.2010, 11:27 | Maria9988 | Auf diesen Beitrag antworten » | ||
jetzt weiss ich was er meint danke |
||||
14.01.2010, 15:00 | mathematikus | Auf diesen Beitrag antworten » | ||
Ein Baum ist definiert als ein nichtleerer, kreisloser, zusammenhängender Graph G:=(V,E). Daher, wenn du eine Kante entfernst, erhöht sich durch die Definition die Zusammenhangskomponenten. Entfernst du eine Kante {u,v} € E, und der Graph ist immer noch zusammenhängend, so gibt es einen Weg von u nach v, so dass vorher ein Kreis existiert hat. Hier hast du einen Widerspruch zur Definition eines Baumes und bist fertig. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |