| Autor |
Beitrag |
    
Telefonmann
| | Veröffentlicht am Donnerstag, den 07. Dezember, 2000 - 08:19: | 
|
Sei G einGraph mit n Knoten,m Kanten und c Zusammenhangskomponenten.
(a)Man zeige:m >(gleich)n-c
(b)Man gebe eine notwendige und hinreichende Bedingung dafür an ,daß m=n-c ist |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 07. Dezember, 2000 - 19:28: |
|
Hallo Telefonmann,
eine Zusammenhangskomponente aus ni Knoten hat mindestens ni-1 Kanten.
Wenn also G aus c Zusammenhangskomponenten mit jeweils ni Knoten besteht, dann hat jede davon mindestens ni-1 Kanten.
Die Mindestzahl der Kanten in G ist also Sc i=1 ni-1 = n -c. Die Summe der ni ist nämlich gleich n, die Zahl der Knoten in G ist n und jeder Knoten liegt in genau einer Zusammenhangskomponente.
Wenn m=n-c, genau dann, wenn es in G keine Kreise gibt. Ein Graph ohne Kreise ist ein sog. Wald.
Gruß
Matroid |
Telefonmann
| | Veröffentlicht am Samstag, den 09. Dezember, 2000 - 21:17: |
|
Alles klar! |
|
