DISKRETINĖS MATEMATIKOS METODAI

DISKRETINĖS MATEMATIKOS METODAI

2. SANTYKIAI

Poaibis RĶMn yra vadinamas n-mačiu santykiu, apibrėžtu aibėje M. Labiausiai paplitę santykiai yra, kai n=2. Jie vadinami binariniais. Šiuo atveju priklausomybė (a,b) ĪR yra dažnai užrašoma aRb.

Tegul aibėje M yra duotas santykis R. Bet kuriam poaibiui M1 Ķ M galima apibrėžti santykį R’, vadinamą santykio R susiaurinimu aibei M1, kurį sudaro visos poros iš R, neturinčios elemento, priklausančio M1. Kitaip tariant, R’=RĒM12.

Binarinis santykis gali būti vaizduojamas įvairiai. Galima išvardinti visas poras. Priklausančias R, arba galima surašyti vvisą informaciją į matricą. Pastaruoju atveju matricos, tegul C, elementas

Kadangi santykiai yra tam tikros aibės poaibiai, tai tarp jų galioja tokios pat operacijos kaip ir tarp aibių. Be to, yra tokia specifinė operacija. Tegul R – santykis. Tada jam gali būti priskiriamas atvirkštinis santykis R-1, kuomet aiR-1aj tada ir tiktai tada, kada ajRai. Pagal apibrėžimą (R-1) -1=R.

Apibrėšime dabar paprasčiausias santykių savybes. Santykis R vadinamas refleksyviu, jeigu bet kuriam aibės M (pagimdančios R) elementui a galioja aRa. Priešingai, R vadinamas antirefleksyviu, jjeigu nėra tokio aĪM, kad būtų aRa. Pavyzdžiui, santykiai £ ir “turėti bendrą vardiklį” yra refleksyvūs, o < ir “būti sūnumi” yra antirefleksyvūs. O santykis “būti simetrišku x ašies atžvilgiu” yra nei vienoks nei kitoks. Santykis R vadinamas simetrišku, jeigu bbet kuriai porai (a,b)ĪM2 iš to, kad aRb, seka bRa. Simetriško santykio matrica yra simetriška pagrindinės diagonalės atžvilgiu: C i j = C j i visiems i ir j. Santykis R vadinamas antisimetrišku, jeigu iš aiRaj ir ajRai seka, kad ai=aj. Tokiu, pavyzdžiui, yra santykis £. Aišku, kad santykis R yra simetriškas tada ir tiktai tada, kada R=R-1. Santykis R vadinamas tranzityviu, jeigu bet kuriems a,b,c iš to, kad aRb ir bRc, seka aRc. Santykiai =, £, “gyventi viename mieste ” yra tranzityvūs, o santykis “turėti netuščią persikirtimą” – ne. Bet kuriam santykiui R santykis R^, vadinamas R tranzityviu uždarymu, apibrėžiamas taip: aR^b, jeigu aibėje M egzistuoja seka a=a1,a2,.,an-1,an=b tokia, kad aRa2, a2Ra3,.,an-1Rb. Jeigu R tranzityvus, tai R^= R. Pavyzdžiui, ssantykio “būti sūnumi” tranzityvus uždarymas – tai santykis “būti palikuonimi”.

Santykis R vadinamas ekvivalentiškumo santykiu, jeigu jis yra refleksyvus, simetriškas ir tranzityvus. Tegul M yra aibė, o R ekvivalentiškumo santykis, apibrėžtas joje. Aibė M yra suskaidoma į poaibius sekančiu būdu. Išrenkamas bet kuris elementas a1ĪM ir formuojama klasė C1, susidedanti iš a1 ir visų bĪM tokių, kad galioja a1Rb. Po to išrenkamas elementas a2ĪMC1 ir iš a2 bei visų elementų, ekvivalentiškų jam, sudaroma klasė C2. Tęsiant šį procesą gaunama klasių ssistema Ci, iĪI={1,2,.}, tenkinanti tokias sąlygas: 1) (nuo iĪI) Č Ci =M; 2) Ci Ē Cj =Ę, visiems i,jĪI, i¹j; 3) bet kurie du vienos klasės elementai yra ekvivalentiški; 4) bet kurie du elementai iš skirtingų klasių yra neekvivalentiški. Gautas suskaidymas yra vadinamas aibės M suskaidymas į ekvivalentiškumo klases santykio R atžvilgiu. Klasių skaičius yra vadinamas suskaidymo indeksu. Galimas ir atvirkščias kelias. Turint aibės M suskaidymą į klases gaunamas ekvivalentiškumo santykis R. Dviem elementams a,bĪM galioja aRb tada ir tiktai tada, kada a ir b priklauso vienai suskaidymo klasei.

Pavyzdys. Aibė M – tai natūrinių skaičių aibė N, o santykis R – tai “turėti tokią pat liekaną po dalybos iš 7”. Šiuo atveju R indukuoja 7 ekvvalentiškumo klases: 0,7,14,.; 1,8,15,.; 2,9,16,. ir t.t. Visos jos suskaičiuojamos.

Santykis vadinamas negriežtos tvarkos santykiu, jeigu jis refleksyvus, antisimetriškas ir tranzityvus. Jeigu santykis antirefleksyvus, antisimetriškas ir tranzityvus, tai jis vadinamas griežtos tvarkos santykiu. Aibė M, kurioje yra apibrėžtos tvarkos (negriežtos ar griežtos) santykis, vadinama pilnai sutvarkyta, ir dalinai sutvarkyta priešingu atveju. Dalinai sutvarkytos aibės pavyzdys – tai kokios tai aibės poaibių sankaupa M. sutvarkymą duoda įjungimo santykis Ķ.

3. ALGEBROS

Atvaizdavimas j: Mn®M yra vadinamas n-arine operacija, apibrėžta aibėje M. Aibė M kartu su užduota jjoje operacijų sankaupa Q={j1,j2,.}, t.y. sistema A=(M; j1,j2,.) yra vadinama algebra.

Aibė M’ĢM vadinama uždara n-arinės operacijos j atžvilgiu, jeigu j (M’n)ĶM’. jeigu aibė M’ yra uždara visų algebros A operacijų j1,j2,. atžvilgiu, tai sistema A’=(M’; j1,j2,.) yra vadinama algebros A poalgebra.

1 pavyzdys . Algebra (R;+, *) vadinama realių skaičių lauku, čia R – tai visų skaičių tiesė. Šios algebros poalgebra gali būti, pavyzdžiui, visų racionalių skaičių laukas.

2 pavyzdys . Tegul U – aibė, o b( U) – visų jos poaibių sankaupa (dar vadinama buleanu). Algebra B=(b( U); Č,Ē, -) vadinama buline aibių algebra. Bet kuriam poaibiui U’Ģ U sistema B’=(b( U’); Č,Ē, -) yra algebros B poalgebra.

Tegul duotos 2 algebros A=(K; j1,.jp) ir B=(M; y1,.yp) su operacijomis ji:Kl(i)®K, yi:Ml(i)®M, i=1,2,.p, (tada sakoma, kad algebros A ir B yra vienodo tipo). Algebros A į algebrą B homomorfizmu vadinamas atvaizdavimas r:K®M, tenkinantis sąlygą r(ji( ,., ))=y i (r( ),.,r( )), visiems i=1,2,.,p ir visiems ĪK.

Algebros A izomorfizmu į algebrą B vadinamas abipus vienareikšmis homomorfizmas. Šiuo atveju egzistuoja atvirkščias atvaizdavimas r-1:M®K, kuris yra abipus vienareikšmis. Nesunku parodyti, kad jei egzistuoja izomorfizmas iš A į B, tai taip pat egzistuoja ir izomorfizmas iš B į A. tad paprasčiausiai sakoma, kkad algebros A ir B yra izomorfinės. Aišku, šiuo atveju aibių K ir M galingumai sutampa.

Jeigu A=B, tai izomorfizmas iš A į B vadinamas automorfizmu.

