Graphentheorie

Neue Frage »

eppi1981 Auf diesen Beitrag antworten »
Graphentheorie
Sei ein schlichter Graph mit |E| = n Knoten, der aus m paarweise disjunkten Untergraphen für j =1,...,m besetzt.
Zeigen Sie, dass für die Menge K der Kanten des Graphen G die folgende Abschätzung gilt:


Kann mir jemanden helfen, ich habe keine Ahnung, wie das man zeigen kann.
AD Auf diesen Beitrag antworten »

Induktion über sieht vielversprechend aus.
 
 
eppi1981 Auf diesen Beitrag antworten »

kannst du bisschen genauer erklären?
AD Auf diesen Beitrag antworten »

Der Induktionsanfang sollte klar sein, da es in einem Graphen mit Knoten höchstens Kanten geben kann.


Tja, und dann der Induktionsschritt :

Da trennst du erstmal den Untergraphen mit Knoten ab und kannst für den Rest die Induktionsvoraussetzung nutzen, dann ergibt sich



Jetzt musst du dir nur noch überlegen,

(a) welche Werte für überhaupt nur in Frage kommen, und

(b) warum für all diese Werte der Ausdruck rechts in (*) ist,

dann ist der Induktionsbeweis vollbracht. Deutlicher kann ich nicht werden, also stell jetzt bitte erstmal keine Fragen mehr, sondern knie dich rein!
eppi1981 Auf diesen Beitrag antworten »

ein schlichter Graph hat
falls m=1



falls m=2


und das stimmt nicht unglücklich
AD Auf diesen Beitrag antworten »

Das stimmt in der Tat nicht, was du da geschrieben hast. Offenbar muss ich mich wiederholen:

Zitat:
Original von Arthur Dent
stell jetzt bitte erstmal keine Fragen mehr, sondern knie dich rein!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »