Diskrete Mathematik < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:20 Fr 09.06.2006 | | Autor: | Sunny85 |
| Aufgabe | | Gibt es einen einfachen Graphen mit 7 Knoten, der nicht zusammenhängend ist und bei dem der Grad eines jeden Knotens mindestens gleich drei ist? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich weiß, das es keinen Graphen dieser Art gibt. Ich habe dieses an Beispielen ausprobiert, aber wie soll ich das begründen? Bedeutet mindestens gleich drei, dass es auch Knoten mit einem Grad von 1 und 2 geben kann?
|
|
| |
|
Hallo!
> Gibt es einen einfachen Graphen mit 7 Knoten, der nicht
> zusammenhängend ist und bei dem der Grad eines jeden
> Knotens mindestens gleich drei ist?
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Ich weiß, das es keinen Graphen dieser Art gibt. Ich habe
> dieses an Beispielen ausprobiert, aber wie soll ich das
> begründen? Bedeutet mindestens gleich drei, dass es auch
> Knoten mit einem Grad von 1 und 2 geben kann?
Nein, mindestens gleich 3 bedeutet, dass alle Knoten Grad 3 oder Grad 4 oder Grad 5 oder... hat. Also halt "mindestens" Grad 3 und nicht weniger.
Wenn es kein formaler Beweis sein muss, sondern nur eine Begründung, würde ich das folgendermaßen begründen: Damit jeder Knoten mindestens Grad 3 hat, muss man mindestens vier Knoten haben. Denn bei zwei Knoten gäbe es nur eine einzige Kante und somit hätten beide Knoten nur Grad 1, bei drei Knoten kann es maximal drei Kanten geben, und dann hat jeder Knoten genau Grad 2. Also brauchst du mindestens vier Knoten.
Wenn du nun schon vier Knoten benutzt hast, bleiben von den insgesamt sieben nur noch drei übrig (du sollst ja einen nicht zusammenhängenden Graphen finden), und für diese gilt eben wieder nur, dass die Knoten maximal Grad zwei haben können. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo und guten Morgen,
die Antwort von Bastiane erlaube ich mir mal noch etwas allgemeiner zu formulieren:
Sei n die Knotenzahl, d der Minimalgrad, dann ist die Frage, ob wir [mm] n=n_1+n_2 [/mm] schreiben können mit
[mm] n_1\cdot d\slash [/mm] 2 [mm] \leq \frac{n_1\cdot (n_1-1)}{2},
[/mm]
[mm] n_2\cdot d\slash [/mm] 2 [mm] \leq \frac{n_2\cdot (n_2-1}{2}
[/mm]
Dann siehst Du für n=7, dass oE [mm] n_1\leq [/mm] 3 gelten muss und bekommst für d=3 also die Antwort ''nein''.
Schreiben wir die obere Ungl. nochmal hin:
[mm] n_1^2\: [/mm] - [mm] (d+1)n_1\geq [/mm] 0, also
[mm] n_1(n_1-d-1)\geq [/mm] 0, und analog also
[mm] (n-n_1)(n-n_1-d-1)\geq [/mm] 0
d.h.
[mm] n_1\geq [/mm] d+1
[mm] n-n_1\geq [/mm] d+1
und wir sehen: Das geht für [mm] n\geq [/mm] 2d+2. 
Gruss,
Mathias
|
|
|
|
