Excerpt
Preferencijos žymėjimas ženkliuku “ * nėra vienintelis, bet jis gal kiek patogesnis už kitus, nes skaičių tiesinio tvarkinio sąryšis “nemažesnis" žymimas panašiai “> *7 ir atitinkamai “=? bei “> ". Jei a, B, y yra skaičiai tokie, kad "= BE arba az B> 7, …
Excerpt
Apibrėžimas. Funkcija f, apibrėžta netuščių poaibių rinkinyje B vadinama pasirinkimo funkcija, jei 0 + f(A)c A visiems Ae B. Kiekvieną visiškąjį binarųjį sąryšį R galima vienareikšmiškai susieti su tam tikra pasirinkimo funkcija. Tas daroma taip: xRy sxe …
Excerpt
Jei pasirinkimo funkcija f. atitnkanti nesusijsiųjų alternatyvų aksiomą I, yra apibrėžta aibės X tokiems poaibiams A, kad |Al …
Excerpt
II skyrius GRAFAI Egzistuoja atskira matematikos šaka - grafų teorija, kurios tyrimų objektas yra binariųjų sąryšių diagramos. Minėtoji teorija ne tik egzistuoja, bet ir išsiskiria darbų gausa: vien tik monografijas, prisieitų skaičiuoti šimtais. Kodėl? …
Excerpt
Galvosūkyje, kuriuo domėjosi kenigsbergiečiai, buvo klausiama, ar galima pasivaikščioti, pereinant visus tiltus ir kiekvieną tik po vieną kartą? Oileris įrodė, kad toks pasivaikščiojimo maršrutas neįmanomas. Įrodinėdamas jis pasižymėjo nesusisiekiančias …
Excerpt
Grafų terminais aibės X elementai vadinami viršūnėmis, O binarųjį sąryšį sudarančios poros briaunomis arba lankais. Iš grafo apibrėžimo matome, kad viršūnės gali būti sujungtos tik viena briauna. Grafe negali, nes R - nerefleksyvusis sąryšis, būti ir, …
Excerpt
kurioms |U,| - nelyginis, skaičius yra O arba 2. Tas pats kriterijus tinka ir neorientuotiems multigrafams. Priegliaus tiltams turėtume: IUA|=5, |U5|=3, |Vc|=3, |Up|=3. Matome, jog skaičiai |U,| visose keturiose viršūnėse yra nelyginiai. Todėl šiame …
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, …
