Einführung Graphentheorie

05.02.2013, 11:08

Silva

Auf diesen Beitrag antworten »

Einführung Graphentheorie

Meine Frage:
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.
$\begin{eqnarray*} \forall v,w \in V \exists \end{eqnarray*}$ Wanderung zwischen v und w.

Ich weiß
$\begin{eqnarray*} \sum_{v\in V(G)} d(v)= 2 * |E| \end{eqnarray*}$
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 Augenzwinkern

Augenzwinkern

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 $\begin{eqnarray*} v_1 , v_2 \end{eqnarray*}$ durch eine Kante verbunden-> G zusammenhängend.
Wären die zwei Knoten $\begin{eqnarray*} v_1 , v_2 \end{eqnarray*}$ nicht duch eine Kante miteinander verbunden: $\begin{eqnarray*} d(v_1) + d(v_2) \ge 2-1=1 \end{eqnarray*}$
D.h. mind einer der Knoten muss mit einer Kante inzidieren, und da bleibt nur die Kante $\begin{eqnarray*} \{v_1, v_2 \} \end{eqnarray*}$ übrig.-> Wid.

Induktionsvorrsetzung für n Knoten
Induktionsschritt: n+1 Knoten
Laut Induktionsvorrausetzung ist der induzierte Teilgraph $\begin{eqnarray*} G- v_{n+1} \end{eqnarray*}$ zusammenhängend.
Wenn $\begin{eqnarray*} v_{n+1} \end{eqnarray*}$ 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
traurig

traurig

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 »

Zitat:

Original von weisbrot
der "restgraph" G' (also der ausgangsgraph ohne k und mit k verbundene kanten) ist nach voraussetzung zusammenhängend.

Tatsächlich? Ich stutze ein wenig bei dieser Beweisführung, wenn ich an folgende Konstellation denke:

Nehmen wir mal an, für zwei Knoten $\begin{eqnarray*} v_1,v_2 \end{eqnarray*}$ aus dem Restgraph gilt "nur" $\begin{eqnarray*} d(v_1)+d(v_2) = n \end{eqnarray*}$ im $\begin{eqnarray*} (n+1) \end{eqnarray*}$ -Graph, und beide seien mit $\begin{eqnarray*} k \end{eqnarray*}$ verbunden, dann gilt im $\begin{eqnarray*} n \end{eqnarray*}$ -Restgraph (mit Knotenanzahlfunktion d') nur noch $\begin{eqnarray*} d'(v_1)+d'(v_2) = n-2 \end{eqnarray*}$ , womit die Induktionsvoraussetzung so nicht angewandt werden kann. Oder sehe ich da was falsch? verwirrt

verwirrt

P.S.: Ich hab nicht wirklich Ahnung von Graphentheorie, und bitte daher um Nachsicht, wenn ich was falsch interpretiert habe. Augenzwinkern

Augenzwinkern

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 $\begin{eqnarray*} \not\exists \end{eqnarray*}$ Kante von k' in G'
-> $\begin{eqnarray*} d(k)=0 \end{eqnarray*}$
Es gilt $\begin{eqnarray*} d(v_1)+..+d(k)+..+d(v_{n+1})\ge (n+1)-1 = n \end{eqnarray*}$
<=> $\begin{eqnarray*} d(v_1)+..+d(v_{k-1}) +d(v_{k+1})+..+d(v_{n+1})\ge (n+1)-1 = n \end{eqnarray*}$

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 »

Zitat:

P.S.: Ich hab nicht wirklich Ahnung von Graphentheorie, und bitte daher um Nachsicht, wenn ich was falsch interpretiert habe.

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 $\begin{eqnarray*} (n+1) \end{eqnarray*}$ -Graph sei nicht zusammenhängend, dann kann man diesen Graphen zerlegen in zwei disjunkte Graphen $\begin{eqnarray*} G_1 \end{eqnarray*}$ mit Knotenanzahl $\begin{eqnarray*} n_1 \end{eqnarray*}$ und $\begin{eqnarray*} G_2 \end{eqnarray*}$ mit Knotenanzahl $\begin{eqnarray*} n_2 \end{eqnarray*}$ , so dass $\begin{eqnarray*} 1\leq n_1\leq n, 1\leq n_2\leq n \end{eqnarray*}$ und $\begin{eqnarray*} n_1+n_2=n+1 \end{eqnarray*}$ 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. verwirrt

verwirrt

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, $\begin{eqnarray*} d(v_i) \ge n \end{eqnarray*}$
-> Wid da es nur n-1 Knoten gibt mit denen v_i induziert
so?
Also ist es doch auf eine Induktion herausgelaufen smile

smile

07.02.2013, 12:07

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von Silva
sei v_i ein beliebiger Knoten von die n Knoten, $\begin{eqnarray*} d(v_i) \ge n \end{eqnarray*}$
-> Wid da es nur n-1 Knoten gibt mit denen v_i induziert
so?

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:

Zitat:

Wenn man von einem zusammenhängenden Graphen mit n Knoten zu einem nicht-zusammenhängenden mit (n+1) Knoten übergeht [...]

wie meinst du das? so funktioniert jedenfalls induktion nicht.. verwirrt

verwirrt

@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 $\begin{align*} \{(k_m,k_l), k_m\in G_m, k_l\in G_l| G_m \ne G_l, G_i \small\text{ Teilgraphen}\} \end{align*}$ berücksichtigen. Insbesondere muss es Knoten $\begin{align*} k_1\in G_m \end{align*}$ und $\begin{align*} k_2\in G_l \end{align*}$ 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

$\begin{align*} d(k_1) \le |G_m| -1\land d(k_2)\le |G_l| -1 \end{align*}$

folgt

$\begin{align*} d(k_1)+d(k_2) \le |G_m| +|G_l| -2 < n \end{align*}$ ,

da $\begin{align*} |G_m| +|G_l| \le n +1 \end{align*}$ (das $\begin{align*} < \end{align*}$ bei mehr als zwei Zusammenhangskomponenten). Nach Voraussetzung soll für die Summe der Grade von allen diesen Paaren aber $\begin{align*} d(k_m) +d(k_l) \ge n \end{align*}$ 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

Zitat:

Original von RavenOnJ
Da der Grad eines Knotens höchstens gleich der um Eins verminderten Zahl der Knoten im zugehörigen Teilgraphen sein kann, also

$\begin{align*} d(k_1) \le |G_m| -1\land d(k_2)\le |G_l| -1 \end{align*}$

[...]

$\begin{align*} |G_m| +|G_l| \le n +1 \end{align*}$ (das $\begin{align*} < \end{align*}$ bei mehr als zwei Zusammenhangskomponenten)

ohne jeden Einsatz der Induktionsvoraussetzung. Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »