Kantenmenge/Knotenmenge Beweis |
| 08.11.2010, 10:40 | fanta90 | Auf diesen Beitrag antworten » |
| Kantenmenge/Knotenmenge Beweis ich habe folgende Aufgabe: Wir betrachten ungerichtete Graphen G = (V;E) mit Knotenmenge V und Kantenmenge E. Zeigen Sie: Jeder Graph G = (V;E), für den |E| >= |V| gilt (d.h. es gibt mindestens so viele Kanten wie Knoten) enthält einen Kreis. Also was eine Knoten-/Kantenmenge ist weiß ich. Jedoch habe ich leider keine Ahnung wie ich zeigen soll das G = (V;E) einen Kreis enthält. Kann mir jemand einen Tipp geben? Danke im vorraus. MfG fanta90 |
||
| 08.11.2010, 11:29 | Huggy | Auf diesen Beitrag antworten » |
| RE: Kantenmenge/Knotenmenge Beweis Zunächst mal sollte klar sein, dass es genügt, den Beweis, für zusammenhängende Graphen zu führen. Einen zusammenhängenden Graphen kann man schrittweise so aufbauen: Man beginnt mit der Knotenmenge und einer beliebigen Kante. Dann fügt man jeweils eine Kante hinzu mit der Bedingung, dass einer ihrer Endknoten schon mit einer Kante verbunden ist. Das geht, weil der Graph zusammenhängend ist. Jetzt betrachtet man bei jedem Schritt die Menge der Knoten, die schon durch Kanten verbunden sind und die Menge der hinzugefügten Kanten. Im ersten Schritt sind 2 Knoten durch eine Kante verbunden. Das heißt, die Knotenmenge ist größer als die Kantenmenge. Das bleibt bei jedem weiteren Schritt so, es sei denn, die neue Kante verbindet 2 Knoten, die beide schon mit Kanten verbunden sind. Dann hat man aber einen Kreis erzeugt. |
||
| 08.11.2010, 11:50 | fanta90 | Auf diesen Beitrag antworten » |
vielen dank für deine antwort dass es ein kreis werden muss weiß ich und wieso auch aber ich weiß nicht wie ich das matematisch darstellen soll es gibt 5 punkte auf diese aufgabe und ich vermute dass da mehr als ein aufsatz verlangt ist. der kleinste zusammenhängende graph ist ja G=(V,E) wobei E= V-1 ist jede weitere kante führt zum kreis aber kann ich das mathematisch ausdrücken? und wenn ja wie |
||
| 08.11.2010, 12:12 | Huggy | Auf diesen Beitrag antworten » |
Wie der Beweisweg inhaltlich aussehen könnte, habe ich dir aufgezeigt. Ich habe natürlich keine Ahnung, wie formal dein Beweis aussehen muss. Es sollte aber zumindest kein Problem sein, die nach jedem Schritt vergebene Knotenmenge mit zu bezeichnen und die vergebene Kantenmenge mit . Dann zeigt man es sei denn, ein Kreis wurde erzeugt. P.S. Ich bin immer wieder erstaunt, wie oft der Einwand kommt, ich verstehe das, aber wie zeige ich das formal? Der Kern eines Beweises ist ein Gedanke! Wie man diesen Gedanken formal darstellt, hängt davon ab, welche formalen Hilfsmittel einem zur Verfügung stehen. Die Devise sollte aber sein, erst denken, dann formalisieren. P.P.S. Ich habe Null Ahnung von formaler Graphentheorie. Aber ich denke, ich kann ein wenig denken. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
