Beweis bei Graphen |
| 06.05.2005, 09:49 | morbus | Auf diesen Beitrag antworten » | ||||
| Beweis bei Graphen ich soll in der Uni die folgenden Bewesie zum Thema Graphen führen und ich komm damit nicht wirklich klar 
1.) Mann soll zeigen, das wenn für Graph G=(V,E) gilt : der maximale Knotengrad in einem Graphen + dem minimalen Knotengrad in einem Graphen + 1 = die Anzahl der Knoten, dann ist G zusammenhängend. 2.) Man soll zeigen, das ein Graph genau dann bipartit ist, wenn er keinen Kreis ungerader Länge enthält. 3.) Man soll zeigen, das der komplementäre Graph eines nicht zusammenhängenden Graphen zusammenhänged ist. Also wenn ihr ne Idde habt, bitte helft, ich komm , wie gesagt, nicht wirklich weiter. Die einzige Idde hab ich bei 1., undzwar das man da vielleicht mit Kontraposition rangehn könnte. Also bitte bitte bitte helft 
|
||||||
| 06.05.2005, 12:16 | JochenX | Auf diesen Beitrag antworten » | ||||
hmm, frische uns doch bitte mal mit einigen dingen auf: was hieß noch mal bipartit? was ist ein komplementärer graph? zusammenhängend bedeutet, dass jeder punkt mit jedem verbunden ist, oder? hast du einen (un)gerichteten graphen?! |
||||||
| 06.05.2005, 12:23 | Sciencefreak | Auf diesen Beitrag antworten » | ||||
Also ich kann mit den beiden oberen egriffen auch nicht viel anfangen, aber bei mir ist zusammenhängend etwas anderes. Bei mir heißt das bloß, dass man jeden Knoten von jeden anderen Knoten ereichen kann und dass auch indirekte Verbindungen über andere Knoten zählen, ansonsten stelle ich mir auch die Aufgaben 1 und 3 als recht sinnlos vor Edit:Ich merk gerade, dass du es auch so gemeint haben kannst, aber deine Formulierung ist schon etwas komisch. Meine Überlegung zu komplementärer wären, dass dann jede Kante zu einer Nichtkante und jede Nichtkante zu einer Kante werden würde, aber ich habe überlegt und bin der Meinung, dass dann die Aussage von aufgabe 3 falsch ist, also kann das irgendwie nicht sein |
||||||
| 06.05.2005, 12:25 | JochenX | Auf diesen Beitrag antworten » | ||||
ja, genau das meinte ich auch mit "verbunden" sein, es gibt einen weg (belibige länge) zwischen ihnen. das war wirklich missverständlich ausgerückt. hätte bei komplementärer graph an den graphen gedacht, der genau die kanten hat, die der andere graph nicht hat.
das wäre sinnig, aber dann wäre c falsch. mfg jochen edit: sehr lieb sciencfreak, wir sind uns einig 
|
||||||
| 06.05.2005, 12:29 | Sciencefreak | Auf diesen Beitrag antworten » | ||||
Vielelicht kannst du ja etwas damit anfangen http://www.abbiseite.de/informatik/#36a Das ist eine Erklärung für komplementärer Graph Und hier eine Erklärung für Bipartiter Graph die sogar ich verstehe http://www.computerbase.de/lexikon/Bipartiter_Graph |
||||||
| 06.05.2005, 12:43 | JochenX | Auf diesen Beitrag antworten » | ||||
hmmmm, ja an bipartit erinnere ich mich jetzt wieder aus der infovorlesung. die aussage für den kompl. graphen bezüglich der kanten war auf jeden fall richtig. aber dafür benötigt man noch: "[...]ein vollständiger Graph[...]" das wiederum ist "ein schlichter Graph mit maximaler Anzahl der Kanten."..... das sollte auch unser gegenbeispiel widerlegen (das vermutlich bei beiden ähnlich aussah.) mfg jochen da ich das auch nur aus informatik (grundvorlesung 1) kenne und auch hier alles auf info veweist.... ist das übehaupt eine matheaufgabe? es gibt ja auch ein informatikerboard...... |
||||||
| Anzeige | ||||||
|
|
||||||
| 06.05.2005, 12:54 | Sciencefreak | Auf diesen Beitrag antworten » | ||||
Also ich würde Graphentheorie eher in die Mathematik einordnen und habe es dort auch kennengelernt(Infovorlesungen habe ich in meinem Alter noch nicht gehabt) Also zu Aufgabe 2 wäre der Teil mit jeder bipartit Graph enthält nur Kreise mit gerade Länge wäre ja noch einfach zu begründen, nur die andere Richtung bereitet mir noch Kopfzerbrechen |
||||||
| 06.05.2005, 13:02 | JochenX | Auf diesen Beitrag antworten » | ||||
die rückrichtung sollte mit konsekutivem zufügen der punkt nacheinander zu den mengen A und B (ich übernehme mal aus deinem Link) klappen.... man muss zeigen, dass man den punkt immer zu einer der mengen hinzufügen kann, solange es keine ungeraden kreise gibt.... is aber noch nicht ausgearbeitet der schritt.... edit: bissl komplizierter isses schon |
||||||
| 06.05.2005, 13:19 | Tobias | Auf diesen Beitrag antworten » | ||||
Zu 1.) Nimm an, dass dein Graph mindestens zwei Zusammenhangskomponenten hat aber die Bedinung noch gilt. Aus deinen Zusammenhnagskomponenten pickst du dir nun zwei raus: G1 hat am meisten Ecken unter allen Zshkmp und G2 am wenigsten. Damit kannst du ein paar sehr nützliche Abschätzungen machen: Ecken von G1 + Ecken von G2 <= Ecken von G Maximalgrad von G <= Ecken von G1 - 1 Minimalgrad von G <= Ecken von G2 - 1 Damit lässt sich dann ein Widerspruch konstruieren. Zu 2.) Stellen wir uns vor, es gäbe einen Kreis ungerader Länge. Die an diesem Kreis partizipierenden Ecken müssen wir in zwei Mengen partitionieren, so dass in einer Menge keine zwei Ecken sind, die zueinander adjazent sind. Das ist aber bei einem Kreis ungerader Länge nicht möglich, denn hat ein Kreis n Ecken, dann sind unter jeder Auswahl von (mehr als) ObereGauß(n/2) Ecken mindestens zwei adjazent. Zu 3.) G ist nicht zusammenhängend. D.h. es existieren Zusammenhangskomponenten G1, G2, ..., Gs (mindestens 2). Im komplementären Graph ist jede Ecke aus Komponente Gi mit jeder Ecke aus Komponente Gj (für alle i != j) verbunden. Damit ist der Graph zusammenhängend, denn 1. Fall: Zwei Ecken v, w liegen in unterschiedlichen Zusammenhangskomponenten => Im komplementären Graph sind sie durch eine Kante verbunden. => Es gibt einen Weg zwischen v und w 2. Fall: Zwei Ecken v, w liegen in der gleichen Zusammenhangskomponente. => Gehe im komplementären Graph von v zu einem Knoten z aus der zuvor anderen Zusammenhangskomponente und gehe dann von z nach w (denn z und w lagen zuvor auch in anderen Zusammenhangskomponenten). Damit ist der komplementäre Graph zusammenhängend. |
||||||
| 06.05.2005, 13:21 | Sciencefreak | Auf diesen Beitrag antworten » | ||||
Das kann morbus ja dann machen. Hast du eine Idee mit 3.? Mit Begriffen kenne ich mich bei der Graphentheorie noch nicht so aus, denn ich habe das alles innerhalb von 2 Schulstunden erzählt bekommen und das dort ging eher in eine andere Richtung. Und komme immer noch nicht zurecht mit der Definition vom komplimentären Graphen, aber ich habe jetzt keine Lust da irgendwie was dran zu ändern. |
||||||
| 06.05.2005, 23:28 | morbus | Auf diesen Beitrag antworten » | ||||
Hi Leute, erstmal großes Danke für die vielan Antworten. Ich erkläre nochmal schnell die Begriffe. Zusammenhängend : Ein Graph G heißt zusammenhängend, wenn je 2 Knoten in G durch einen Kantenzug verbunden sind. Und wenn man eine Kante aus dem Graphen entfernt, zerfällt der Graph in 2 Teilgraphen (Zusammenhangskomponenten) und es gibt nicht mehr für alle je 2 Knoten einen Kantenzug. bipartit : Die defenition ist ziemlich trocken. Im grunde kann man sagen, wenn du die Knoten so fäbren kannst, das je ein roter Knoten einen grünen als nachbar hat und umgekehrt, ohne das ein Roter einen roten oder ein Grüner einen grünen als NAchbar hat, dann ist G bipartit. komplementärer Graph : Das ist ein Graph, beim dem sich die Knotenmenge V nciht verändert , jedoch die Kantenmenge alle Kanten enthält, die in der ürsprünglichen Kantenmenge nicht enthalten sind. Danke danke nochmal ! |
||||||
| 06.05.2005, 23:43 | Tobias | Auf diesen Beitrag antworten » | ||||
Nicht unbedingt. Eine Kante, die in keinem Kreis vorkommt nennt man Brücke. Und wenn man eine Brücke aus einem Graphen entfernt, zerfällt der Graph in mehrere Zusammenhangskomponenten und ist dann nichtmehr zusammenhängend. Das ist aber nicht bei jeder Kante der Fall.
Wenn man einen Graphen (V, E) hat und der vollständige Graph (d.h. der schlichte Graph, der ein Maximum an Kanten hat) sei (V, E'), dann ist der komplementäre Graph definiert als (V, E'\E). D.h. im Komplement sind zwei Ecken genau dann adjazent, wenn sie im Graph nicht adjazent waren. Schön, dass sich hier auch Leute noch mit Graphentheorie beschäftigen. Das ist übrigens sehr gut im Bereich Mathematik aufgehoben.
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