3 pavyzdys. Tegul QN, Q2N – atitinkamai visų sveikų skaičių ir visų lyginių sveikų skaičių aibės. Tada algebros (QN; +) ir (Q2N ; +) yra izomorfinės. Izomorfizmą garantuoja atvaizdavimas r:n®2n. Kadangi Q2NĢQN, tai r yra algebros (QN; +) izomorfizmas į save.

4 pavyzdys. Aibių Bulio algebros (b(U); Č,Ē, -) ir (b(U’); Č,Ē, -) yra izomorfinės, kai aibių U ir U’ galingumai yra vienodi. Kaip atvaizdavimas r gali būti imama bet kokia bijekcija iš U į U’.

4. PUSGRUPĖS IR GRUPĖS

Pusgrupe vadinama algebra su viena binarine asociatyve operacija *, t.y. tokia operacija, kuriai (a*b)*c=a*(b*c). jei operacija dar ir komutatyvi, t.y. a*b=b*a, tai tai pusgrupė yra vadinama Abelio pusgrupe. Pusgrupė gali turėti tokį elementą e, kad bet kuriam kitam elementui a ae=ea=a. Toks elementas e vadinamas pusgrupės vienetiniu elementu, o tokia pusgrupė – monoidu .

1 pavyzdys. Tegul yra duota aibė M ir tegul G yra kokia tai aibės M atvaizdavimų į save sankaupa. Šioje sankaupoke galima apibrėžti atvaizdaimų kompozicijos operaciją. Ši operacija yra asoiatyvi. Todėl, jeigu sankaupa G yra uždara kompozicijos atžvilgiu, tai ji yra

pusgrupė. Vienetinis elementas – tai tapatingas atvaizdavimas.

Grupė vadinama pusgrupė su vienetu, kurioje kiekvienam elementui a egzistuoja elementas a-1, vadinamas atvirkščiu elementui a, kuris tenkina sąlygą: aa-1=a-1a=e. Elementų skaičius grupėje vadinamas jos eile. Grupė, kurios operacija yra komutatyvi, vadinama Abelio grupe. Grupė, kurios visi elementai yra vieno elemento a laipsniais, yra vadinama cikline. Ji visada yra abelinė.

2 pavyzdys. Racionalių skaičių aibė be nulio su daugybos operacija yra Abelio grupė. Elementui a yra atvirkščias 1/a.

Labai svarbią grupę sudaro baigtinės aaibės M abipus vienareikšmių atvaizdavimų aibė S kartu su atvaizdavimų kompozicijos operacija. Ši grupė yra vadinama simetrine grupe. Grupės eilė lygi |M|!. Simetrinė grupė, aišku, nėra abelinė.

Bet kuriai baigtiniai grupei jos operacija gali būti charakterizuojama Keli lentele. Lentelė turi tiek eilučių ie stulpelių, kiek grupėje yra narių, ir jos elementas i-tosios eilutės ir j-tojo stulpelio persikirtime lygus aiaj. Ši lentelė turi tokią savybę: bet kuris jos stulpelis turi visus grupės elementus. Sakykim, kad nėra taip, ir stulpelis, atitinkantis ai, tturi ne visus elementus. Bet tada jame egzistuoja elementas, tarkime aj, kuris sutinkamas dukart, tarkime, k-oje ir l-oje eilutėse. Bet tada akai=aj, alai=aj ir akai=alaj. Padauginus abi puses iš ai -1, gauname, kad ak=al. Bet taip negali būti. Tiagi i-tasis llentelės stulpelis, t.y. daugyba iš ai – tai ne kas kita, kaip grupės elementų perstatymas. Galima patikrinti, kad šis atitikimas yra izomorfizmas. Gauname Keli teoremą.

Teorema. Bet kuri baigtinė grupė yra izomorfinė jos elementų aibės perstatymų grupei.

Apibrėžimas. Grupės G pogrupiu vadinamas bet koks poaibis SĢG, kuris yra grupė operacijos * atžvilgiu.

TINKLELIAI

1 apibrėžimas. Aibė, kurioje be operacijų yra užduoti ir santykiai, vadinama algebrine sistema.

Algebros ir aibės, kuriose užduoti tik santykiai, yra dalinai algebrinių sistemų atvejai. Svarbiausias algebrinių sistemų pavyzdys yra tinklelis.

Tegul M yra aibė, kurioje duotas dalinio sutvarkymo santykis £. Elementams a,bĪM jų viršutine riba vadinamas bet kuris elementas cĪM toks, kad c³a, c³b, o jų apatine riba – bet kuris elementas dĪM toks, kad d£a, d£b. Aplamai, kkažkokiems elementams a ir b viršutinė ar apatinė riba gali neegzistuoti arba gali būti nevienintele ir skirtingos viršutinės (arba apatinės) ribos gali būti nepalyginamos. Žymėsime aŁb=c tokią apatinę ribą elementams a ir b, kad bet kuri kita jų apatinė riba yra mažesnė už c. Analogiškai, aŚb=d – tokia viršutinė riba elementams a ir b, kad bet kuri kita jų viršutinė riba yra didesnė už d. Elementai aŁb ir aŚb yra vadinami didžiausia apatine ir mažiausia viršutine ribomis.

2 apibrėžimas. Tinkleliu vvadinama algebrinė sistema {M; £; Ł,Ś}, t.y. dalinai sutvarkyta aibė M, kurioje bet kurie du elementai turį didžiausią apatinę ir mažiausią viršutinę ribas.

Dalinai sutvarkytos aibės yra vaizduojamos diagramomis. Iš taško a eina rodyklė į tašką b, jeigu an – 0. Pavyzdžiui, kai C={1,2}, Y={a,b,c,d}, tai turime (4)2=12 m-perstatymų ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc. Prie m=n gauname perstatymus arba keitinius, kurių skaičius n!.

Kai C=C”, Y=Y”, kiekvienas injektyvus atvaizdavimas prie n>m aibėje Y išskiria jos poaibį, susidedantį iš m elementų. Tokių aibės Y m-poaibių arba dar kaip vadinama derinių skaičius yra žymimas (nm) (t.y. n virš m). Parinkus bet kurį elementą yĪY visus m-poaibius galima suskirstyti į 2 grupes: Į tuos, kurie turi y ir tuos, kurie neturi y. Pirmųjų skaičius –

, antrųjų – . Gauname rekurentinę lygybę

= + . (1)

Turime = = 1, be to priimame = 1, = 0, prie m>n. Spręsdami (1) nustatome, kad

= , m≤n (2)

Iš šios formulės iškart seka, kad

= (3)

Dydžiai (mn) yra vadinami binominiais koeficientais. Juos galima apibrėžti ir prie neigiamų n, t.y.

(4)

Jei atvaizdavimas f: C”®Y¢ bet koks, tai gauname jam atitinkančią m-multiaibę, sudarytą iš elementų, priklausančių aibei Y. Tokių m-multiaibių skaičius llygus V(n,m) =

= = . Tai seka iš to fakto, kad prie C={1,.,m}, Y={1,.,n} atvaizdavimas

j: y1 y2.ym® y1, y2+1, . ,ym+(m-1) yra bijekcija tarp m-multiaibių, sudarytų iš Y elementų, ir aibės {1,2,.,n+m-1} m-poaibių sankaupų. Antroji iš šių sankaupų turi, būtent,

elementų. Arba galima samprotauti labiau vaizdžiai. Yra n+m pozicijų, pirmoje iš kurių randasi pirmas aibės Y elementas, o kitos tuščios. Reikalinga į tuščias pozicijas įrašyti likusius elementus iš Y. Po to kiekviena laisva pozicija yra užpildoma aibės Y elementais, kurie yra artimiausi joms iš kairės. Kiekvienas taip gautas rinkinys yra m-multiaibė ir tokių rinkinių skaičius įvertinant (3), yra V(n,m). Pavyzdžiui, kai C={1,2,3,4}, Y={a,b,c}, pradžioje

, po to ir pagaliau

, t.y. ganame 3-multiaibę. Tokia procedūra duoda skirtingas m-multiaibes.

Pavyzdžiui, nurodytiems C, Y turime V(n,m)=15 ir tokias 3-multiaibes aaaa, aaab, aaac, aabb, aabc, aacc, abbb, abbc, abcc, accc, bbbb, bbbc, bbcc, bccc, cccc.

Jeigu yra užduotas apribojimas, kad m-multiaibės būtinai apimtų Y, tai gauname siurjektyvinius atvaizdavimus f: C”®Y¢. Jų skaičius V0(n,m) = ( nm–11 ). Galima parodyti panašiai kaip ir anksčiau: į m-1 poziciją pradedant nuo antros yra įrašomi elementai y2,.,yn-1, po to laisvos pozicijos užpildomos kaip ir anksčiau. Gauta m-multiaibė būtinai turės visus aibės Y elementus. Pavyzdžiui, pprie tų pačių C,Y,

pradžioje , po to , ir pagaliau .

Aibės C suskaidymų į n netuščius poaibius skaičius Smn yra vadinamas antros rūšies Stirlingo skaičiumi. Pavyzdžiui, kai C={1,2,3,4}, o n=2, turime tokius 7 suskaidymus: {1,2,3}Č{4}, {1,2,4}Č{3}, {1,3,4}Č{2}, {2,3,4}Č{1}, {1,2}Č{3,4}, {1,3}Č{2,4}, {1,4}Č{2,3}. Paprastos formulės šiems skaičiams nėra.

Siurjektyvių atvaizdavimų f: C¢®Y¢ skaičius lygus n!Smn. Iš tikro, kiekvienas toks atvaizdavimas duoda aibės C suskaidymą į n poaibių. Tačiau iš kitos pusės, kiekvienas toks suskaidymas duoda n! neekvivalentinių siurjektyvių atvaizdavimų. Pavyzdžiui, kai C={1,2,3}, Y={a,b} gauname tokius atvaizdavimus:

suskaidymas {1,2}Č{3} suskaidymas {1,2}Č{3} suskaidymas {1}Č{2,3}

Atvaizdavimų f: C¢®Yn” skaičius yra vadinamas Belo skaičiumi ir lygus

Bm=(nuo k=1 iki n)å Smk, kai |C|=m, |Y|=n.

Kai C=C”, Y=Y” ir f – siurjektyvinis atvaizdavimas, gauname skaičiaus m suskaidymą į n dalių. Tokių suskaidymų kiekį pažymėkime Pmn. Šis dydis taipogi neturi paprastos išraiškos. Pavyzdžiui, kai m=7, n=3, tai turime tokius suskaidymus: 5+1+1, 4+2+1, 3+2+2.

Reziumuojant galima pateikti tokią lentelę, kurios kiekviename langelyje įrašytas atitinkamo 1-os lentelės langelio atvaizdavimų skaičius.

2 lentelė.

f: C®Y bet koks injektyvus siurjektyvus Bijektyvus

C¢,Y¢ nm (n)m n!Smn n!

C”,Y¢ 1

C¢,Y” B m 0 arba 1 S mn 1

C”,Y” n å P mk k=1 0 arba 1 P mn 1

Yra svarbūs ir kai kurie kiti skaičiai. Visų pirma, tai polinominiai koeficientai. Toks koeficientas Pm(q1,.,q n) lygus atvaizdavimų skaičiui, kai qi

aibės C elementų xj yra atvaizduojama į yi, i= .

Konkrečiai . Akivaizdu, kad .

q1+.+qn=m, qi³0.

Derinių skaičius yra lygus m-poaibių skaičiui. Visų aibės C poaibių rinkinys įtraukiant tuščią aibę Ę ir pačią C yra vadinamas buleanu ir žymimas 2C. Pavyzdžiui, jei C={0,1}, tai 2C susideda iš Ę, {0}, {1}, {0,1}. Kiekvienam buleano elementui C¢ galima priskirti 0-1 vektorių (S1,S2,.,Sm), kuriame Si=1, jeigu xiĪC¢, ir Si=0 priešingu atveju. Tokių vektorių skaičius, taigi ir poaibių skaičius lygus |2C|= 2m (sutinkamai su 1-u 22 lentelės langeliu).

4. KOMBINATORINĖS KONFIGŪRACIJOS

Sprendžiant praktinius uždavinius, pavyzdžiui, atliekant statistinius tyrimus eksperimentų planavime, naudojami lotynų stačiakampiai ir kvadratai, ortogonalūs lotynų kvadratai, BIB – schemos ir kitos jiems artimos kombinatorinės konfigūracijos.

1 apibrėžimas. Lotynų stačiakampiu vadinama sudaryta iš aibės C={1,2,.,n} elementų stačiakampė m eilučių ir n stulpelių lentelė, kurioje kiekvienoje eilutėje ir kiekviename stulpelyje visi elementai yra skirtingi.

2 apibrėžimas. n-tos eilės lotynų kvadratu vadinama kvadratinė n stulpelių ir n eilučių lentelė, kuri užpildoma n skirtingais elementais taip, kad kiekvienas eelementas tik vienąkart sutinkamas kiekvienoje eilutėje ir kiekviename stulpelyje.

Pavyzdžiui, lentelės

2 4 5 1 3 1 2 3 4

3 1 4 5 2 2 3 4 1

5 3 1 2 4 3 4 1 2

4 1 2 3

yra atitinkamai llotynų stačiakampis ir 4-tos eilės lotynų kvadratas.

Lotynų kvadratams būdingas betarpiškas praktinis pritaikymas. Kaip pavyzdį galima pateikti tokį uždavinį. Reikalinga suskaidyti stačiakampio formos lauką į sklypelius taip, kad būtų galima pasėti jame n veislių javus turint tikslą objektyviai palyginti šių veislių derlingumą ir to siekiant būtų atsižvelgta į dirvožemio kokybės nevienodumą lauko ribose. Laikoma, kad dirvožemio derlingumas mažėja tolstant nuo vienos lauko kraštinės (neaišku tiktai kurios) link priešingos. Šio uždavinio sprendimas toks: reikia suskaidyti lauką į n2 vienodų stačiakampių ir pasėti javus taip, kad kiekviena jų veislė būtų panaudota lygiai vieną kartą kiekvienoje sklypelių eilėje ir lygiai vieną kartą kiekviename jų stulpelyje. Tokiu būdu, kiekviena šio eksperimento schema yra n-tos eilės lotynų kvadratas.

3 apibrėžimas. Du n-tos eilės lotynų kvadratai LL1n=(aij) ir L2n=(bij), vadinami ortogonaliais, jeigu visos poros (aij, bij) yra skirtingos.

Pavyzdžiui, lotynų kvadratai

0 1 2 3 0 2 3 1 0 3 1 2

1 0 3 2 1 3 2 0 1 2 0 3

2 3 0 1 2 0 1 3 2 1 3 0

3 2 1 0, 3 1 0 2 ir 3 0 2 1

yra ortogonalūs.

Ortogonalių lotynų kvadratų poros egzistuoja prie bet kurio n, išskyrus n=2 ir n=6. n-tos eilės poromis oortogonalių lotynų kvadratų skaičius neviršija n-1.

Ortogonalių lotynų kvadratų praktinę svarbą galima pailiustruoti tokiu pavyzdžiu. Tegul yra atrinkti n veislių javai ir n rūšių trąšos, ir vieni ir kiti sunumeruoti skaičiais nuo 1 iki n. javų veislės yra paskirstomos tarp n2 sklypelių pagal lotynų kvadratą L1n, o trąšos pagal – lotynų kvadratą L2n. jeigu L1n ir L2n – ortogonalūs, tai kiekviena iš n javų veislių sudarys porą su kiekviena iš n trąšų rūšių. Atsitiktinai parenkant ortogonalius lotynų kadratus L1n ir L2n , galima patikrinti trąšų įtaką veislių derlingumui, neutralizuojant pačios dirvos derlingumo netolygumo efektą.

