Graphen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:59 Mo 30.05.2005 | | Autor: | squeezer |
Hallo
Ich habe folgende Aufgabe zu bearbeiten:
$G = (V, E)$ sei ein Graph mit $n$ Ecken und $n-1$ Kanten ($n [mm] \ge [/mm] 2 $)
Zeigen Sie: Hat G keine isolierten Ecken, so enthällt $G$ mindestens zwei Ecken vom Grad 1.
Desweiteren sei G ein endlicher, ungerichteter Graph ohne Schlingen und Mehrfachkanten.
Ich hab keine Ahnung wie ich folgendes Beweisen könnte.
Vielen Dank für Ihre Hilfe
MfG
Marc
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:34 Di 31.05.2005 | | Autor: | Zyllyn |
na einfach über Induktion :)
hier die Idee
Du musst es wahrscheinlich noch deutlich sauberer aufschreiben, das war nie meine Stärke :)
n=2
zwei Ecken, eine Kante -> da gibts nur eine Möglichkeite -> keien isolierten Ecken, zwei Ecken mit Grad 1 -> Beh. stimmt
n -> n+1
damit die Beziehung n Ecken und n-1 Kanten erfüllt ist, muss mit jeder Ecke auch eine Kante zum Graphen hinzugefügt werden
1. Fall:
Die neu hinzugefügte Ecke gehört nicht zur neu hinzugefügten Kante -> eine isolierte Ecke mehr (Beh. stimmt)
interessant ist aber auch wo die Kante eingefügt wird
Fall 1a:
verbindet zwei Ecken mit Grad 0 -> zwei isolierte Ecken weniger, zwei Ecken mit Grad 1 mehr
insgesamt eine isolierte Ecke weniger, zwei Ecken mit Grad 1 mehr
Fall 1b:
verbindet eine Ecke mit Grad 0 mit einer vom Grad 1 -> eine isolierte Ecke weniger, eine mit Grad 1, eine mit Grad 2
insgesamt bleibt die Anzahl der isolierten Ecken und Ecken mit Grad 1 gleich
Fall 1c:
zwei Ecken mit Grad 1 -> zwei Ecken mit Grad 1 weniger
aber insgesamt auch eine isolierte Ecke mehr (die gerade eingefügte)
Fall 1d:
eine Ecke mit Grad 2 (oder mehr) mit isolierter Ecke -> eine isolierte Ecke weniger
insgesamt bleibt die Anzahl der isolierten Ecken gleich
Fall 1e:
eine Ecke mit Grad 2 (oder mehr) mit Ecke vom Grad 1 -> eine Ecke vom Grad 1 weniger
insgesamt eine Ecke vom Grad 1 weniger und eine isolierte Ecke mehr
Fall 1f:
zwei Eckem vom Grad 2 (oder mehr) -> keine änderung der islierten Ecken oder der Ecken vom Grad 1
insgesamt eine isolierte Ecke mehr
2. Fall:
Die neu hinzugefügte Ecke gehört zur neu hinzugefügten Kante:
Fall 2a:
hinzufügen an einer Ecke mit Grad 2 oder mehr -> Gesamtzahl der Ecken mit Grad 1 steigt um 1
Fall 2b:
hinzufügen an einer Ecke mit Grad 1 -> die neue Ecke hat den Grad 1 -> eine weniger mit Grad 1, eine mehr mit Grad 1, Gesamtzahl bleibt gleich
Fall 2c:
hinzufügen an einer Ecke mit Grad 0 -> zwei neue Ecken mit Grad 1 -> Gesamtzahl der Ecken mit Grad 1 steigt um 2, Anzahl isolierter Ecken sinkt um 1
zu zeigen sind quasi zwei Teile, entweder ich habe mindestens eine isolierte Ecke, oder mindestens zwei Ecken vom Grad 1
für n=2 haben wir gezeigt, dass die zweite Aussage stimmt
und bei der Analyse aller Möglichkeiten beim Hinzufügen von Ecke+Kante im Induktionsschritt wurde gezeigt, dass isolierte Ecke eingefügt werden (ggf. auf Kosten von Ecke mit Grad 1) aber nur wieder entfernt werden können durch einfügen von 2 Ecken mit Grad 1.
hmm nun ist es noch unübersichtlicher geworden als ich gedacht habe *g* naja vielleicht liefert dir ja das Durchlesen die notwendige Idee, ne mathematisch saubere Form ist es auf jeden Fall noch nicht :)
ach noch ne Nebenbemerkungen:
sobald einmal beim Hinzufügen Fall 1 gewählt wurde ist der Graph nicht mehr zusammenhängend (falls es noch weitere Teilaufgaben gibt :) )
|
|
|
|
