Beweise Graphentheorie |
| 28.06.2005, 03:00 | zygyzy | Auf diesen Beitrag antworten » |
| Beweise Graphentheorie 1. Sei G ein Graph mit n Knoten, m Kanten und c Zusammenhangskomponenten. Man zeige: m>=n-c Man gebe eine notwendige und hinreichende Bedingung dafür an, dass m=n-c ist. 2. Eine Menge von Knoten eines Graphen heisst unabhängig, wenn je zwei Knoten dieser Menge nicht durch eine Kante verbunden sind. Sei G ein Graph mit n Knoten, bei dem jeder Knoten eine Valenz (Grad) nicht grösser d hat. Zeige, dass es eine unabhängige Menge mit mindestens n/(d+1) Knoten gibt. 3. Zeige, dass für jeden paaren Graphen ohne isolierte Knoten gilt: Die grösste Anzahl von Knoten, die paarweise nicht durch eine Kante verbunden sind, ist gleich der kleinsten Anzahl von Kanten, mit denen man alle Knoten überdecken kann. P.S.: Ein Graph G=(V,E) heist paar, wenn es eine Zerlegung AuB (vereinigung) von V gibt, so dass alle Kanten von G genau einen Eckpunkt in A und einen Eckpunkt in B haben. Ein Knoten heisst isoliert, wenn keine Kante zu ihm incident ist. Hab echt keine Plan, und wäre für Hilfe wirklich dankbar. 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