Pilnos poromis ortogonalių lotynų kvadratų aibės sudarymui galima panaudoti Stivenso-Bouzo metodą. Tegul n – paprastas skaičius, A={a0, a1,.,an-1} – aibė, susidedanti iš skirtingų elementų, be to, aiĪ{0,1,.,n-1}, . Tada n-1 poromis ortogonalūs n-tos eilės lotynų kvadratai apibrėžiami taip:

Lℓn=( aℓij), i,j=0,n-1 , ℓ=1,2,.,n-1, kur aℓijŗ( ai aℓ+aj) (mod n).

Teorema. Tegul n – paprastas skaičius. Tada prie n³3 egzistuoja pilna poromis ortogonalių n-tos eilės lotynų kvadratų aibė, susidedanti iš n-1 kvadrato.

Įrodymas. Tarkime, kad a0=0, a1=1,.,an-1=n-1. Kiekviena lentelė Lℓn nusako lotynų kvadratą. Iš tikrųjų, lygybė aℓij, aℓij¢ prie j¹j¢ reiškia, kad aj=aj¢, bet tai yra prieštaravimas. Analogiškai, lygybė aℓij=aℓi¢j prie i¹i¢ implikuoja sąlygą (ai-ai¢)aℓ=0. Iš čia, žžinant, kad aℓ¹0, gauname prieštaraujančią lygybę ai=ai ¢.

Parodysime Lkn ir Lℓn , l¹k, ortogonalumą. Tarkime, kad prie (i,j)¹(i¢,j¢) (akij, aℓij)=( aki¢j¢, aℓi¢j¢). Iš čia seka 2 lygybės

ai ak+ aj= ai ¢ ak+ aj ¢,

ai aℓ + aj= ai ¢ aℓ+ aj ¢.

Atimant 2-ą lygybę iš pirmos, gauname, kad ai(ak-aℓ)=ai ¢(ak-aℓ), ir kadangi ak-aℓ¹0, tai ai=ai¢ , t.y. i=i¢. Iš pirmos lygybės nustatome, kad aj=aj¢ , t.y. j=j¢. Gavome prieštaravimą.

3 apibrėžimas. Aibės C={x1,x2,.,xv} poaibių sankaupa C1,C2,.,Cv , sudaro (v,k,l) – konfigūraciją, jeigu 01 ir vℓ+1=v1, tai grandinė yra vadinama ciklu.

3 pav.

3 pav. v2,e5,v5,e4,v7,e3,v8 ir v1,e1,v2,e2,v3 – grandinės, o v2,e1,v4,e3,v7,e4,v5,e5,v2 ir v1,e1,v2,e5,v5,e4,v7,e3,v4,e2,v1 – ciklai.

Tegul k(H) – hipergrafo H surištų komponenčių skaičius.

1 teiginys. n viršūnių m briaunų hipergrafas H neturi ciklų tada ir tiktai tada, kada

å (|e|-1)=n-k(H) (1)

eĪE

Įrodymas. H neturi ciklų tada ir tiktai tada, kada K(H) yra miškas. Bet K(H) turi k(H) komponenčių, m+n viršūnių ir (nuo eĪE)å |e| briaunų. Todėl (nuo e)å |e|=m+n-k(H) t.y. gauname (1).

Suporavimu hipergrafe H vadinamas poaibis E¢ĶE toks, kad bet kurioms briaunoms e¢, e¢¢ galioja e¢Ēe¢¢=Ę. Briaunų skaičius didžiausiame suporavime vadinamas suporavimo skaičiumi (žymėsime a1(H)).

Tegul duota baigtinės aibės S netuščių poaibių šeima S1,S2,.,Sk. Šios šeimos transversaline aibe vadinama aibė TTĶS tokia, kad TĒ Si¹Ę, i=1,2,.,k. Hipergrafo H transversaline aibe vadinama jo briaunų transversalinė aibė. Mažiausias viršūnių skaičius joje vadinamas H transversalumo skaičiumi (žymėsime t(H)).

2 teiginys. Bet kuriam hipegrafui H teisingos nelygybės

a1(H) £ t(H),

t(H) £ r(H) a1(H), r(H)= .

Įrodymas. (1). Jeigu P – suporavimas hipergrafe H, o T hipergrafo H transversalinė aibė, tai |T|³|P|. Todėl

t(H)= ³ =a1(H).

(2). Tegul P0 – didžiausias suporavimas. Tada

– H transversalinė aibė.

Todėl t(H) £ | |= | e | £ r(H)*|P0|= r(H)a1(H).

Hipergrafo H=(V,E) realizacija vadinamas bet kuris grafas G=(V¢,E¢), tenkinantis tokias sąlygas:

1) V¢=V;

2) bet kuri G briauna priklauso bent vienai H briaunai;

3) bet kuriai briaunai eĪE indukuotas pografis G(e) yra surištas.

Hipergrafo H briaunos eĪE realizacija yra bet kuris surištas grafas Ge=(V¢e,E¢e), kuriam V¢e=e. Todėl bet kuri hipergrafo realizacija – tai jo briaunų kažkokių realizacijų apjungimas.

4 pav. parodytas grafas ir dvi jo realizacijos.

4 pav.

H

G¢

G¢¢

Hipergrafo H=(V,E) briaunų grafu vadinamas grafas L(H)=(E,T), kuriame viršūnės atitinka H briaunoms, ir dvi viršūnės sujungtos briauna tada ir tiktai tada, kada joms atitinkančios H briaunos yra gretimos. Faktiškai L(H) – hipergrafo H briaunų sankirtų grafas.

Sakoma, kad poromis gretimų briaunų aibė {e1,e2,.,ek} tenkina Cheli sąlygą, jeigu (nuo i=1 iki k)Ē ei ¹ Ę. Jeigu

bet kuri H briaunų aibė su nurodyta sąlyga tenkina Cheli sąlygą, tai yra sakoma, kad Cheli sąlygą tenkina hipergrafas H.

Teorema. Hipergrafo H realizacija medžiu egzistuoja tada ir tiktai tada, kada H tenkina Cheli sąlygą ir briaunų grafas L(H) yra sutrikampiuotas. /Be įrodymo/.

Hipergrafas H 4 pav. tenkina teoremos sąlygas. Viena iš realizacijų medžiu – tai grafas G¢.

NEPRIKLAUSOMOS AIBĖS HIPERGRAFE

Hipergrafo H viršūnių aibė vadinama nepriklausoma, jeigu ji neturi nei vienos briaunos. Viršūnių skaičius didžiausioje nepriklausomoje aibėje vadinamas hipergrafo H nepriklausomumo sskaičiumi (žymėsime a0(H)). Tegul I(H) -visų H nepriklausomų aibių šeima.

Kiekvienam hipergrafui H=(V,E) be kartotinių briaunų galima priešpastatyti monotoninę bulinę funkciją. Tegul xU={x1,x2,.,xn} – bet kurio poaibio UĶV charakteringas vektorius. Apibrėžkime bulinę funkciją fH, priimdami, kad fH(x)=0 n-mačiui 0-1 vektoriui x=xU tada ir tiktai tada, kada UĪI(H). Akivaizdu, kad fH monotoninė ir fH(0,0,.,0)=0.

Atvaizdavimas H®fH apskritai nėra injektyvus, kadangi hipergrafo briaunos gali priklausyti viena kitai. Ryšium su tuo ypač įdomūs yra specialūs hipergrafai – tai antigrandinės. Tai toks hipergrafas, kai jjokia jo briauna nėra kitos briaunos poaibiu. Visi k-vienalyčiai hipergrafai, tame tarpe paprasti grafai, yra antigrandinės.

Tegul H=(V,E) – bet kokia antigrandinė. H briaunų charakteringi vektoriai yra poromis nepalyginami santykio £ atžvilgiu: x=(x1,x2,.,xn) £ y=(y1,y2,.,yn) Ū (xi£yi, ). Todėl egzistuoja vvienintelė n kintamųjų monotoninė bulinė funkcija, kurios apatinių vienetų aibė sutampa su H briaunų charakteringų vektorių aibe. Akivaizdu, kad fH ir yra tokia funkcija. Antigrandinei, neturinčiai briaunų, fHŗ0

