СЛУЧА́ЙНЫЙ ГРАФ

СЛУЧА́ЙНЫЙ ГРАФ, слу­чай­ный эле­мент G не­ко­то­ро­го мно­же­ст­ва гра­фов 𝒢. В за­ви­си­мо­сти от свойств гра­фов мно­же­ст­ва 𝒢 раз­ли­ча­ют­ся С. г. ори­ен­ти­ро­ван­ные и не­ори­ен­ти­ро­ван­ные, слу­чай­ные де­ре­вья, слу­чай­ные ле­са и т. д., см. Гра­фов тео­рия. Ес­ли мно­же­ст­во 𝒢 ко­неч­но и все С. г. G рав­но­ве­ро­ят­ны, то го­во­рят о рав­но­ве­ро­ят­ных С. г. G. В тео­рии С. г. изу­ча­ют­ся точ­ные и пре­дель­ные рас­пре­де­ле­ния осн. ха­рак­те­ри­стик гра­фов, напр. чис­ло и раз­ме­ры ком­по­нент связ­но­сти, диа­метр гра­фа и т. д. При этом ком­по­нен­той связ­но­сти на­зы­ва­ет­ся мак­си­маль­ный связ­ный под­граф дан­но­го гра­фа, диа­мет­ром гра­фа на­зы­ва­ет­ся наи­боль­шее рас­стоя­ние ме­ж­ду его вер­ши­на­ми. Боль­шой ин­те­рес пред­став­ля­ют за­да­чи об эво­лю­ции С. г. Напр., пусть вер­ши­ны гра­фа ин­тер­пре­ти­ру­ют­ся как го­ро­да, а рёб­ра – как до­ро­ги, их со­еди­няю­щие. На­ли­чие тех или иных до­рог обу­слов­ле­но ис­то­ри­че­ски, и этот граф мож­но счи­тать С. г. До­ро­ги с те­че­ни­ем вре­ме­ни мо­гут слу­чай­ным об­ра­зом раз­ру­шать­ся и вос­ста­нав­ли­вать­ся. Пред­став­ля­ет ин­те­рес, напр., во­прос о том, как с те­че­ни­ем вре­ме­ни ме­ня­ет­ся ве­ро­ят­ность то­го, что этот граф свя­зен.