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