Iš kitos pusės, tegul f – monotoninė n kintamųjų bulinė funkcija, be to f≠1. Apibrėžkime hipergrafą Hf, priimdami Vf={1,.,n} ir laikydami briaunomis visus Vf poaibius, kurių charakteringi vektoriai yra f apatiniais vienetais. Kadangi f yra monotoninė, tai Hf yra antigrandinė. Akivaizdu, kad HHf=f.

Tokiu būdu, f®Hf yra bijekcija tarp monotoninių bulinių funkcijų, neekvivalentiškų 1, aibės ir antigrandinių aibės.

Tegul A – bet kokia m x n matrica be nulinių stulpelių, kurios elementai – tai neneigiami realūs skaičiai. Panagrinėkime tiesinių nelygybių sistemą

AC£B, (1).

čia C – kintamųjų xi, , vektorius B – neneigiamų skaičių sstulpelis. Laikysime, kad xi gali įgyti tik reikšmes Ī{0,1}. Apibrėžkime n kintamųjų bulinę funkciją f priimdami f(x1,.,xn)=0 tada ir tiktai tada, kada (x1,.,xn) yra sistemos (1) sprendinys. Akivaizdu, kad f yra monotoninė funkcija ir f(0,0,.,0)=0. Sakysime, kad f yra užduodama sistema (1).

Parodysime, kad bet kuri monotoninė bulinė funkcija neekvivalentiška 1, užduodama tam tikra pavidalo (1) tiesinių nelygybių sistema su neneigiamais koeficientais ir dešiniosiomis pusėmis. Tegul f – tokia funkcija, Hf – jai atitinkanti antigrandinė, Vf={1,.,n}, Ef={e1,e2,.,em}, ei={j1,j2,.,jni}, |ei|=ni, . GGalima apibrėžti sistemą

xj1+ xj2+.+ xjni £ ni-1, . (2)

Akivaizdu, kad vektorius x=xU=(x1,x2,.,xn) yra šios sistemos sprendiniu tada ir tiktai tada, kada UĪI(Hf). Tai reiškia, kad fHf=0. Bet fHf=f. Todėl funkcija f yra užduodama sistema (2). Apskritai, nelygybių sistema, užduodanti monotoninę bulinę funkciją, apibrėžiama nevienareikšmiškai.

Teiginys. Tegul f – monotoninė bulinė funkcija, neekvivalentiška 1, (1) – ją užduodanti tiesinių nelygybių sistema, Hf=(Vf,Ef) – atitinkanti antigrandinė, UĶVf, xU – poaibio U charakteringas vektorius. Tada tokie teiginiai yra ekvivalentiški:

1) f(CU)=0;

2) vektorius xU yra sistemos (1) sprendinys;

3) UĪI(Hf).

NEPRIKLAUSOMUMO SISTEMOS MATROIDAI

1 apibrėžimas. Aibės E poaibių sistema S=(E,I) vadinama nepriklausomumo sistema, jeigu I susideda iš E poaibių rinkinio, uždaro įjungimo santykio prasme (t.y. jeigu BĪI ir B¢ĶB, tai ir B¢ĪI). Aibės I elementai vadinami nepriklausomais.

Esant duotai nepriklausomumo sistemai S=(E,I) ir svoriams C(e)³0, priskirtiems aibės E elementams e, galima formuluoti tokį uždavinį: surasti poaibį BĪI tokį, kuriam vertė (nuo eĪB)å C(e) yra maksimali. Sudarant šio uždavinio sprendimo algoritmus, yra labai svarbu kaip užduodama sistema S=(E,I). Ji, aišku yra algoritmo įėjimo davinių dalis. Elementariausias būdas – tai pateikti visų poaibių iš I sąrašą. Tačiau šis būdas labai jau neefektyvus, kadangi tokių poaibių skaičius gali būti proporcingas dydžiui 2|E|. Geresnis būdas tai toks, kai I yra reprezentuojama algoritmu AI, ppateikiamam poaibiui B nustatančiu, ar BĪI, ar ne.

1 pavyzdys. Maksimalaus svorio miško grafe G=(V,E) išskyrimo uždavinys gali būti suprantamas kaip uždavinys su nepriklausomumo sistema S=(E,T), čia T – aibės E poaibių, atitinkančių miškams grafe G, klasė.

2 pavyzdys. Taip pat duotas grafas G=(V,E), suporavimais kuriame sudaro aibę M. Nesunku suvokti, kad suporavimų sistema S=(E,M) yra nepriklausoma.

3 pavyzdys. Esant duotai orgrafui D=(V,A) su svoriais C(e)³0, priskirtais lankams aĪA, galima suformuluoti šitokį uždavinį: išskirti aibėje A didžiausio svorio poaibį B tokį, kad aibėje B nebūtų dviejų lankų, turinčių bendrą galinę viršūnę. Tai uždavinys su sistema (A,K), kurioje sankaupą K sudaro poaibis B su aukščiau nurodyta savybe.

4 pavyzdys. Tegul E yra nx|E| – matricos A stulpelių aibė. Tuo atveju, kai I – matricos A tiesiškai nepriklausomų stulpelių aibių rinkinys H, gauname nepriklausomumo sistemą S=(E,H). Matricai, duotai žemiau, {e1, e2, e3, e4}ĪH, tuo tarpu kai {e1, e4, e5, e6}ĻH, { e4, e6, e7}ĻH.

3 1 3 0 2 1 1 1

0 2 1 1 0 0 1 2

1 1 2 0 1 0 0 0

2 0 0 -1 0 2 1 0

e1 e2 e3 e4 e5 e6 e7 e8

Paprasčiausias algoritmas uždaviniams su nepriklausomumo sistema spręsti yra godus algoritmas.

begin

N:=Ę;

while E¹Ę do

begin

tegul e – elementas iiš E su didžiausiu svoriu C(e);

išmesti e iš E;

if N+eĪI then N:=N+e

end

end

2 apibrėžimas. Tegul S=(E,I) – nepriklausomumo sistema. Vadinsime S matroidu, jeigu godus algoritmas bet kuriam uždaviniui su S (t.y. prie bet kokių C(e)³0) duoda optimalų sprendinį.

1, 3 ir 4 pavyzdžiuose pateiktos sistemos yra atitinkamai grafinis, suskaidymo iš matricinis matroidai. Tuo tarpu sistema S=(E,M) nėra matroidas. Kontrpavyzdys atrodo taip

Kairėje parodytas suporavimas, kurį duoda godus algoritmas, dešinėje – maksimalus suporinimas.

Kai kurias nerpiklausomumu sistemas galima apibūdinti kaip dviejų arba daugiau matroidų persikirtimus. Pavyzdžiui, dvipusiam grafui G=(VČU,E) atitinkanti suporavimų sistema S=(E,M) gaunama sukirtus du suskaidymo matroidus R1=(E,I1) ir R2=(E,I2). Tada M= I1Ē I2 . Matroidas R1 yra nusakomas suskaidymu PV kuris sudalija briaunas iš E į poaibius priklausomai nuo to, kokiai aibės V viršūnei tos briaunos yra incidentinės. Pavyzdžiui, grafui piešinyje PV ={{ e9,e6,e8},{ e3,e2 }, { e1 }, { e4,e5 },{ e7 }}. Analogiškai (tik aibės U atžvilgiu) apibrėžiamas matroidas R2 . Jis atitinka suskaidymui PU ={{ e9,e7},{ e6,e3,e4},{ e8,e5 }, { e1,e2}}.

MATROIDŲ CHARAKTERIZACIJA

Teorema. Tegul S=(E,I) – nepriklausomumo sistema. Tada tokie tvirtinimai yra ekvivalentiški.

S- matroidas.

Jeigu Np, Np+1ĪI, čia | Np |=p ir | Np+1|=p+1, tai egzistuoja toks elementas eĪ Np+1- Np , kad Np +eĪI.

Jeigu A –

