Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Graphentheorie Vollständige Induktion

Graphentheorie Vollständige Induktion

Universität / Fachhochschule

Sonstiges

Graphentheorie

Tags: Graphentheorie, Sonstig, Vollständig Induktion

JonSchnee aktiv_icon

21:18 Uhr, 28.11.2017

Sei

H = (E, K, φ)

ein schlichter, zusammenhängender Graph mit

| E | = n

.
Zeigen Sie:

H

ist genau dann ein Bau, wenn

H

genau

n - 1

Kanten besitzt.

Vor: Sei Graph

H = (E, K, φ)

schlicht, zusammenhängend mit

| E | = n

.
Behauptung:

(| E | = n) \land (| K | = n - 1) \Rightarrow H

ist Baum.

Induktions Basis:

(n = 1)

(| E | = 1) \land (| K | = 1 - 1) \Rightarrow H

ist Baum.
Eine Ecke alleine kann keine Kanten besitzten. Somit sind 0 Kanten richtig.

Induktions Annahme:

(n = k)

(| E | = k) \land (| K | = k - 1) \Rightarrow H

ist Baum.

Induktions Behauptung: (Gilt auch für

k + 1)

(| E | = k + 1) \land (| K | = k) \Rightarrow H

ist Baum.

Induktions Beweis:
Entferne diese Ecke und alle sie enthaltenen Kanten.
Der verbleibende Graph ist nach Induktionsvoraussetzung ein Baum.

Und weitere Schritte fallen mir nicht ein

: /

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

ermanus aktiv_icon

22:44 Uhr, 28.11.2017

Hallo,
ich sehe bei dir nirgendwo, dass du die Definition eines Baumes verwendest,
wie willst dann vorankommen.
Ist bei dir ein Baum definiert als zusammenhängender kreisfreier Graph?

JonSchnee aktiv_icon

22:53 Uhr, 28.11.2017

Jap, genau so ist er definiert :-D)

Definition:
Ein zusammenhängender Graph ist ein Baum, wenn er keine Kreise hat.

Bemerkung: Bäume sind schlichte Graphen.

ermanus aktiv_icon

23:03 Uhr, 28.11.2017

In der Induktionsbehauptung hast du stehen

∣ E ∣ = k + 1

als Teil der Prämisse,
dann kannst du doch nicht sagen: entferne diese (!) Ecke, welche denn ?
Damit bricht leider schon dein Beweisansatz zusammen. Wir müssen irgendwie
anders vorgehen ;-)

JonSchnee aktiv_icon

23:13 Uhr, 28.11.2017

Ich finde die Idee auch komisch, aber in der Vorlesungsfolie wird irgendwie damit ein Induktionsbeweis bewiesen und ein netter Herr von der "Mathe-Lernhilfe" schlug dieses Vorgehen auch vor

: /

ermanus aktiv_icon

23:23 Uhr, 28.11.2017

Also, ich denke, wir sollten die Ausgangslage des Induktionsschrittes
uns ganz klar vor Augen führen:
Es kommt jemand zu deinem Geburtstag und schenkt dir einen Graphen mit

k + 1

Ecken und

k

Kanten und du hast keine Ahnung, in welcher Reihenfolge dein
Gast dieses Gebilde zusammengebaut hat. Du weißt aber, dass ein solches Kunstwerk,
wenn es

k

Ecken und

k - 1

Kanten hat, ein Baum ist, also nach dem Auspacken nicht
aus einander fällt und auch keine Schlingen hat.
Das sind deine Voraussetzungen ...
Nun möchtest du gerne von den

k + 1

Ecken auf

k

Ecken herunterkommen, indem
du eine Ecke - sagen wir die Ecke

e

- wegnimmst und daher auch die mit dieser Ecke
verbundenen Kanten tilgst. Was für eine Eigenschaft soll denn so eine
Ecke haben ?

JonSchnee aktiv_icon

23:30 Uhr, 28.11.2017

Die Ecke darf nur eine Kante besitzen, was bei schlicht gegeben ist? :-D)

JonSchnee aktiv_icon

23:32 Uhr, 28.11.2017

Auch kann man sagen das diese Ecke nicht Mehrfachkantig ist?

ermanus aktiv_icon

23:39 Uhr, 28.11.2017

Wenn die Anzahl der Ecken größer ist als die der Kanten, muss es eine Ecke geben, in der
nur eine Kante endet. Genau, wie du denkst! Solch eine Ecke sei unser

e

.
Wenn wir nun

e

und die zugehörige Kante entfernen, kann der Graph dann zerfallen?
Wie ist die Anzahl der Ecken und Kanten nach der Entfernung?
Kann ich also nun meine Induktionsvoraussetzung einsetzen?
Ist nach Wiederhinzufügung von

e

und der gelöschten Kante ein Kreis entstanden?
Ist der Graph nun immer noch zusammenhängend?
Ist er infolgedessen ein Baum, also q.e.d. angesagt? ;-)

JonSchnee aktiv_icon

23:57 Uhr, 28.11.2017

Wenn die Anzahl der Ecken größer ist als die der Kanten, muss es eine Ecke geben, in der nur eine Kante endet. Genau, wie du denkst! Solch eine Ecke sei unser

e

.
Wenn wir nun

e

und die zugehörige Kante entfernen, kann der Graph dann zerfallen?
-Nein das "Ergebnis" ist vom "selben Typ"? Also die Behauptung bleibt wahr.

Wie ist die Anzahl der Ecken und Kanten nach der Entfernung?

- | E | = k

und

| K | = k - 1

kann durch Entfernen von Kanten ein Kreis entstehen?
- Nein weil eine Ecke und eine Kante entfernt wurden. (Verhältnis bleibt gleich?)

Wie groß ist die Anzahl der Ecken und Kanten nach der Entfernung?

- | E | = k

und

| K | = k - 1

Kann ich also nun meine Induktionsvoraussetzung einsetzen?
-Eigentlich ergibt sich daraus die Induktionsvorraussetzung, oder?

Ist nach Wiederhinzufügung von

e

und der gelöschten Kante ein Kreis entstanden?
-Nein, weil das Verhältnis immernoch gleich bleibt? Wenn es kein zusammenhängender Graph wäre, dann könnte man evlt einen Kreis bilden.

Ist der Graph nun immer noch zusammenhängend?
-Ja die Eigenschaft ist ja eine Vorraussetzung und wird nicht verändert.

Ist er infolgedessen ein Baum, also

q . e . d

. angesagt? ;-)
-Ja (Unter der Vorraussetzung kann es nie zu einem Kreis kommen, da durch die Vorrausetztungen "nur" gewährleistet wird das alle zusammenhängend sind.)

ermanus aktiv_icon

01:09 Uhr, 29.11.2017

Also hast du den "Induktionstest" bestanden. Ich denke, wir haben alle kritischen
Punkte damit ausgeräumt.

Gruß ermanus

JonSchnee aktiv_icon

18:20 Uhr, 29.11.2017

Danke, das war mir eine große Hilfe :-)

1402138

1401914

	Status: nicht eingeloggt	Noch nicht registriert?