cayley-ev tm

[matijaB]

teorem 3.2.5 u skripti...
kuzim sve do....broj surjekcija s (n-2) u n-člani skup je 0.....i onda slijedi formula i sve je ocito...e kad bi mi neko pomogao s tim ocitim?
hvala

[krcko]

Sjeti se formule za broj surjekcija s m-clanog na n-clani skup. Ubaci m=n-2, izjednaci s nulom i dobit ces istu formulu kao kad n^(n-2) uvrstis u rekurziju. Sad znamo da je formula istinita, dakle niz zadovoljava rekurziju, dakle teorem vrijedi.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[matijaB]

jos malo teorije
u dokazu Oreovog tm-a za hamiltonove cikluse....zasto je |A U B| <= n-1 ?


|AUB| = |A|+|B|-|A presjek B|
moze malo pojasnjenje sta je zapravo skup B ?

[krcko]

B je skup prethodnika vrhova koji su susjedi od y. Kardinalni broj unije A i B je <n (ukupnog broja vrhova) jer postoji vrh koji nije ni u A ni u B - to je x.

Ukratko, ideja dokaza je ovo. Imamo Hamiltonov put od x do y. Izmedju x i y nema brida, tj. taj put nije ciklus. Htjeli bismo ga "prekopcati" tako da postane ciklus. Za to nam treba vrh koji je susjed od x, a njegov prethodnik je susjed od y (nacrtaj pa ces vidjeti kako treba prekopcati). Zato tako definiramo skupove A i B i trazimo nesto u presjeku.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.