Zadacic iz diskretne

[vjekovac]

[hermione]

Gadno se mucim sa zadatkom u kojem treba naci broj razpinjucih stabala od kotaca(to je graf koji se dobije iz ciklusa dodavanjem jednog sredisnjeg vrha koji se spoji sa vrhovima ciklusa).
Krenula sam od teorema o matricnim stablima.I dobili sam determinantu koju ne mogu rijesiti(barem za sada).
Detrminanta je reda n i izgleda ovako

3 1 0 0 ....................................0 0 0 -1
-1 3 -1 0..................................... 0 0 0 -1
0 -1 3 -1................................... 0 0 0 -1
0 0 -1 3.................................... 0 0 0 -1
.
.
.
.
.
.
0 0 0 0 ...................................... 3 -1 0 -1
0 0 0 0.......................................-1 3 -1 -1
0 0 0 0....................................... 0 -1 3 -1
-1 -1 -1 -1 .....................................-1 -1 -1 n


Ili ako tko ima drugu ideju za rjesavanje bila bih veoma zahvalna.

[Nesi]

cinimise da ako svaki red dodas zadnjem
da ce zadnji izgledati 1 2 2 .... 1 0
onda zadnji pomnozis sa -1 pa ces imati stupac jedinica...


hmm... ma ne...

to je ono kada imas formulu... pocetna je npr M_n
naime, razvij ju po elementu (1,1)
i onda ces dobiti nesto gdje ces imati M_(n-1)

ako se ne varam, mislim da to ide tak nekak... pogledaj kak ste to tocno na lineranoj radili, ja sam malkoca zaboravila
u svakom slucaju, probaj se igrati i dobiti izraz sa slicnim determinantama nizeg reda....
to ti je gradivo mislim na samom kraju price s determinantama....
( zamoli Vjeku da pogleda.... )

_________________
It's not who you love. It's how.

[hermione]

Pokusala sam i to ,ali mi nije suoijelo.Prevrtila sam vjezbe il LA1,ali no help.....Dobih tip da pokusam rijasiti zadatal cisto preko rekurzije za razapinjuca stabla.....Pa se sada sa time zabavljam,makar bas i ne ide....

[vjekovac]

Rekurzivna relacija za determinantu je
D(n+1)=3*D(n)-D(n-1)+2
uz početne uvjete D(3)=16, D(4)=45.
Rješenje u zatvorenoj formi je

Odgovorio sam pod Linearnom algebrom jer si i tamo postala.
Ipak, dokaz je prekompliciran pa ga nisam pisao.

[krcko]

[hermione]

Kako dokazati ovo:
Neka je P(G,t) kromatski polinom grafa G s n vrhova i m bridova.Dokazite da je najmanji broj r takav da je koeficijent u t^r razlicit od nule jednak broju c(G),tj broju komponenti povezanosti grafa G?

[Gost]

Bome se i ja patim sa diskretnom. Muce me zadaci sa trokutovima pa ako neko zna rjesenje pliz help.
U potpunom grafu K_n svaki je brid obojan zutom ili crvenom bojom. Neka je z_i broj zutih bridova koji izlaze iz vrha v_i (i=1,...,n). Odredite broj jednobojnih trokutova u tom grafu.

ili ovaj:

Neka je G k-regularan graf. Dokazite da je ukupan broj trokutova u G i G^c (G komplement) jednak (v(G) povrh 3) - v(G)*k*(v(G)-k-1)/2

[hermione]

To to je ista sema zadataka.Izaberi triclani skup vrhova ,pogledaj kad oni ne tvore trokut i promjeni FUI.

[hermione]

Moze netko staviti zadnji rok na ovaj topic?