Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

random graph

[es] :: Art of Programming :: random graph

[ Pregleda: 3484 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

jandrla

Član broj: 8087
Poruke: 45
*.76.EUnet.yu



Profil

icon random graph21.07.2003. u 00:29 - pre 221 meseci
Ima li iko ideju kako napraviti neusmeren random graf sa n cvorova i m ivica?
Znaci ulaz je broj cvorova i ivica a izlaz je matrica ili lista povezanosti svejedno.
Hvala.
 
Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391


+3 Profil

icon Re: random graph21.07.2003. u 01:06 - pre 221 meseci
Mislim da je dovoljno da generišeš matricu susednosti (adjacency) dimenzija gde ćeš u gornje trougaoni deo smestiti jedinica, i naravno za svaku gornje trougaonu jedinicu na poziciji postavljaš odgovarajuću jedinicu na poziciji .

jedinica ćeš generisati tako što numerišeš gornje trougaone elemente matrice od do i ove brojeve smestiš u niz ; sledeći korak je biranje slučajnih elemenata tog niza i to tako što ćeš:

a) izabrati slučajan element niza ,

b) jedinicu upisati na onu poziciju u matrici na koju pokazuje ;

c) poslednji element niza onda prebacuješ na poziciju . Sledeće generisanje ide identično, osim što je sada broj elemenata u nizu manji za 1.

Naravno na kraju treba dokazati da je ansambl ovako generisanih matrica zaista izvučen sa uniformnom raspodelom (slučajan graf znači izabran po uniformnoj raspodeli, zar ne?) ali mi se ne čini da je to toliko teško.

I da, ko će da premesti ovu temu u Art of Programming?

f
 
Odgovor na temu

[es] :: Art of Programming :: random graph

[ Pregleda: 3484 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.