aibės E poaibis ir N, N¢, – maksimalūs pagal elementų įjungimą nepriklausomi aibės A poaibiai, tai | N¢|=|N|.

Įrodymas.(1)Ž(2). Tarkime, kad S – matroidas, bet (2) yra pažeidžiama, t.y. egzistuoja tokie du nepriklausomi poaibiai Np, Np+1, kad | Np |=p ir | Np+1|=p+1, ir kiekvienam eĪ Np+1- Np poaibis Np +e yra priklausomas. Tegul aibėje E duoti svoriai W:

ģ p+2, eĪ Np

W(e)=ķp+1, eĪ Np+1- Np

ī0, eĻ NpČ Np+1.

Galima pastebėti, kad poaibis Np yra neoptimalus, kadangi W(Np+1)³(p+1)2>p(p+2)=W(Np). Tuo tarpu godus aalgoritmas kaip tik ir suformuoja šitą poaibį, rinkdamas elementus eĪ Np pagal W(e) maksimumą. Prie Np jau neįmanoma prijungti elemento eĪ Np+1- Np, taigi gauname, kad S nėra matroidas. Tai prieštarauja pradinei prielaidai.

(2)Ž(3). Tarkime, kad yra tenkinama sąlyga (2), ir tegul N, N¢ – du maksimalūs pagal įjungimą aibės AĶE nepriklausomi poaibiai. Tarkime priešingai savybei (3), kad | N¢|<|N|. Atmetant |N¢|-|N|-1 elementą iš N¢, galima gauti tokią aibę N¢¢Ķ N¢, kad | N¢¢|=|N|+1. Aišku, kad N¢¢ĪI. Iš (2) seka, kad eegzistuoja toks elementas eĪ N¢¢-N, kad N+eĪI. Bet tai prieštarauja prielaidai, kad N – maksimumas pagal įjungimą aibės A nepriklausomas poaibis. Taigi reikalinga implikacija įrodyta.

(3)Ž(1). Tarkime, kad sistemai S galioja (3). Parodysime, kad tada godus algoritmas visada suranda optimalų uždavinio ssu S sprendinį. Priimkime priešingą prielaidą, kad taip nėra, t.y. prie tam tikrų svorių W(e), eĪE, godus algoritmas duoda nepriklausomą aibę N={ e1,e2, . . .,ei}, nors egzistuoja aibė J={ e1¢,e2¢, . . ., ej¢}ĪI tokia, kad W(J)>W(N). Galima laikyti, kad aibių N ir J elementai sutvarkyti taip, kad W(e1)³ W(e2)³ . ³W(ei), W(e1¢)³ W(e2¢)³ . ³W(ej¢), o J yra maksimalus pagal įjungimą aibės E nepriklausomas poaibis. Pagal apibrėžimą tokiu yra ir poaibis N. Todėl pagal (3) i=j. Parodysime, kad visiems m=1,2, . ,i teisinga nelygybė W(em)³ W(em¢). Tuo pačiu bus gautas prieštaravimas pradinei prielaidai. Kad parodyti šių nelygybių teisingumą, naudosime indukciją pagal m. Prie m=1 W(e1)³ W(e1¢). Tarkime, kad prie fiksuoto m>1

W(em)< W(em¢), nors W(es)³ W(es¢), s=1, . .. . , m-1. Apibrėžkime aibę A={eĪE; W(e)³ W(em¢)}. Aibė R={ e1, . , em-1} yra maksimalus pagal įjungimą aibės A nepriklausomas poaibis. Nes priešingu atveju egzistuotų poaibis RČ{e}ĪI toks, kad W(e)³ W(em¢)>W(em). Bet tada godus algoritmas turėtų išrinkti vietoj em elementą e. Seka, kad kitas nepriklausomas aibės A poaibis

{ e1¢, . . ., em¢} yra didesnio galingumo negu R. Tačiau tia prieštarauja (3). Teorema įrodyta.

1 apibrėžimas. Tegul S=(E,I) – matroidas ir AĶE. Aibės A rangu r(A) vadinamas maksimalaus nnepriklausomo aibės A poaibių galingumas. Visi aibės E poaibiai B tokie, kad |B|=r(E), vadinami bazėmis.

Akivaizdu, kad matroidas vienareikšmiškai yra nusakomas jo bazių sistema b, t.y. I={N:NĶB, bent vienai bazei BĪb}.

2 apibrėžimas. Aibės E poaibis D, nepriklausantis I, vadinamas priklausomu. Minimalus pagal įjungimą priklausomas poaibis CĶE vadinamas ciklu.

TRANSVERSALIŲ MATROIDAI

Tegul A={A1, . , An} – duotos baigtinės aibės E poaibių šeima. Aibė S={e1, . , ek}ĶE vadinama šeimos A daliniu transversaliu, jeigu kažkokiam indeksų {1, . . . , k} perstatymui f ir kažkoiai indeksų sekai 1£i1£ . . . £ik£n seka (ef(1), . . . , ef(k)) yra sekos (Ai1, . . . , Aik) skirtingų atstovų sistema. Elementas ef(ℓ) “atstovauja” Aiℓ.

Teorema. Tegul duota šeima A, apibrėžta aibėje E, ir tegul I yra šeimos A dalinių transversalių rinkinys. Tada M(A)=(E,I) yra matroidas (vadinamas šeimos A transversalių matroidu).

Šeimą A galima vaizduoti dvipusiu grafu H su viršūnėmis u1, . . . , um, atitinkančiomis aibei E={e1, . , em}, ir viršūnėmis v1, . . . , vn atitinkančiomis poaibiams Ai, i=1,2,.,n, bei briaunomis (ui,vj), kai eiĪAj. Sekos (Aj1, . . . , Ajk) skirtingų atstovų sistemai (ei1 , . . . , eik) grafe H atitinka suporavimas M={ (ui1,vj1), . . . , ((uik,vjk)}.

Tarkime, kad aibės E elementams yra priskirti neneigiami svoriai, ir e1, . , em yra surašyti svorių nedidėjimo tvarka.

Godus algoritmas traversalių matroidui atrodo taip.

Begin

S:=Ę; M:=Ę;

for i:=1 to m do

if grafe egzistuoja padidinanti besikaitaliojanti grandinė P suporavimo M atžvilgiu, kurios pradžia yra ei

then

begin S:=SČ{ ei }; M:=MDP

end ­

end simetrinis skirtumas

ALGORITMŲ SUDĖTINGUMAS

Pagrindine algoritmų charakteristika yra laikomas vykdomų operacijų kiekis. Ši algoritmo charakteristika yra vadinama jo sudėtingumu. Aišku, kad algoritmo sudėtingumas priklauso nuo konkretaus sprendžiamo uždavinio apimties.Kiekvieną uždavinį galima užkoduoti, naudojant kokio tai pasirinkto alfabeto simbolius. Labiausiai natūralus – tai dvejetainis alfabetas, papildytas pagalbiniais simboliais. Tada uždavinio apimtis – tai simbolių skaičius jo užkodavime.Paprastai uždavinio apimtį galima išreikšti asimptotiškai, naudojant vieną, o kartais du ar daugiau, charakteringų tam uždaviniui parametrų. Pavyzdžiui, jeigu uždavinys susijęs su grafu, tai tokiu parametru gali būti viršūnių skaičius. Arba gali būti du parametrai: viršūnių skaičius ir briaunų skaičius. Jeigu uždavinio apimtis būna nusakyta asimptotiškai, tai, natūralu, ir uždavinio sudėtingumas yra vertinamas asimptotiškai. Tam naudojami simboliai O,W ir q.

Apibrėžimas. Tegul f(n) ir g(n) – funkcijos, apibrėžtos teigiamų sveikų skaičių aibėje ir įgyjančios teigiamas realias reikšmes.

a) Rašysime f(n)=O(g(n)), jeigu egzistuoja tokia konstanta c>0, kad f(n)£ cg(n) prie pakankamai didelių n.

