nejasnoća u vezi Kruskala

[Luuka]

Ja sam skužio da se uzima najmanji mogući brid (najmanje težine) bio on u istoj komponenti povezanosti ili ne. A kad uzimaš taj najmanji onda paziš da ne napraviš ciklus, tj ako ispadne da taj najmanji zatvara ciklus, onda uzmeš idući najmanji itd... A to kaj ne radiš cikluse (valjda) garantira da ćeš uzet n-1 brid, tj napravit stablo. (i to minimalno moguće)

_________________
"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

[buzov5]

malo mi se mjesa sve to...
neznam jel spada tu al radi se o kol pa ce te
mi oprostit. jel ko rjesavao lanjski kolokvij?
nekuzim onaj 3. zad?
zad kaze odredite FI za broj razlicitih rjeci koje mozemo
sastaviti od svih slova rjeci abrakadabra.
nekuzim ovo od svih slova rjeci ab... jel to
znaci da moram koristit svako slovo koliko hocu puta,
ili sto? a onda stavim da mi je n-ti clan niza broj nacina
da sastavim rjec duljine n od tih slova? ak je tak onda mi
ovih 5 a u abrakadabra dodje isto ko da je sam jedno a.
mozda sam trebo spavat...

_________________
tko je ikada naučio od poraza?

[teja]

abrakadabra={a^5,b^2,r^2,k}
onda ti je EFI=[1+x+(x^2)/(2!)+(x^3)/(3!)+(x^4)/(4!)+(x^5)/(5!)]*[1+x+(x^2)/(2!)]^2*(1+x)
jer a možeš staviti 0,1,2,3,4,5 puta, b i r 0,1,2 puta i k 0,1 put
ja mislim..

[woodstock]

tražio je FI, a ne EFI...
al nema veze, samo nema onih faktorijela...ostalo je isto

[buzov5]

znaci ne moram imat sva slova u rjeci.
hvala. samo fali jos jedan (1+x) za slovo d.

_________________
tko je ikada naučio od poraza?

[teja]

čitanje, zbrajanje i tako to nije moje područje...

[buzov5]

prosao sam jos par stranica u biljeznici sa vjezbi,
i tamo ima skoro isti zadatak, samo ne pise nadjite FI nego
koliko rjeci duljine 4 mozemo sataviti od slova rjeci banana.
i tamo su uredno faktorijeli dolje. sad nekuzim, znaci ja cu
dobit isti broj rjeci ako uzmem EFI i FI?
ako da, kad racunam sa EFI a kad sa FI?

_________________
tko je ikada naučio od poraza?

[teja]

heh, FI kad ti nije bitan poredak a EFI kad ti je bitan. ili kad ti kažu da napišeš FI ili EFI

[Luuka]

Mislim da nećeš dobit isti broj riječi

A sjećam se da je Maroje reko da se FI koriste za kombinacije, a EFI za permutacije. Dakle, FI kad poredak nije bitan, a EFI kad je.

edit:

[5ra]

mi smo na predavanjima dokazivali da Kruskalov algoritam zbilja daje najbolje rješenje.
baš i ne kužim taj dokaz.

w je ta težinska funkcija
označili smo bridove u stablu dobivenom Kruskalom sa e1, e2, ...e(n-1)
rako da je w(e1)<=...<=w(e(n-1))

i sada smo pretpostavili suprotno da postoji stablo sa bridovima f1,...,f(n-1) koje ima manji težinu
kak smo sad dobili na kraju kontradikciju?

help pliz )

_________________
http://www.youtube.com/watch?v=xYVoUEly-jA

[sun]

[buzov5]

neznam oce li mi napisati nadji efi ali u zad o kojem
sam pricao je pisalo odredite funkciju izvodnicu.

_________________
tko je ikada naučio od poraza?

[teja]

ma da ali efi je isto fi...