2 dokaza

[ivanzub]

da li bi netko mogao dokazati ova 2 korolara s predavanja (moze malo detaljnije posto je jedan od dokaza bio u proslogodisnjem kolokviju)

1. suma stupnjeva vrhova grafa je paran broj.

2. broj vrhova s neparnim stupnjem je paran.

[Luuka]

1. Slijedi direktno iz teorema da je

lijevo je paran broj, pa je i desno.

2. Tu se malo raspiše formula iz teorema tj razbije se V(G) na one sa parnim stupnjem i one s neparnim, tj V(G) = Vp U Vn pa je



Prva suma je parna jer sadrži samo parne sumande, pa onda i druga suma mora biti parna da bi sve skupa bilo parno. (2E(G) je parno) pa pošto je to suma neparnih brojeva (vidi kak smo razbili V(G) ) slijedi da tih vrhova mora biti paran broj (suma neparnih je parna akko ima parno sumanada, lako provjerit a i dokazat)

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[ivanzub]

hvala..

[betty]

da ne otvaram novu temu..

imam samo jedno malo pitanjce.. u dokazu kod deranžmana na predavanjima, u onom dijelu kad objašnjava kako smo došli zapravo do te rekurzivne formule
d(n)-nd(n-1) = -(d(n-!) - (n-1)d(n-2))=...= (-1)^n-2 (d(2)- 2d(1)) = (-1)^n
zanima me jel tu stvarno taj n-2 ili možda treba n-1

[darkangel]

Meni isto pise n-2...

[Ančica]

To ti je dobro, vidi se po tome kad si prvi put koristila - i onda gledas koliko puta si ga koristila, a i jer na kraju dobijes (-1)^n sto je jednako (-1)^(n-2).. tako da to mora ici tako, nadam se da si ista od ovoga skuzila

_________________
..a jooooooj..

[betty]

kako bi išao dokaz da primov algoritam generira razapinjuće stablo minimalne težie:?: