Excerpt
Apibrėžimas. Matrica A = ||a;||, kurios eilutės i=1,..,„m; o stulpeliai j=1,...,n; vadinama grafo gretimumo matrica, jei L, kai ij e R, “| O,kai ij £ R. Pavyzdys. Sudarykime gretimumo matricą grafui (tiksliau pseudografui) G=(X,R), kuriame …
Excerpt
Pavyzdžiui, grafo gretimumo matrica būtų sgo kasilobu 40 10 IL I I A=|ą;|=|1 1 0 1 || pa. B98 0 O A sell Amo Matricos elementai atitinka simetriškumą: aj = Aj Todėl neorientuoti grafai dažnai vadinami simetriniais grafais.Jei turime multigrafą, tai a; …
Excerpt
S a a a > (V = a Š ss == rs S > . S S S —m m S HH Dabar matricos A" antdiagonalinėje dalyje visi vienetukai. Pažymėsime v(A)=vienetukų skaičių ant pagrindinės diagonalės ir v(A*)=max v(A), kur maksimumas ieškomas pagal A eilučių ir stulpelių visus galimus …
Excerpt
Sukeitę 6 ir 4 vietomis, gautume A 05 A5 As 5 A |0 1 1 1 10 Asi Goa a lž6 ya Lose 003 Ost O isl: išel siel Ža S S S O SI Ag Aps Asų UEI L UI Ūj4 (0 Turime v(A')=11. Sukeitę 6 ir 2 pasiektume, jog matrica: Aj A5 Az Ap As Gy| |0 1 1 1 1 0 As5; Ūgp App Ass …
Excerpt
tokia, kad i I sR visiems re(0,1...,k-1). Sakykime, kad lankui ijeR priskiriamas skaičius a; Apibrėžimas. Kelio ig...,i, ilgiu I(u) vadinama suma k-I Nu)= Ža, r=0 Atskiru atveju, kai a; yra vienetukai, suma /(14) parodo iš kiek lankų susideda kelias tarp …
Excerpt
Jei minfas + a4) lygus a; +a; arba aj+ aj, tai aišku, kad trumpiausias kelias būtų vienintelė briauna. Pažymėkime A“ = B | trumpiausių ne daugiau kaip dviejų lankų kelių ilgių matricą. Ne daugiau kaip keturių lankų kelio, ilgis būtų: 2 2 Trumpiausią ai …
Excerpt
viršūnių. Šio grafo matrica A! yra tokia “ > 2 Ieškosime a; 1 k 1 . = i 2 a, Gj, II, norint surasti a m= S 8 88-94. 8 8 1 S a 8 8 B 8 B =E86 8 BND BS 6 5 Isa S 848 5" N. ma. S Š N.-8 88 S Aa B 8 ij? PERLA GS LE RER R 8 8 LS 68 A at aa 828 S NH arB 8 MR G …
Excerpt
Nuo matricos A“ pereiname prie o k Vip. 00 ID 48 53 A 02 010 Liao 6 IA IG ią 9 0 122422 9 29917 o 1 L 03,2 A o „alų žes a 2 89 22 42 09) 7) 6 5. 654 213 02 GO S 4. 27 6 100 5 2 0 D 1 02 5 9 7 3 G 3 0 14 13 2-5 2 64 10 2 0 Matricos 4* elementai a7 randami …
Excerpt
Pereiname prie A? : D Iš 10 9 M2+8+54 3' M 44 L UV LB o 125855 7 94 70246 1 5 4 02573 9 6 2 15 0298 5 > *=6||5 DE “9 a. 5 Ii pri 5 0 Palyginus su A“, sumažėjo kelių ilgiai tik tarp viršūnių porų 79, 69, 47 ir 48. Skaitytojas gali pasitikrinti, kad ŽŽ …
Excerpt
Pavyzdžiui 3 - 2 1 a; = mini a, rū] 2 3 = = Pako ok D A . Cia a; - trumpiausias atstumas tarp viršūnių ! IrJ per nedaugiau kaip tris žingsnius. …
Excerpt
Illskyrius Grafai operacijų tyrime + Yra nemažai uždavinių, susijusių su ekonomika ir sociologija, kurių esmę sėkmingai galima pavaizduoti atitinkamu grafu. Mat grafo briaunoms priskiriamus skaičius galime labai įvairiai interpretuoti. Jie gali reikšti ne …
Excerpt
Antroje lentelėje yra ta pati informacija, nors tuo iš pirmo žvilgsnio sunkoka patikėti Darbai AVFEB“ | EG ED SESIEBBĖG EEE IE ET [EK [LTL Darbai, be- Gi EE | D-|AEF CE [AEG ECE L tarpiški po KG E 21 …
Excerpt
tai darbo atitinkamai pradžia ir pabaiga, tai tokį darbą galima žymėti pora ij. Taigi, mūsų darbus grafe atitiktų poros: A B C D E F 02 05 T 65 05-16) G H I J K B GO TTT 000700 Kokie tie darbai su nulinėmis trukmėmis ir štrichuotomis briaunomis, t.y. …
Excerpt
2. Išbraukiame visas briaunas, prasidedančias įvykiu 0. Jas išbraukius, atsiranda įvykių, kuriais nesibaigia jokie darbai (I rango įvykiai). 3. Išbraukiame visas briaunas, išeinančias iš I-jo rango įvykių. Likusio grafo pradines viršūnes vadinsime II-jo …
Excerpt
galutinės viršūnės m (projekto užbaigimo įvykis), tai projekto realizacijos minimali trukmė , bus, aišku, didesnė ar jau nemažesnė, už kelio 7 ilgi /(z), kuriame briaunų ij ilgis matuojamas atitinkamų darbų trukmėmis /;. Tas formaliai užrašoma nelygybe im …
Excerpt
visoms briaunoms ji, priklausančioms grafui. Iteruodami pagal paskutinę lygybę, po 2 žingsnių surasime /„— projekto realizacijos minimalią trukmę. Pavyzdys. Surasime f„=/jg ir kritinį kelią grafui (18pav.). to=0, t;=maxkty+-t;Y=7, L;=maxity+-19> )=30, …
Excerpt
Kitais žodžiais galima sakyti, jog kritinio kelio viršūnėje neklaidinga yra lygybė T:= tį. Gana aišku, jog atvirkščias tvirtinimas būtų klaidingas, t.y. gali būti T,=t.,, bet viršūnė r nepriklauso jokiam kritiniam keliui. Pavyzdys. Surasime T; grafui …
Excerpt
10. Sistemos būsenos grafai Kickvienas daiktas kinta, bet kisdamas jis dažniausiai išlaiko savo identitetą. Suprantama, pasitaiko objektų, kurių identifikacija po vienokio ar kitokio pokyčio esti neįmanoma. Pavyzdžiui, vargu ar sprogusią bombą galima būtų …
Excerpt
1 - abi sekcijos veikia; 2 - pirma sekcija remontuojama, antra dirba; 3 - antra sekcija remontuojama, pirma dirba; 2 4- abi sekcijos remontuojamos. Dabar sistemos būsenų grafikas atrodytų taip: 4 21 pav. Čia nenurodytos perėjimo galimybės iš būsenos 1 į …
Excerpt
32 - pirmoji remontuojama, antroji profilaktiškai apžiūrima, 33 - abi sekcijos remontuojamos. 22 pav. matome sistemos būsenų grafą. 11.Būsenų ribinės tikimybės Sistemų (tame tarpe ir 10 skyrelio 1-4 pavyzdyje) būsenų kaita dažniausiai yra stochastinė. …
Excerpt
Perėjimo tikimybė iš 1 į 2 lygi 0,6, todėl, kad po užsakymo, t.y. būsenos 1, tikimybė vėl jį turėti yra p» = 0,4. Aišku, kad tikimybė neturėti užsakymo, t.y. atsidurti būsenoje 2, yra 1- P2= 0,6. Klausimas būtų toks. Kiek vidutiniškai pirmadienių agentas …
Excerpt
surasti, nes jos lygios perėjimo tikimybėms iš r — os būsenos, t.y. pi(1) = Dr Sunkiau būtų surasti i-osios būsenos tikimybę p;(2) po 2 perėjimų. Prisieitų spręsti tam tikrą tiesinių lygčių sistemą. Tą patį reiktų daryti ir ieškant p(3) = (P(3),---, p.(3) …
Excerpt
Viena iš galimų lygybės interpretacijų būtų tokia. Įsivaizduokime, kad sistemos buvimo būsenoje i dažnumas yra materiali substancija, pavyzdžiui, pinigai. Pinigai iš i išplaukia rodyklių į / kryptimis ir proporcingai tikimybėms p;. Analogiškai į i jie …
Excerpt
P5x (kavinė po bažnyčios) = 3/6 = 1/2, P». (teatras po bažnyčios) = 3/6 = 1/2, Pax (kavinė po kavinės) = 3/6 = 1/2. Analogiškai Px = 2/6 = 13, pu = 1/2, pi, = 1/6, pix = 5/6. Tad būsenų grafas su prie briaunų, esančiomis perėjimų tikimybėmis būtų toks: …