Graphentheorie [Diskrete Mathematik] |
| 21.11.2010, 17:04 | Fetterchefkoch | Auf diesen Beitrag antworten » |
| Graphentheorie [Diskrete Mathematik] Hallo zusammen, ich habe wieder einmail ein Problem mit meinen Aufgaben. Die Frage lautet: a) Zeigen Sie: Ein einfacher ungerichteter Graph ist genau dann nicht kreislos, wenn er mindestens eine Kante besitzt, die keine Brücke ist. b) Zeigen Sie: Ein Wald ist genau dann kein Baum, wenn existieren mit und so, dass kreislos ist. Meine Ideen: Teilaufgabe a) heisst doch eigentlich auch, Falls ein Graph nur Brücken hat ist er kreislos... Meine Idee wäre gewesen, dies mit einem Gegenbeweis oder sogar mit Induktion zu beweisen. Jedoch bin ich im beweisen, nett ausgedrückt, eine riesen Flasche. (Das die Behauptung stimmt ist klar, ich habe mir dies auch aufgezeichnet.) b) auch hier ist mir klar wie dies sein muss. Also es müssen immer einzelne Punkte einen Wald darstellen, denn sobald es ein Weg von v nach w existiert ist der Wald sofort ein Baum. Jedoch ist mir nicht klar, warum E geschnitten mit v und w ist und nicht der durchschnitt genommen wurde. Da ja die Edge 0 sein muss weil sonst sofort ein Baum entsteht. Meine Idee wäre eigentlich einen Induktionsbeweis zu führen. Jedoch habe ich keine Ahnung wie ich ihn in dieser Situation führen soll. Ich hoffe irgendjemand hat grad gecheckt, was ich damit sagen wollte. Jedenfalls schonmal danke im voraus 
|
||
| 21.11.2010, 19:09 | kiste | Auf diesen Beitrag antworten » |
Was ist eine Brücke? Aus dem Zusammenhang rate ich einmal eine Kante, die wenn man sie entfernt die Zusammenhangskomponente der Kante unzusammenhängend macht? b) Welche Definition von Baum benutzt ihr? Je nach Definition ergibt sich natürlich ein anderer Beweis |
||
| 21.11.2010, 21:30 | Fetterchefkoch | Auf diesen Beitrag antworten » |
Eine Brücke ist eine Kante, wenn man sie entfernt aus einem 2 Bäume macht. Wenn man also eine Kante entfernt aus einem Baum und es trotzdem ein Baum bleibt, heisst dies, das die Kante keine Brücke ist. Unser Baum ist so definiert, dass sobald eine Knoten eine Kante mit einem anderen Knoten hat ein Baum entsteht. |
||
| 21.11.2010, 21:46 | kiste | Auf diesen Beitrag antworten » |
Deine Definition von Brücke macht kaum Sinn, was wenn die Kante nicht in einem Baum ist? Und deine Definition von Baum ist auch recht komisch. Schau die genauen Definitionen bitte einmal nach |
||
| 21.11.2010, 22:39 | Fetterchefkoch | Auf diesen Beitrag antworten » |
ein Baum besteht minimal aus 2 Knoten und einer Kante. Jedoch kann es auch sein, dass ein Knoten nicht verbunden ist mit einem anderen Knoten. die Brücke ist eine Kante. da sobald es eine Kante in einem Graphen gibt, sofort ein Baum sein muss, existiert die möglichkeit gar nicht, dass eine Brücke nicht in einem Baum sein kann. Ich hoffe, dass das dir weiterhilft |
||
| 22.11.2010, 02:02 | kiste | Auf diesen Beitrag antworten » |
Das soll dir doch weiterhelfen. Ich weiß was ein Baum ist, du leider nicht 
Bei dir fehlt doch jegliche Bedingung die ein Baum erfüllen muss, du sagst lediglich dass es 2 Knoten und eine Kante geben muss, das erfüllen aber sehr viele Graphen. Tollerweise gibt es auch einen Baum mit nur einem Knoten 
Also jetzt nochmals die Bitte an dich: Schaue die wort-genaue(!) Definition von Baum in deinem Skript nach und gebe sie hier wort für wort wieder. Den Begriff der Brücke kann man folglich auch nicht so definieren wie du es gemacht hast, weil eben nicht alles Bäume sind. |
||
| Anzeige | ||
|
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
