Wald: max. Anzahl von Kanten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:20 Do 16.06.2011 | | Autor: | user0009 |
Hallo!
Stimmt die Aussage: Jeder Wald mit n Knoten besitzt n-1 Kanten?
Aus meiner Sicht sollte es schon stimmen, denn ein Baum ist ja ein Wald und dieser hat max. n-1 Kanten. Außerdem kann es ja keinen Wald geben, der mehr Kanten als Knoten hat, wenn er azyklisch sein soll.
Danke und lg user0009
|
|
| |
|
> Hallo!
>
> Stimmt die Aussage: Jeder Wald mit n Knoten besitzt n-1
> Kanten?
Nein. So stimmt sie nicht.
Du hast die Aussage hier aber falsch wiedergegeben.
Es fehlt doch hier das "maximal", oder ?
> Aus meiner Sicht sollte es schon stimmen, denn ein Baum ist
> ja ein Wald und dieser hat max. n-1 Kanten. ![[haee]](/images/smileys/haee.gif "[haee]")
Letztere Aussage ist doch die, die du beweisen solltest.
Also darfst du sie bestimmt nicht im Beweis verwenden !
> Außerdem kann
> es ja keinen Wald geben, der mehr Kanten als Knoten hat,
> wenn er azyklisch sein soll.
Du musst einen klaren Beweis liefern. Der könnte etwa
so beginnen:
Sei W ein Wald mit n Knoten und e Kanten, [mm] k\in\IN [/mm] die
Anzahl seiner Komponenten (Einzelbäume), [mm] v_i [/mm] die
Anzahl Knoten und [mm] e_i [/mm] die Anzahl Kanten der i-ten
Komponente. Dann gilt:
$\ e\ =\ [mm] \summe_{i=1}^{k}e_i\ [/mm] =\ ....\ =\ ....\ [mm] \le [/mm] n-1$
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:56 Fr 17.06.2011 | | Autor: | user0009 |
Ja das max. hat gefehlt.
Danke, dass heißt meine Überlegung war korrekt.
Danke und lg
|
|
|
| |
|
Also: Ein Baum mit n Knoten und k Komponenten
hat n-k Kanten, und wegen [mm] k\ge1 [/mm] ist dann [mm] n-k\le{n-1}
[/mm]
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:43 Fr 17.06.2011 | | Autor: | felixf |
Moin Al,
> Also: Ein Baum mit n Knoten und k Komponenten
du meinst Wald und nicht Baum :)
LG Felix
|
|
|
| |
|
> du meinst Wald und nicht Baum :)
oh je ...
wieder mal den Wald hinter dem Baum nicht gesehen ...
warum schreiben die Finger manchmal etwas anderes
als das, was man offensichtlich gemeint hat ?
LG Al
|
|
|
|
