Einführung Graphentheorie |
05.02.2013, 11:08 | Silva | Auf diesen Beitrag antworten » | ||
Einführung Graphentheorie Sei G ein einfacher Graph(=ohne SChlingen und ohne mehrfache Kanten) mit n Knoten, und sei für je zwei Knoten v_1 , v_2 , die nicht durch eine Kante verbunden sind, die Summe ihrer Grade mindestens n-1. Zeige :G ist zusamennhängend Meine Ideen: G zusammenhängend <=> Wenn je zwei Knoten von G durch eine Wanerung(Knotenfolge bzw Kantenzug) miteinander verbunden sind. Wanderung zwischen v und w. Ich weiß wobei E die Kanten bezeichnet. Ich komme nicht wirklich weiter.. |
||||
05.02.2013, 12:46 | weisbrot | Auf diesen Beitrag antworten » | ||
RE: Einführung Graphentheorie du kannst einfach induktion über n machen, und dann, ja.. ist eigendlich nicht schwer, versuch mal lg |
||||
05.02.2013, 13:35 | Silva | Auf diesen Beitrag antworten » | ||
Der Fall n=1 denke ich mir ist eine definitionssache bzw. zu degeneriert? n=2 Sind die zwei Knoten durch eine Kante verbunden-> G zusammenhängend. Wären die zwei Knoten nicht duch eine Kante miteinander verbunden: D.h. mind einer der Knoten muss mit einer Kante inzidieren, und da bleibt nur die Kante übrig.-> Wid. Induktionsvorrsetzung für n Knoten Induktionsschritt: n+1 Knoten Laut Induktionsvorrausetzung ist der induzierte Teilgraph zusammenhängend. Wenn mit jeden Knoten verbunden ist über eine Kante wären wir fertig . Nun hatten ich paar sachen versucht es aber nicht hinbekommen. Ist hier eine Fallunterscheidung notwendig? Ich weiß nicht so recht Ich glaub ich denke da zu kopliziert? |
||||
05.02.2013, 14:13 | weisbrot | Auf diesen Beitrag antworten » | ||
anfang bei n=1 reicht, und das ist auch klar (und nicht definitionssache), denn der grad des einzigen knotens ist 0=1-0, also ok. im ind.schritt. nimmst du dir einen solchen graphen G mit n+1 knoten. aus denen pickst du dir einen raus (nennen wir k). der "restgraph" G' (also der ausgangsgraph ohne k und mit k verbundene kanten) ist nach voraussetzung zusammenhängend. jetzt gilt es nur noch zu zeigen, dass es eine kante von k in G' gibt. das kannst du z.b. übern widersruch zeigen, dabei musst du natürlich die vorausgesetzte eigenschaft von G benutzen. lg |
||||
05.02.2013, 14:26 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Tatsächlich? Ich stutze ein wenig bei dieser Beweisführung, wenn ich an folgende Konstellation denke: Nehmen wir mal an, für zwei Knoten aus dem Restgraph gilt "nur" im -Graph, und beide seien mit verbunden, dann gilt im -Restgraph (mit Knotenanzahlfunktion d') nur noch , womit die Induktionsvoraussetzung so nicht angewandt werden kann. Oder sehe ich da was falsch? P.S.: Ich hab nicht wirklich Ahnung von Graphentheorie, und bitte daher um Nachsicht, wenn ich was falsch interpretiert habe. |
||||
05.02.2013, 14:40 | Silva | Auf diesen Beitrag antworten » | ||
Ja "fast" dasselbe stand in meinen Versuch. Aber du nimmst einen beliebigen Knoten, Ich hatte vorher gedacht dass ich den bestimmten Punkt den ich neu dazu gebe auch verwenden muss Ang Kante von k' in G' -> Es gilt <=> Aber da bekomme ich keinen Widerspruch, sondern sogar eine wahre Aussage.Da jeder Grad mind 1 sein muss |
||||
Anzeige | ||||
|
||||
05.02.2013, 15:05 | weisbrot | Auf diesen Beitrag antworten » | ||
dito. ja danke, du hast natürlich recht, mein gedanke war völlig falsch, das tut mir leid silva. eine induktion auf diese weise sieht doch ziemlich fruchtlos aus.. zumindest sehe ich grad nicht wie man das reparieren könnte. da muss ich nochmal drüber nachdenken. währenddessen ist es jemandem, der eine guten beweis hat, freigestellt den thread zu übernehmen. lg |
||||
05.02.2013, 15:21 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ich würde den Induktionsschritt eher indirekt aufziehen: Angenommen, der -Graph sei nicht zusammenhängend, dann kann man diesen Graphen zerlegen in zwei disjunkte Graphen mit Knotenanzahl und mit Knotenanzahl , so dass und gilt. Das scheint man dann ziemlich einfach auf einen Widerspruch führen zu können. P.S.: "Übernehmen" will ich aber nicht. EDIT: Hmm, Induktion braucht man dann eigentlich gar nicht mehr. |
||||
07.02.2013, 09:11 | Silva | Auf diesen Beitrag antworten » | ||
Hallo HAL 9000 WO siehst du da einen Widerspruch? ich wüsste nämlich nicht wie man die Vorrausetzung hier anwenden sollte. LG |
||||
07.02.2013, 11:10 | RavenOnJ | Auf diesen Beitrag antworten » | ||
Wenn man von einem zusammenhängenden Graphen mit n Knoten zu einem nicht-zusammenhängenden mit (n+1) Knoten übergeht, dann ist der neue Knoten offensichtlich isoliert, hat also Grad 0. Jetzt muss aber nach Voraussetzung die Summe der Grade dieses Knotens und irgendeines beliebigen anderen Knotens größer oder gleich n sein. Daraus resultiert ein Widerspruch. |
||||
07.02.2013, 11:52 | Silva | Auf diesen Beitrag antworten » | ||
Hallo, Ich hab ein Detail die ganze Zeit falsch verstanden. ABer es steht ja JE zwei Knoten , die nicht durch Kanten verbunden sind. Ich habe immer gedacht ich muss alle aufsummieren.DANKE RavenOnJ, sei v_i ein beliebiger Knoten von die n Knoten, -> Wid da es nur n-1 Knoten gibt mit denen v_i induziert so? Also ist es doch auf eine Induktion herausgelaufen |
||||
07.02.2013, 12:07 | RavenOnJ | Auf diesen Beitrag antworten » | ||
Ich verstehe nicht genau, was du da meinst. Der Widerspruch resultiert daraus, dass alle Knoten (es reicht eigentlich einer) des zusammenhängenden Graphen der letzten Induktionssstufe den Grad n haben müssen. Dies ist aber nicht möglich, da dieser nur n Knoten hat, also die Knoten höchstens Grad (n-1) haben können. |
||||
07.02.2013, 12:09 | Silva | Auf diesen Beitrag antworten » | ||
Genau das steht in meinen beitrag nur hast du es in worten formuliert.. |
||||
07.02.2013, 15:45 | weisbrot | Auf diesen Beitrag antworten » | ||
@ravenonj:
wie meinst du das? so funktioniert jedenfalls induktion nicht.. @silva: ich würde doch versuchen zu verstehen, wie hal das gemeint hat! du kannst das wirklich einfach gleich über kontraposition (oder widerspuch, wie du willst) zeigen. geh halt davon aus, dass ein graph G nicht zusammenhängend ist - dann hat er mind. zwei disjunkte (und eben nicht verbundene) untergraphen; dann betrachte die summe der grade von je einem knoten aus dem einen und aus dem anderen untergraph. lg |
||||
07.02.2013, 16:54 | RavenOnJ | Auf diesen Beitrag antworten » | ||
@weisbrot Hast recht. Also anders: Die Aussage sei unter der genannten Voraussetzung für alle Graphen mit weniger als (n+1) Knoten bewiesen. Man betrachte nun einen Graphen mit (n+1) Knoten, der nicht zusammenhängend sei. Da alle zusammenhängenden Teilgraphen weniger als (n+1) Knoten haben und die Aussage damit für alle Knotenpaare, die zur selben Zusammenhangskomponente gehören, gilt, muss man nur Knotenpaare aus zwei nicht zusammenhängenden Teilgraphen betrachten. Da es keinen Pfad zwischen Knoten von nicht zusammenhängenden Teilgraphen geben kann, muss man alle Paare berücksichtigen. Insbesondere muss es Knoten und geben, für die die Gradsumme minimal ist. Da der Grad eines Knotens höchstens gleich der um Eins verminderten Zahl der Knoten im zugehörigen Teilgraphen sein kann, also folgt , da (das bei mehr als zwei Zusammenhangskomponenten). Nach Voraussetzung soll für die Summe der Grade von allen diesen Paaren aber gelten. Dies ist ein Widerspruch. Unter den Voraussetzungen muss der Graph also zusammenhängend sein. |
||||
07.02.2013, 17:02 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Genau. Und wenn wir uns den Beweis sorgfältig anschauen, dann brauchen wir die Induktionsvoraussetzung nicht wirklich: Denn die wirklich benötigten Argumente sind die hier
ohne jeden Einsatz der Induktionsvoraussetzung. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|