Juhuslik graaf

Juhuslik graaf on graaf, mis on saadud teatud juhusliku protsessi teel.

Juhuslike graafide teooria asub graafiteooria ja tõenäosusteooria piirimail. Juhuslik graaf saadakse n tippude hulga tipupaaride vahele servade juhusliku lisamise teel. Erinevad juhuslike graafide mudelid annavad erinevaid tõenäosuste jaotusi graafidel. Tuntud on Edgar Gilberti mudel G(n,p) kus iga serv lisatakse sõltumatult tõenäosusega p.

Kui kõikide n-tipuliste graafide hulka käsitleda graafide süsteemina, siis on võimalik määrata iga graafi olekutõenäosus selles süsteemis.

Vaata ka

• Graafide süsteem

Kirjandust

• Gilbert, E. N. (1959), Random graphs. – Annals of Mathematical Statistics, No 30, 1141–1144.
• Bollobás, B. (2001) Random Graphs, 2nd Edition, Cambridge University Press.