b) Rašysime f(n)=W(g(n)), jeigu egzistuoja tokia konstanta c>0, kad ff(n)³ cg(n) pakankamai dideliems n.

c) Rašysime f(n)=q(g(n)), jeigu egzistuoja tokios konstantos c,c¢>0, kad cg(n)£f(n)£c¢g(n) pakankamai dideliems n.

Pavyzdžiui, duotas masyvas A(n)={a1,.,an}. Galimi tokia uždaviniai: 1) surasti didžiausią elementą; 2) surinkti elementus mažėjimo tvarka. Pirmuoju atveju, sudėtingumas lygus q(n). Antruoju atveju, algoritmui, pagrįstam didžiausio elemento kiekviename žingsnyje išrinkimu, sudėtingumas įvertinamas dydžiu q(n2). Yra įrodyta, kad uždavinio sudėtingumas yra lygus q(nlogn) (nes yra gautas jo įvertinimas Ω(nlogn) ir yra sudaryti algoritmai, kurių sudėtingumas

Ο(nlogn)).

Šiuo metu vyrauja nuomonė, kad sprendžiant bent vidutinės apimties uždavinius, kurių sudėtingumas neviršija q(nc), c – kokia tai konstanta. Tokie algoritmai vadinami polinominiais. Paprastai konstanta c neviršija 3. Kita grupė algoritmų yra tokie, kuriems sudėtingumas įvertinamas dydžiu c12c2nc3. c1, c2, c3 – konstantos. Tokie algoritmai vadinami eksponentiniais (pagal sudėtingumą). Eksponentinio greičio pavyzdžiai gali būti tokie: n!, 2n2, kn, k – konstanta, nn, nlogn. Eksponentiniai algoritmai praktikoje naudojami tiktai sprendžiant mažos apimties uždavinius.

19. KLASĖS P IR NP

Nagrinėsime kombinatorinį uždavinį su leistinų sprendinių aibe S ir vertės funkcija f: S®R. Laikysime, kad S ir f užduoti netiesiogiai dviem algoritmais As ir Af. Pirmasis algoritmas duotiems kombinatoriniam objektui s ir parametrų aibei T nustato ar sĪS, čia S yra priklausomas nuo parametrų aibės T. Algoritmas Af, esant duotiems leistinam sprendiniui s

ir parametrų aibei Q, išduoda reikšmę f(s). Kiekvienas individualus kombinatorinis uždavinys yra nusakomas parametrų aibėmis T ir Q. Pavyzdžiui, komivojažerio uždaviniui T -tai sveikas teigiamas skaičius n, reiškiantis miestų skaičių, o Q – tai simetrinė atstumų matrica ||dij||nxn.

Tokiu būdu kombinatorinis optimizacinis uždavinys gali būti formuluojamas taip: duotoms parametrų aibėms T ir Q, susijusioms su algoritmais As ir Af , aibėje S surasti optimalų pagal f sprendinį. Tai optimizacinis uždavinio variantas. Kitas, vadinamas skaičiuojamuoju variantu, yra toks: esant duotiems T iir Q, nustatyti optimalaus sprendinio vertę. Pagaliau trečiame uždavinio variante, vadinamame atpažinimo variantu, prie duotų T, Q ir sveiko skaičiaus L yra reikalaujama nustatyti ar egzistuoja toks leistinas sprendinys sĪS, kuriam f(s)£L.

Prie tam tikrų silpnų ir visai realistiškų prielaidų atpažinimo ir optimizacinis uždavinio variantai yra praktiškai ekvivalentiški. Kitaip tariant, optimizacinį uždavinį galima išspręsti iškviečiant atpažinimo varianto sprendimo algoritmą ne daugiau kaip polinominį skaičių kartų.

Uždavinių klasę P sudaro atpažinimo uždaviniai, kurie gali būti išsprendžiami polinominio algoritmo pagalba. Polinomiškumo reikalavimas gali bbūti apibrėžiamas bet kokio protingo skaičiavimo modelio, pavyzdžiui, Tiuringo mašinos atžvilgiu. Klasei P priklauso, pavyzdžiui, grafo surištumo nustatymo, trumpiausio kelio orgrafe išskyrimo, maksimalaus suporavimo sudarymo ir minimalaus padengiančio medžio ieškojimo uždaviniai.

Tegul å – fiksuotas baigtinis alfabetas ir $ – iišskirtas iš å simbolis. Jeigu x – simbolių, priklausančių å, eilutė, tai jos ilgį žymėsime |x|.

Apibrėžimas. Laikysime, kad atpažinimo uždavinys U priklauso klasei NP, jeigu egzistuoja polinomas p(n) ir algoritmas A, vadinamas patvirtinimo tikrinimo algoritmu, kuriems teisinga tokia savybė: eilutė x koduoja konkretų U tipo uždavinį (nusakomą parametrų aibėmis T ir Q) ir šiam uždaviniui galioja atsakymas “taip” tuomet ir tiktai tuomet, jeigu egzistuoja tokia simbolių iš å eilutė c(x), vadinama patvirtinimu, kad |c(x)|£p(|x|), ir algoritmas A prie įėjimo x$c(x) išduoda atsakymą “taip” po ne daugiau kaip p(|x|) žingsnių.

Pagalbinis simbolis $ pažymi uždavinio kodavimo pabaigą ir patvirtinimo pradžią.

1 pavyzdys. KLIKA.

Duoti grafas G=(V,E) ir sveikas skaičius k. Nustatyti, ar šiame grafe egzistuoja dydžio k klika, t.y. pilnas grafo GG pografis, turintis k viršūnių.

Tegul šiame uždavinyje x reprezentuoja grafą G ir skaičių k, kuriems teisingas atsakymas “taip”. Patvirtinimas c(x) eilutei x – tai reikiamo dydžio klikos C viršūnių sąrašas. Jo tikrinimo algoritmas A pirmiausia nustato ar iš tikro eilutė x yra užkoduotas grafas G ir sveikas skaičius k, o eilute c(x) – viršūnių aibė C, |c|=k. Po to algoritmas kiekvienai klikos C viršūnių porai u,v tikrina ar grafas G turi briauną (u,v). Jei visas briaunas turi, tai algoritmas iišduoda atsakymą “taip”. Polinomas p(n) gali būti lygus 2n2.

2 pavyzdys. STP.

Duota sveikakaitinė (mxn)-matrica D ir sveikaskaitinis m-vektorius b. Nustatyti, ar egzistuoja sveikaskaitinis n-vektorius x, kuriam Dx=b, x³0.

Formuluojant šį atpažinimo uždavinį nėra reikalo išskirti sveiką skaičių L ir nelygybę c¢x£L, nes tokią nelygybę, panaudojus fiktyvų kintamąjį, galima įtraukti į lygčių sistemą. Yra įrodoma, kad tuo atveju, kai STP uždavinys turi leistiną sprendinį, tai jis turi taip pat tokį sprendinį, kurio kiekviena komponentė neviršija M=n*(ma1)2m+3(1+a2), čia

a1=max|aij|, a=max|bi|.

i,j i

Šio apriboto sprendinio dvejetainis kodas gali būti imamas kaip patvirtinimas c(x) uždaviniui su atsakymu “taip”. Dvejetainio kodo ilgis yra polinominis įėjimo parametrų atžvilgiu. Tokiu būdu STP priklauso klasei NP.

Pastaba. Uždavinių klasė P yra klasės NP poaibis. Iškyla klausimas: ar P=NP? Į šį klausimą atsakymo iki šiol nėra.

20. POLINOMINIS SUVEDIMAS

1 apibrėžimas. Tegul U1 ir U2 – atpažinimo uždaviniai. Sakysime, kad uždavinys U1 per polinominį laiką (arba polinomiškai) suvedamas į uždavinį U2 tada ir tiktai tada, kada egzistuoja polinominis algoritmas A1 uždaviniui U1 spręsti, naudojantis kaip paprogramę, kurios kaina lygi 1, algoritmą A2, išsprendžiantį uždavinį U2. Algoritmas A1 yra vadinamas uždavinio U1 polinominiu suvedimu į U2.

