Raschet Veroyatnosti Svyaznosti Sluchaynogo Grafa S Primeneniem Secheniy

Dlya seti, elementy kotoroy podverzheny sluchaynym otkazam, odnim iz vazhneyshikh pokazateley strukturnoy nadezhnosti yavlyaetsya veroyatnost' svyaznosti zadannogo podmnozhestva uzlov. Set' s nenadezhnymi elementami obychno modeliruetsya sluchaynym grafom, vershiny kotorogo sootvetstvuyut uzlam seti, a rebra - kanalam svyazi. Dlya kazhdogo elementa grafa zadana veroyatnost' ego prisutstviya v grafe, chto sootvetstvuet nadezhnosti sootvetstvuyushchego elementa seti. V dannoy rabote rassmatrivaetsya zadacha tochnogo rascheta veroyatnosti svyaznosti sluchaynogo grafa s absolyutno nadezhnymi vershinami i nenadezhnymi rebrami. Eta zadacha yavlyaetsya NP-trudnoy, odnako, nesmotrya na eto, sovremennye EVM pozvolyayut za razumnoe vremya rasschityvat' nadezhnost' setey prakticheski interesnoy razmernosti (desyatki i sotni uzlov). S drugoy storony, neobkhodimost' proverki priblizhennykh metodov na tochnost' ikh raboty takzhe stimuliruet dal'neyshie issledovaniya tochnykh metodov. V nastoyashchey rabote predlagayutsya novye metody ponizheniya razmernosti postavlennoy zadachi, osnovannye na ispol'zovanii secheniy (vershinnykh razrezov). Kak pokazali chislennye eksperimenty, poluchennye metody znachitel'no uskoryayut raschet nadezhnosti setey.