Pagal šį apibrėžimą algoritmas A2 yra traktuojamas kaip operatorius, kuriam įvykdyti užtenka vieno laiko vvieneto.

Teiginys. Jeigu uždavinys U1 polinomiškai suvedamas į U2 ir egzistuoja polinominis algoritmas uždaviniui U2 spręsti, tai tuomet egzistuoja polinominis algoritmas ir uždaviniui U1.

Įrodymas. Tegul p1(n) ir p2(n) – polinomai, apribojantys algoritmų A1 ir A2 sudėtingumą. Čia p1 yra duotas, įvertinant tai, kad A2 turi vienetinę kainą. Todėl realus algoritmo A1 sudėtingumas apribotas dydžiu p(n)=p1(n)* p2(p1(n)). Tai seka iš tokių dviejų pastebėjimų. Pirma, blogiausiu atveju algoritmas A1 gali susidėti vien iš kreipinių į algoritmą A2, kiekvieną kartą perduodamas jam maksimalaus ilgio įėjimo informaciją. Tokių kreipinių, aišku, ne daugiau p1(n). Antra, algoritmo A2 įėjimo informacijos maksimalus ilgis negali viršyti p1(n) netgi tuomet, kada algoritmas A1 kiekviename žingsnyje formuoja šią informaciją.

2 apibrėžimas. Sakysime, kad atpažinimo uždavinys U1 polinomiškai transformuojamas į kitą atpažinimo uždavinį U2, jeigu duotai bet kuriai eilutei x galima polinomiškai (atžvilgiu |x|) suformuoti tokią eilutę y, kad x yra konkretaus U1 tipo uždavinio kodavimas su atsakymu “taip” tada ir tiktai tada, kada y yra konkretaus U2 tipo uždavinio kodavimu su atsakymu “taip”.

Polinominės transformacijos yra suprantamos kaip polinominiai suvedimai su vieninteliu paprogramės uždaviniu U2 iškvietimu algoritmo uždaviniui U1 pabaigoje. Polinominės transformacijos pavyzdys jau buvo pateiktas – tai patenkinamumo uždavinio pertvarkymas į STP uždavinį.

21. NP – PILNUMAS

Apibrėžimas. AAtpažinimo uždavinys UĪNP vadinamas NP-pilnu, jeigu visi kiti uždaviniai priklausantys klasei NP, polinomiškai transformuojami prie uždaviniu U.

Remiantis teiginiu iš praeito paragrafo galima nustatyti, kad NP-pilnas uždavinys U turi stiprią savybę: jeigu egzistuoja efektyvus uždavinio U sprendimo algoritmas, tai efektyvus algoritmas egzistuoja ir kiekvienam uždaviniui iš klasės NP spręsti.

NP-pilnų uždavinių samprata ir stiprus įtarimas, kad P¹NP, įgalina klasę NP įsivaizduoti taip, kaip parodyta 1 pav.

1 pav.

Lieka klausimas: ar egzistuoja NP-pilni uždaviniai? Atsakymas “taip” seka iš Kuko

teoremos.

1 teorema. Patenkinamumo uždavinys yra NP-pilnas.

Įrodymas gana ilgas ((rus.) Papadimitric C., Caiglic K. Kombinat..,1985, p. 364-369).

Tam, kad įrodyti, jog nagrinėjamas uždavinys yra NP-pilnas, užtenka nustatyti, kad

a) uždavinys priklauso klasei NP;

b) visi kiti uždaviniai iš NP polinomiškai transformuojami į nagrinėjamą uždavinį.

Pastaroji sąlyga yra keičiama ekvivalentine paprastesne.

b¢) žinomas NP-pilnas uždavinys polinomiškai transformuojamas į nagrinėjamą.

Teiginys. STP uždavinys yra NP-pilnas.

Tai, kad STPĪNP, buvo parodyta užpraeito paragrafo antru pavyzdžiu. Be to, patenkinamumo uždavinys yra suvedamas į STP.

3-patenkinamumo uždaviniu vadinsime patenkinamumo uždavinį, kurio kiekviename disjunkte radasi lygiai trys literalai.

2 teorema. 3-patenkinamumo uždavinys yra NP-pilnas.

Įrodymas. Aišku, kad 3-patenkinamumas priklauso klasei NP. Parodysime, kad patenkinamumas polinomiškai transformuojamas į 3-patenkinamumą. Tegul F – bet kokia formulė, susidedanti iš disjungtų C1,.,Cm. Sudarysime naują formulę F¢

su trimis literalais kiekviename disjunkte tokią, kad F¢ patenkinama tada ir tiktai tada, kada patenkinama formulė F. Peržiūrėdami kiekvieną formulės F disjunktą Ci atliekame tokius veiksmus.

1. Jeigu Ci susideda iš trijų literalų, tai Ci įtraukiame į F¢.

2. Jeigu Ci susideda iš daugiau negu trijų literalų, pavyzdžiui, ci=(l1+l2+.+lk), k>3, tai į F¢ įtraukiame k-2 disjunktus , čia x1,.,xk-3 – nauji kintamieji. Lengva įsitikinti, kad šie disjunktai yra patenkinami tada ir tiktai tada, kada patenkinamas disjunktas ci.

3.Jeigu ci=l , tai įį F¢ įtraukiame l+y+z, o jeigu ci=l+l¢, tai įtraukiame l+l¢+y. Be to pridedame disjunktus

,

čia y,z,a ir b – nauji kintamieji. Toks papildymas disjunktais garantuoja tai, kad kintamieji z ir y priims reikšmę 0 prie bet kokio kintamųjų reikšmių rinkinio, patenkinančio formulę F¢.

Įrodymas baigiamas pastebėjimu, kad formulė F¢ yra sudaroma per polinominį laiką.

3 teorema. Uždavinys KLIKA yra NP-pilnas.

Įrodymas. Jau žinome, kad KLIKAĪNP. Parodysime, kad 3-patenkinamumas polinomiškai transformuojamas prie klikos atpažinimo uždavinio. Esant duotai bet kokiai bulinei formulei ssu trimis literalais kiekviename disjunkte, sudarysime grafą G=(V,E) ir parinksime sveiką skaičių k, tokius, kad grafe G bus k dydžio klika tada ir tiktai tada, kada formulė F yra patenkinama.

Tegul x=(x1,.,xn) – kintamųjų vektorius. Rinkinį t vadinsime teisingumo reikšmių ddaliniu rinkiniu, jeigu kiekvienam kintamajam xi rinkinyje t atitinka viena iš reikšmių – 0,1,d. Reikšmė t(xi)=d pažymi neapibrėžtumą. Dalinį reikšmių rinkinį vaizduosime 0,1 ir simbolio d seka. Pavyzdžiui, t=d01d0 prie n=5 pažymi, kad t(x2)=0, t(x3)=1, t(x5)=0, o kitos reikšmės neapibrėžtos. Du teisingumo reikšmių dalkiniai rinkiniai t ir t¢ vadinami suderinamais, jeigu viesiems kintamiesiems xi tokiems, kad t(xi)¹d ir t¢( xi)¹d, galioja lygybė t(xi)= t¢(xi).

Tegul C1,.,Cm – formulės F disjunktai. Viršūnių aibei V priklausys po 7 viršūnes kiekvienam disjunktui Ci. Tegul jos pažymėtos tij, . Šios viršūnės atitinka teisingumo reikšmių daliniams rinkiniams, kuriose reikšmės priskirtos tiktai kintamiesiems, įeinantiems į Ci. Iš 8 tokių rinkinių yra atmetamas tiktai tas, prie kurio visų literalų reikšmės yra lygios 0. Grafo G briaunos sujungia vvisas viršūnių poras, atitinkančias suderinamiems rinkiniams. Grafo G fragmentas parodytas 2 pav. Priimkime k=m.

2 pav.

Jeigu sudarytame grafe G egzistuoja klika, kurios apimtis ne mažesnė kaip k, tai formulė F yra įvykdoma, ir atvirkščiai.