Kombinatorika

by

1.Naturalieji skaiciai. Matematines indukcijos principasNepriestaringumo desnis. Du vienas kitam priesingi teiginiai p ir ¯p vienu metu negali buti teisingi (p^¯p=0)Treciojo negalimo desnis. Is dvieju priesingu teiginiu p ir ¯p vienas visada yra teisingas (p^¯p=1).Apibrezimas. Naturaliaisiais skaiciais vadiname netuscios aibes N elementus, jeigu tarp kai kuriu is juegzistuoja sarysis ,,a‘ eina po a“, tenkinantis aksiomas:1) egzistuoja skaicius (vadinamas vienetu), neinantis po jokio kito skaiciaus;2) po kiekvieno skaiciaus eina tik vienas skaicius;3) kiekvienas skaicius eina ne daugiau kaip po vieno skaiciaus;4) aibes N poaibis M sutampa su pacia aibe N, jei jis turi tokias savybes:a) 1 $ M,b) jeigu skaicius a priklauso M, tai ir po a einantis skaicius a‘ taip pat priklauso aibei M Matematines indukcijos principasTegu p(n) – kazkoks teiginys apie naturaluji skaiciu n. Tarkime, kad p(1) yra teisingas, ir is prielaidos, kad p(n) yra teisingas, sugebame isvesti, kad p(n‘) irgi yra teisingas. Darome isvada: teiginys p(n) yra teisingas visiems n $ N.Archimedo aksioma. Bet kuriai naturaliuju skaiciu porai a, b galima rasti toki naturaluji skaiciu n, kad an>b.Maziausiojo elemento principas. Kiekvienas netuscias naturaliuju skaiciu aibes poaibis turi maziausia elementa.Dirichle (P.G.L. Dirichlet, 1805–1859) principas. Jei m rutuliu yra sudeti i n < m deziu, tai bent vienoje dezeje yra 2 ar daugiau rutuliu.

2.Dauginimo tasykleDekarto ( Rene Descartes, 1596–1650) sandauga. Tai sutvarkytuju poru aibe.A × B = {(ai, bj) : ai e A, bj e B, 1 ≤i ≤ n, 1 ≤ j≤ m}1 teorema. |A × B| = |A| |B|.2 teorema. Jei abecele A turi n raidziu, tai galime sudaryti n^k zodziu, kuriu ilgis yra k.3 teorema. Aibes A = {a1, . . . , an} poaibiu, iskaitant ir tusciaji, skaicius lygus 2^n.|>Nagrinekime visu poaibiu aibes atvaizdi aibeje, sudarytoje is n zodziu su ,,raidemis“ 0, 1. Sis atvaizdis apibreztas taip: A ] P = {ai1 , . . . , aik} 7! (0 . . . , 0, 1, 0 . . . , 0, 1, 0, . . . 0) cia ,,raide“ 1 irasyta is-oje pozicijoje pabreziant, kad is-asis aibes A elementas patenka i poaibi P. Atvaizdis yra bijekcija. Pagal 2 teorema siu zodziu aibes galia lygi 2^n ir sutampa su k poaibiu aibes galia.<|4 teorema. Jei X = {x1, . . . , xn} ir Y = {y1, . . . , ym}, tai funkciju f : X ->aibes galia lygi m^n. |>Kiekviena funkcija f : X ->galime vienareiksmiskai isreiksti vektoriumi (f(x1),…,f(xn)). Kadangi dabar ,,raide“ f(xj ), 1≤ j≤ n, imama is abeceles Y, turincios m raidziu, teoremos teiginys isplaukia is 2 teorem. <|Sioje teoremoje isvesta formule paaiskina daznai naudojama zymeni {f : X ->Y } =: Y^X .

3. Gretiniai, keliniai ir deriniai1 teorema. Ak/n = n(n − 1)(n − 2) • • • (n − k + 1).2 teorema. Deriniu is n po k skaicius lygus Ck/n = (Ak/n)/k!= n!/(k!(n − k)!)Mokslineje literaturoje vartojami ir tokie deriniu is n po k zymemys: (n//k)= (n//(k, n − k))Paimtas is n aibes k elementu rinkinys su galimais pasikartojimais vadinamas kartotiniu sios aibes k deriniu. Ju skaicius Hk/n = Ck/(n+k−1)=((n+k−1)//k)

4. Kartotiniai gretiniaiTeorema. Polinominiu koeficientu formule yra (n//(p1, . . . , pk)) |>Dauginkime panariui n nezinomuju sumu, imdami xi1 is pirmosios sumos, xi2 is antrosios sumos ir t.t., xin is n-osios sumos ir sudekime visas sandaugas(2) xi1 • • • xin. Kadangi ij 2 {1, . . . , k}, 1 ≤ j ≤ n, tai turesime k^n sandaugu (visus n zodzius is k raidziu x1, . . . , xk). Sudedant (2) sandaugas, reikia sutraukti panasius narius. Jie bus to paties pavidalo, t.y.(3) xp1/1 • • • xpk/k, nusakomo vektoriumi ¯p. Kiek tokiu panasiu nariu kaip (3)? Raide x1 (2) sandaugoje galejo uzimti p1 poziciju is n galimu, t.y. buvo (n//p1) budu, x2 – ((n−p1)//p2 ) budu ir t.t. Tesdami si procesa, gautume (n//p1)• ((n−p1)//p2)•••((n−p1−p2−•• •− pk−1)//pk )= n!/(p1! . . . pk!) Cia pasinaudojome binominio koeficiento formule.<|

5. Binominiu koeficientu tapatybesPatogu isplesti binominio koeficiento apibrezima:(z//k)= { 1.(z(z−1)…(z−k+1))/k! , kai z e C, k e N U {0},2.0, kai k < 0.1 teorema. (n//k)= ( n//(n − k)), 0≤k≤n.2 teorema.Hk/n = ((n + k − 1)//k )= (−1)^k*(-n//k ), 0≤k≤n.3 teorema.(n//k)*(k//m)=(n//m)*((n − m)//(k − m)), 0≤m≤k≤n.

4 teorema (Paskalio tapatybe).(n//k)=((n − 1)//(k − 1))+((n − 1)//k), 0≤ k≤n, ((n − 1)//n)= 0.5 teorema. (n ∑k=0) ((r + k)//k)=((r + n + 1)//n).6 teorema (Ortogonalumo sarysis) Tegu δmn – Kronekerio simbolis, t.y. δnn = 1ir δmn = 0, kai m≠n. Jei m≤n, tai Snm :=(n∑k=m)(−1)^k(n//k)*(k//m)= (−1)^mδmn.|>Pagal 3 teorema Snm =(n∑k=m)(−1)^k(n//m)*((n − m)//(k − m))=(n//m)(n∑k=m)(−1)*k((n − m)//(k − m))Pakeiskime sumavimo indeksa k − m = j ir gausime Snm = (n//m)(n−m∑j=0)(−1)^(j+m)((n−m)//j) = (−1)^m(n//m)(1 − 1)^(n−m) = 0,jei m≠n.<|7 teorema (Apgrezimo sarysis) Tegu ak, bk, 0≤k≤n – dvi skaiciu sekos. Is vienos is siu lygybiu bn = (n∑k=0)(−1)^k(n//k)ak, an = (n∑k=0)(−1)^k(n//k)bk isplaukia antroji.|>Jei teisinga pirmoji lygybe, tai istatydami patikriname antraja. Skaiciuojame keisdami sumavimo tvarka (n∑k=0)(−1)^k(n//k)bk =(n∑k=0)(−1)^k(n//k)*(k∑m=0)(−1)^m(k//m)am = (n∑m=0)(−1)^m*am (n∑k=m)(−1)^k (n//k)*(k//m) = anδnn = an. Paskutiniame zingsnyje pritaikeme ortogonalumo sarysi (6 teorema). <|8 teorema (Harmoniniu skaiciu savybe). 1+1/2+ • • • +1/n = (n∑k=1)(−1)^(k+1)(n//k)*1/k.|> Desiniojoje lygybes puseje esanciam binominiam koeficientui pritaikykime Paskalio lygybe. Gauname hn := (n∑k=1)(−1)^(k+1)(n//k)1/k = (n∑k=1)(−1)^(k+1)(((n − 1)//k)+((n − 1)//(k − 1))1/k = hn−1 + (−1)^(n+1) ((n − 1)//n)1/n + (n∑k=1)(−1)^(k+1)((n − 1//(k − 1))1/k (1) Antrasis demuo lygus nuliui, skaiciuojame treciaji. Jis lygus (n∑k=1)(−1)^(k+1) ((n − 1)!)/(k!(n − k)!) = −1/n (n∑k=1)(−1)^k(n//k) = −1/n[(1 − 1)^n − 1] = 1/n. Istate i (1) lygybe gauname rekurentuji sarysi hn = hn−1 + 1/n. Kadangi f1 = 1, pagal matematines indukcijos principa is jo isplaukia hn = 1 + 1/2+1/3+ • • • +1/n. <|

6. Recio principasSkaiciuosime skaiciu elementu, patenkanciu i keletos gal but persikertanciu aibiu sajunga. Apibendrinsime nesunkiai suvokiamas formules |AUB| = |A| + |B| − |A∩B| ir (1) |AUBUC| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.1 teorema.|A1U • • •UAn| = S1 − S2 + S3 + • • • + (−1)^(n+1)Sn.|> Pazymekime U = A1U• • •UAn. Fukcija IA : U -> {0, 1} vadinsime poaibio A C U indikatoriumi, jeigu IA(x) = 1 tada ir tik tada, kai x e A. Vadinasi, |A| = (∑x2U)IA(x). Todel a(i) = (∑x2U)IAi (x), a(i, j) =(∑x2U)IAi∩Aj (x), . . . , a(i1, . . . , ik) =(∑x2U)IAi1 ∩•••∩Aik(x), 1≤iJei ¯Ai := X Ai, tai nagrinejamas skaicius lygus |¯ A1∩• • •∩¯An| = |X (A1U• • •UAn)| = |X| − |A1U ••• UAn|.Toliau pakanka pritaikyti 1 teorema. <|

7. Netvarku uzdavinysTeorema. Netvarkinguju keitiniu skaicius lygus n!(n∑k=0)((−1)^k)/k! . |>Bendras keitinio pavidalas ((1 2 . . . n)//(i1i2 . . . in)). Tegu Ak – aibe keitiniu su savybe ik = k, X – visa keitiniu aibe, o ¯Ak = XAk, 1≤k≤n. Ieskomasis skaicius pagal 6.2 teorema lygus |¯A1∩ ••• ∩¯An| = |X| −(n∑i=1)|Ai| + (∑1≤iJei U – visu atvaizdziu aibe, tai |U| = mn. Tegu Y = {y1, . . . , ym}, o Aj – atvaizdziai, neigyjantys reiksmes yj , 1≤j≤m. Pagal ta pacia atvaizdziu skaiciaus teorema gauname |Aj | = (m − 1)^n, |Ai∩Aj| = (m − 2)^n, . . . , |Ai1∩•••∩Aik| = (m − k)^n. Cia 1≤i< j≤m, 1≤i1 < i2 • • • < ik≤m. Siurjekciju vaizdai yra visi yj , todel mus dominanti aibe yra lygi aibiu Aj papildiniu iki U sankirtai, t.y., S :=¯A1∩¯A2∩•••∩¯An. Pagal praeito skyrelio teoremos isvada (1) |S| = |U| − S1 + S2 − • • • + (−1)^mSm. Cia S1 = (m//1) * (m−1)^n, S2 = (m//2) * (m−2)^n, . . . , Sm−1 = (m//(m − 1)) * (m−m+1)^n, Sm = 0. istate i (1) formule, baigiame irodyma <| Isvada. n! = (n∑k=0)(−1)^k (n//k) * (n − k)^n, n≥1. |> Kiekviena n aibes siurjekcija i ja pacia yra ir bijekcija, o bijekciju skaicius sutampa su n keitiniu kiekiu. Toliau pritaikome teorema, kai n = m <|

9. Stirlingo skaiciaiAibes A skaidiniu (k skaidiniu) vadiname israiska (1) A = A1U•••U Ak, AjCA, Aj ≠ (tuscia aibe); Ai∩Aj = (tiscia aibe), 1≤i Jei A = {a1, . . . , an}, f e Q(n, k), tai pazymeje Aj = {ai e A : f(i) = j}, 1≤j≤k, gauname vieninteli skaidiniA = A1U…Ak. Atvirksciai, turedami toki skaidini, galetume apibrezti daug siurjekciju. Pakaktu aibes Aj elementus atvaizduoti i viena skaiciu ij taip, kad skaiciai i1, . . . , ik sudarytu k kelini. Kadangi tokiu keliniu yra k!, is viso gautume k! siurjekciju. Taigi |Q(n, k)| = k!S(n, k). Toliau pakanka pritaikyti (2) formule <|

Jei Bn – visu galimu A israisku, jungiant netuscius poaibius, skaicius, vadinamas Belo skaiciumi, tai Bn = (n∑k=1)S(n, k).2 teorema. Susitarkime, kad S(0, 0) = 1. Tada S(n, k) = kS(n − 1, k) + S(n−1, k−1), 1≤k< n.|> Panasiai kaip ir Paskalio teoremos irodyme, visus aibes A k skaidinius perskirkime i dvi dalis. Viena dali sudarykime is tokiu skaidiniu, kuriuose vienas is jungiamu poaibiu yra {n}. Ju pavidalas bus toks: A = A1U…Ak−1U {n}. Cia poaibiuose Aj , 1≤k−1, nera n. Tokiu skaidiniu bus S(n−1, k−1).Kita dali sudarantys likusieji skaidiniai gali buti gauti tokiu budu. Imkime aibes {1, . . . , n − 1} k skaidinius {1, . . . , n − 1} = A‘/1U•••UA‘/k, kuriu bus S(n−1, k), ir prijungdami paeiliui n prie A‘/j , 1≤j≤k, is kiekvieno tokio skaidinio padarytume k pradines aibes A skaidiniu. Todel antroje skaidiniu grupeje yra kS(n−1, k) A skaidiniu. Sudeje abieju klasiu skaicius, gauname S(n, k). <|Isvada. Jei 1≤ k≤n, tai S(n, k) ≤k^(n+1). Irodyti, pagal indukcija.3 teorema. Jei S(n, 0) := 0, kai n e N, ir S(0, 0) = 1, tai x^n =(n∑k=0)S(n, k)(x)k, x e R, n≥0, 0^0 := 1.|>Atvejis n = 0 yra trivialus. Tegu toliau n e N. Irodinejamos lygybes pusese yra n laipsnio polinomai, todel pakanka ja patikrinti daugiau negu n tasku. Irodysime, kad ji teisinga su visais naturaliaisiais x≥n. Tuo tikslu, nagrinejame atvaizdzius g : A -> X := {1, 2, . . . , x}. Ju yra xn. Si kieki skaiciuojame kitu budu. Tegu Y = g(X) C X – funkcijos g reiksmiu aibe. Tada g : A -> Y yra siurjekcija. Poaibiuose Y gali buti 1, 2, . . . , n elementu. Jei |Y | = k, tai gausime |Q(n, k)| skirtingu siurjekciju, atitinkanciu skirtingus atvaizdzius g. Pakeite Y C X, vel gautume skirtingas siurjekcijas bei atvaizdzius. Vadinasi, visas atvaizdziu g skaicius gali buti uzrasomas sitaip: xn = (n∑k=1)( ∑Y _X, |Y|=k)|Q(n, k)|. Pagal 2 teorema x^n = (n∑k=1)( ∑Y _X, |Y |=k)S(n, k)k! = (n∑k=1)S(n, k)k! (∑ Y _X, |Y |=k)1 =(n∑k=1) S(n, k)(x)k, nes aibe X turejo (x//k) skirtingu k poaibiu. Jei n e N, pagal susitarima S(n, 0) = 0, todel pastarojoje sumoje galetume prijungti nulini demeni, atitinkanti k = 0. Taip gautume teoremoje nurodyta formule <|Formule (x)n = (n∑k=0)s(n, k)x^k, x e R, apibrezia pirmos rusies Stirlingo skaicius s(n, k).4 teorema (Ortogonalumo sarysis) (n∑k=m)S(n, k)s(k,m) = δmn, m, n≥0.|> Pasinaudokime auksciau nagrinetu polinomu israiskomis per Stirlingo skaicius. Gauname x^n =(n∑k=1)S(n, k)(x)k = (n∑k=1)S(n, k) * ((k∑m=0) s(k,m)x^m) = (n∑m=0)((n∑k=m)S(n, k)s(k,m))x^m. Palygine polinomu koeficientus prie vienodu x laipsniu, baigiame 4 teoremos irodyma <|Rekuriancioji Belo formule: Bn = (n∑k=1) ((n − 1)//(k − 1))Bn−k, n e N.

10. Skirtumo operatoriusΔ^m =Δ(Δ^(m−1)), kai m >=0, Δ^1= Δ; Δ^0 = I, cia I tapatusis atvaizdis.1 teorema. Bet kokiai funkcijai f(x) ir m >= 0 teisingos tapatybes1) Δ^m f(x) =(mΣk=0)(−1)^k (m//k) f(x + m − k) =(mΣk=0)(−1)^(m−j) (m//j) f(x + j),2) f(x) =(mΣk=0)(−1)^k(m//k)Δ^k f(x)3) f(x + m) =(mΣk=0)(m//k)Δ^k f(x)|>Pirmoji is (1) lygybiu irodoma matematines indukcijos pagalba, pasinaudojant Paskalio tapatybe. Patikrine (1) su m = 0, 1 ir tare kad ji si lygybe yra teisinga del m−1>=1, skaiciuojame suma Sm:=(mΣk=0)(−1)^k(m//k)* *f(x+m−k)=(mΣk=0)(−1)^k(m−1//k)f(x+m−k)+ +(mΣk=0)(−1)^k(m−1//k−1)f(x+m−k). Gautose sumose atmete po nulini demeni, o antroje dar ir pakeite k-1=j, gau-name Sm=(m-1Σk=0)(-1)^k(m–1//k)f((x+1)+(m-1)-k)-(m-1Σj=0)(-1)^j(m–1//j-1)f(x+(m-1)-j)=Δ^(m-1)f(x + 1) – Δ^(m-1)f(x) = Δ^(m-1)(f(x + 1) – f(x)). <|Isvada. Jei n,m >=0, tai (Δ^m)(x^n)=(mΣk=0)(-1)^k(m//k)(x + m – k)^n;

(Δ^m)(0^n) := Δ^m)(x^n)|x=0 =(mΣk=0)(-1)^k(m//k)^nDydziai (Δ^m)(0^n), m,n>=0, vadinami Morgano skaiciais. Jei m<=n – tai n aibes siurjekciju I m aibe skaicius, ir jei m > n, tai bet kokiam x € R, (Δ^m)(x^n)=0. Is tiesu, kiekvienas operatoriaus Δ pritaikymas sumazina polinomo x^n laipsni vienetu. Kai x = 0, is cia isplaukia tapatybe(Δ^m)(0^n) =(mΣk=0)(-1)^k(m//k)(m-k)^n=0, m>n.Kadangi atveju m > n ir siurjekciju skaicius lygus nuliui, tai darome isvada, kad Morgano skaiciai visada isreiskia siurjekciju kieki.

11. Laipsnine generuojanti funkcijaFormali laipsnine eilute a0+a1x+a2x^2+•••+anx^n+… vadinama sekos generuojancia funkcija (l.g.f.).1 teorema (Vandermondo sasuka). Bet kuriems naturaliesiems skaiciams k ir m, k,m < n, teisinga lygybe (n//k)=(kΣj=0)(m//j)*(n – m//k – j) |> Panaudoje laipsniniu eiluciu (siuo atveju, polinomu) dauginimo taisykle, gauname (1+x)^n = (1+x)^(n-m)(1+x)^m =(Xi>=0 )(n – m//i)x^i(Σj>=0)(m//j)x^i==(Xk>=0)((Xi,j>=0,i+j=k(n-m//i)(m//j))x^m. Sulygine koeficientus prie x^k, baigiame teoremos irodyma <|2 teorema. Su bet kokiu n >= 0 teisinga lygybe (nΣk=0)((-1)^k+1/k + 1)(n//k)= – 1/n+1Apibendrintoji Niutono binomo formule (1=x)^u=(ooΣk=0)(u//n)x^n, x,u $ R, |x|<1

12. Katalano skaiciai1 teorema. Yra Cn =(1/n)(2n – 2//n – 1) n>=2 demenu suskliaudimo budu. Skaiciai Cn vadinami Katalano vardu.

13. Eksponentines generuojancios funkcijos Sekos {an}, n>= 0 eksponentine generuojancia funkcija (e.g.f.) vadinama formali eilute f(x) := a0 + a1x/1!+ a2x^2/2!+…+anx^n/n!+ . . . .Lema. Jei f(x) – sekos {an} e.g.f., tai f0(x) – sekos {an+1}, n>=0 e.g.f.. Formali suma f(x) + g(x) atlikta panariui yra sekos {an + bn}, n >=0 e.g.f., o sandauga f(x)g(x)– sekos cn :=(nΣk=0)(n//k)akb(n-k) e.g.f.Isvada. Belo skaiciu sekos {Bn}, n >=1, e.g.f. lygi B(x) := exp{e^x – 1}. |> Is rekurenciosios formulas Bn+1 =(nΣk=0)(n//k)Bk ir is Lemos isplaukia sarysis B0(x) = e^xB(x). Sios diferencialines lygties sprendinys su salyga ir yra isvados funkcija.2 teorema. Tegu s(n, k) – pirmos rusies Stirlingo skaiciai. Sekos {s(n, k)}, n>=k e.g.f. lygi fk(x) :=(Xn>=k)s(n, k)*(x^n/n!)=(1/k!)(log(1 + x))^k, |x| < 1, k>=0.

14. Rekurentieji sarysiaiNagrinesime sekas, kuriu n-tasis narys tam tikra formule yra isreiskiamas per jos narius su mazesniais indeksais. Be to, vienetinumui uztikrinti nurodoma pirmuju sekos nariu. Tokios israiskos vadinamos rekurenciosiomis formulemis.

15. Rekurentieji sarysiai. Bendra teorijaTarkime, kad seka {un}, n>= 0 yra apibrezta r eiles sarysiu un+r + a1un+r-1 + • • • + arun = 0, n>=0, ir pradiniais nariais u0, u1, . . . , ur-1. Sio pavidalo formules vadiname tiesiniais homogeniniais rekurenciaisiais sarysiais, o polinomas A(x) =(rΣj=0)ajx^j , a0 := 1vadinamas charakteristiniu polinomu.1 teorema. Sandauga A(x)U(x) yra polinomas D(x) :=(r-1Σk=0)dkx^k su dk =(kΣj=0)aju(k-j), 0<=k<=r – 1. |> Daugindami A(x) ir U(x) panariui, gauname laipsnine eilute su koeficientais dk =(kΣj=0)aju(k-j). Cia laikome, kad aj = 0 , kai j>= r + 1. Jei k <=r – 1, formule yra ieskomoji. Imkime paeiliui k = r, r+ 1, . . . ir naudodami un+r + a1un+r-1 + • • • + arun = 0, isitikinkime, kad tada dk=0.Isvada. Generuojanti funkcija U(x) = D(x)/A(x) yra racionalioji funkcija.Toliau funkcijai U(x) taikysime racionaliuju funkciju teorija. Tokiu funkciju kune C(x) egzistuoja U(x) israiska paprasciausiuju trupmenu suma (*) U(x)=(kΣi=1)(riΣj=1)(lij/(1 – λix)^j). Cia λi-1 $ C, 1<=i<=k – charakteristinio polinomo A(x) saknys, rr – ju kartotinumai, r1 + • • • + rk = r, o lij $ C.2 teorema. Jei U(x) turi (*) israiska tai un=(kΣi=1)* *( λ(n//i)(riΣj=1)lij(j + n – 1//n). n>=0. |> Pagal apibendrintaja Niutono binomo formule 1/(1 – λ ix)^j =(ooXn=0)(-j//n)(-1)^n λn//i x^n = (ooΣn=0)(n+j-1//n) λ n//I^n, | λ ix| < 1. Istate I (*) formule ir sulygine koeficientus prie vienodu x laipsniu, baigiame 2 teoremos irodyma <|

Isvada. Tarkime, kad seka {un}, n _ 0, apibrezta sarysiu un+2 +a1un+1 +a2un = 0 ir pradinemis salygomis u0 = u1 = 1. Jei A(x) = a2(x – x1)(x – x2), x1<>x2, λ i = x1-1, tai un = c1 λ n//1 + c2 λ n//2 o konstantos c1, c2 randamos is pradiniu salygu. Jei A(x) = a2(x – x1)2, λ = x1-1, tai un = c1 λ^n + c2n λ^n, o konstantos c1, c2 randamos is pradiniu salygu.

16. Sudetiniu funkciju Tayloro koeficientu rekurentieji sarysiai1 teorema. Funkcijos F(x) Tayloro koeficientai bn tenkina rekurentuji sarysibn+1 =1/(n + 1)(nΣj=0)a(n-j+1)bj , b0 := 1, n>=0.|> Diferencijuodami gauname F’(x) =(ooXn=1)nbnx^(n-1) = =F(x)(1Xl=0)a(l+1)x^l =(1Xn=0)(( nΣj=0)bja(n-j+1))x^n. Kadangi funkcijos, esancios kaireje sios lygybes puseje, koeficientas prie x^n lygus (n+1)bn+1, apskliaustoji suma yra jo israiska. <|2 teorema. Funkcijos Gm(x) := (A(x))^m :=((ooXk=0)akx^k)^m, m $ N, a0 <> 0 su apreztais realiais aj Tayloro koeficientai gn := gn(m) tenkina rekurentuji sarysi gn+1 = a0-1(nΣj=0)(m – (m + 1)j/(n + 1))a(n-j+1)gj , g0 = am//0 , n>=0.

17. Grandinines trupmenosReiskini α = q0 +(1/(q1 + (1/(q2+… (1/(qk-1+ 1/qk))))))) vadiname grandinine trupmena. Trumpesnis zymuo: α = [q0, q1, q2, . . . , qk]. Cia q0 $ Z, qj $ N, 1<= j<= k, o k>= 0 – sveikasis skaicius.1 teorema. Kiekviena racionaluji skaiciu galime isreiksti grandinine trupmena, be to, vieninteliu budu.2 teorema. Pazymekime P-1 = 1 ir Q-1 = 0. Artiniu skaitikliai ir vardikliai tenkina siuos rekurenciuosius sarysius: Pk = qkPk-1 + Pk-2 , Qk = qkQk-1 + Qk-2 , k>=1.Isvada. Seka Qk, k >=0, grieztai monotoniskai dideja.3 teorema. Kai k>=1, tai det(Pk , Pk-1//Qk, Qk-1)= PkQk-1 – Pk-1Qk = (-1)^(k+1). Be to, δk – δk-1 =(-1)^(k+1)/(QkQk-1) |> Skaiciuodami determinanta pritaikome 2 teorema. Jis lygus priesingam determinantui, kuriame elementu indeksai vienetu yra mazesni. Po k zingsniu gauname jo reiksme: (-1)^k(P0Q-1 – P-1Q0) = (-1)^k(q0•0-1•1)=(-1)^(k+1). Isvedant antraja formule, pakanka subendravardiklinti ir pritaikyti ka tik gauta lygybe. <|Isvada. Teisingos nelygybes δ0 < δ1 < • • • V‘ tokia, kad su kiekviena briauna xy e E yra patenkinta salyga: xy e E  (tuscia aibe)(x)(tuscia aibe)(y) e E‘. Multigrafu atveju pastaroji salyga turi buti patenkinta kiekvienai is kartotiniu briaunu, o digrafams – atvaizdis (tuscia aibe) turi islaikyti ir briaunos krypti.Multigrafu atveju pastaroji salyga turi buti patenkinta kiekvienai is kartotiniu briaunu, o digrafams – atvaizdis (tuscia aibe) turi islaikyti ir briaunos krypti. Kai kada grafo (arba digrafo) virsuniu aibeje tenka ivesti numeracija. Tada grafai (digrafai) vadinami numeruotaisiais, o du tokie grafai G = (V1,E1) ir G = (V2,E2),, cia Vi = {vi1, . . . , vin}, vadinami izomorfiskais, jeigu grafu anksciau apibreztas izomorfizmas islaiko dar ir numeracija, t.y., Φ(v1j) = v2j . Pavyzdziai: keitiniu grafinis vaizdavimas, visu baigtines aibes atvaizdziu i save grafinis vaizdavimas. Apskritai izomorfiskus grafus galima sutapatinti, laikyti juos lygiais. Nagrinesime tik baigtinius grafus, t.y. tik poras (V,E) su baigtinemis aibemis V ir E. Siu aibiu galias zymekime |V | = n≥1 ir |E| = m≥0. Jei nebus pasakyta priesingai,grafas netures taip vadinamu kilpu, t.y. briaunu xx. Kadangi grafas neturi kartotiniu briaunu, tai m≤C2/n. Cia Ck/n – binominis koeficientas. Daznai tokie grafai vadinami paprastaisiais. Skaicius n vadinams grafo G eile, o m – grafo G didumu. Kai m = 0, grafas G vadinamas tusciuoju (tradiciskai zymimas E^n), o kai m = C2/n, – pilnuoju. Pilname grafe visos virsunes yra tarpusavyje sujungtos, jis zymimas Kn. 1 teorema. Galima sudaryti 2^(n(n−1)/2) skirtingu n eiles numeruotuju grafu. Irodymas. Skaiciuojamu grafu didumai gali buti 0, 1, . . . , k, . . . ,N := (n//2). Breziant k didumo grafa, jo briaunu aibe galetume parinkti is visos galimos briaunu aibes (N//k) budu.Taigi, skirtingu n eiles grafu gauname 1 + (N//1) + • • • + (N//k) + • • • + (N//N) = (1 + 1)^N = 2^N.Virsunes x laipsniu (valentingumu) δ(x) laikomas incidenciu jai briaunu skaicius. Kai δ(x) = 0, x – izoliuotoji virsune. Skaiciai δ(G) = min{ δ(x) : x e G}, Δ(G) = max{ δ(x) : x e G} atitinkamai vadinami minimaliuoju bei maksimaliuoju grafo laipsniais. Kai δ(G) = Δ(G) =: k, grafas G vadinamas k reguliariuoju (k-valenciu). Pvz., kubinis bei Petersen’o grafai yra trivalenciai. Grafas G‘ = (V‘,E‘) vadinamas G = (V,E) pografiu, jeigu V‘ C V ir E‘ C E.Jeigu pografio G‘ briaunu aibeje E‘ yra visos E briaunos, jungiancios V‘ virsunes, tai G‘ vadinamas V‘ indukuotoju pografiu, ji zymesime G[V‘].

Grafu veiksmai.Tarkime, kad G = (V,E) – grafas, x e V‘ C V ir xy e E‘ C E. Tada G − V‘ := G[V V‘] ir G − E‘:= (V,E E‘).Taigi, grafas G−x := G−{x} gaunamas is G ismetant ne tik virsune x, bet ir jai incidencias briaunas, o G − xy := G − {xy} – ismetant tik briauna xy. Kai kada tikslinga, atemus is grafo briauna xy, sutapatinti virsunes x ir y. Si operacija vadinama grafo sutraukimu. Grafas (VUV‘,EUE‘) vadinamas G = (V,E) ir G‘ = (V‘,E‘) sajunga, zymima GUG. Dazniausiai grafu sajungoje virsuniu aibems dar iskeliamas reikalavimas netureti bendru tasku. Grafu G ir G‘ suma G+G‘ apibreziama kaip ju sajunga, papildomai isvedant visas briaunas, jungiancias V ir V‘ virsunes. Grafa vaizdziai charakterizuoja ivairios ”klajojimo” juo galimybes. Virsuniu ir briaunu seka x0, e1, x1, . . . , ek, xk su ej = xj−1xj , xj e V , j = 0, . . . , k vadiname keliu (x0 − xk keliu), o k – jo ilgiu. Kai kelyje visos briaunos yra skirtingos, ji vadiname trasa. Uzdara trasa (kai x0 = xk ir k≥2) vadinsime grandine. Jeigu kelyje (arba trasoje) visos vidines virsunes x1, . . . , xk−1 yra skirtingos, ji vadiname taku, ir uzdara taka, kai k≥2, – ciklu (grandimi). Takus bei ciklus zymesime pereinamu virsuniu seka, pvz., P = x1x2x3…xk. Akivaizdzia paskutine briauna xkx1 cikle galime ir nenurodyti. Jei grafe egzistuoja grandine, sudaryta is visu jo briaunu, tai jis vadinamas Euler’io vardu, o jei jame yra ciklas, apimantis visas jo virsunes, tai jis yra Hamilton’o grafas. Sios savokos nera ekvivalencios.Grafas G yra jungusis, jei bet kuria pora virsuniu is E jungia takas. Jei n≥2, sis grafas neturi izoliuotu virsuniu.2 teorema. Grafas yra jungiu pografiu sajunga.Irodymas. Dvi virsunes vadinkime ekvivalenciomis, jeigu grafe yra jas jungiantis takas. Tai ekvivalentumo sarysis virsuniu aibeje V. Ekvivalenciu virsuniu klases V1, . . . , Vs nesikerta, grafe nera briaunu, jungianciu skirtingu klasiu virsunes. Indukuotieji pografiai G[V1], . . . ,G[Vs] ir sudaro ieskomos sajungos pografius.Pografius vadinsime grafo jungumo komponentemis. Virsune, kurios atemimas is grafo keicia komponenciu skaiciu, vadinama iskarpos virsune, o briauna, – tiltu. Atstumu d(x, y) tarp virsuniu x ir y vadinsime trumpiausio tako ilgi, jei toks takas egzistuoja. Priesingu atveju, atstuma laikysime begaliniu.Grafas G = (V,E) vadinamas dvidaliu (bichromachiuoju, dvispalviu), jei V = V‘UV“,V‘∩V“0 =(tuscia aibe), o bet kokia briauna is E jungia virsune is V‘ su virsune is V“. Dvidalis grafas neturi nelyginio ilgio grandiniu.

2. Miskas ir medziai Grafas, neturintis ciklu(beciklis), vadinamas misku, o jungusis miskas – medziu.1 teorema. Grafas yra miskas tada ir tik tada, kada bet kokia virsuniu pora jungia ne daugiau kaip vienas takas.Irodymas. Jei grafas nera miskas, jame egzistuoja ciklas x0x1…xlx0. Todel turime dutakus x0x1…xl ir x0xl. Atvirksciai, tarkime, kad P = x0…xl ir P‘ = x0yl…ys = xl – du takai, jungiantys x0su xl. Tarkime, kad i+1 – maˇziausias indeksas, su kuriuo xi+1 ≠ yi+1, o j≥i maziausias indeksas su kuriuo yj+1 jau priklauso P, t.y. yj+1 = xk. Tada xi…xkyj …yi+1 yra ciklas. Todel grafas nera miskas.2 teorema. Sie tvirtinimai yra ekvivalentus:a) G yra medis; b) G yra minimalus jungus grafas, t.y. bet kurios briaunos atemimas is grafo padidintu komponenciu skaiciu; c) G yra maksimalus beciklis grafas, t.y. sujungiant bet kokias neincidencias virsunes butu sukuriamas ciklas.Irodymas. Pazymekime V,E grafo G virsuniu ir briaunu aibes, xy e E – bet kokia jo briauna, o u, v – bet kokias dvi neincidencias virsunes. Jei G – medis ir grafas G − xy butu jungus, tai G turetu du takus P = xx1…xky ir P = xy, vadinasi, todel turetu cikla P = xx1…xkyx. Tad, is a) isplaukia b). Briauna, kurios atemimas didina grafo komponenciu skaiciu vadinama tiltu. Jei G – medis, tai jame egzistuoja takas nuo u iki v. Isvestas naujasis takas uv su senuoju sudarytu cikla, ir grafas G + uv jau turetu cikla. Tad, is a) isplaukia c)Tarkime, G – minimalus jungus grafas. Jei G nebutu medis, o turetu cikla xx1…yx,

tai ismetus briauna xy, jo jungumas nepakistu. Priestara irodo, jog is b) isplaukia a).Isvada. Jungiame grafe egzistuoja medis, kurio virsuniu aibe sutampa su visa grafo virsuniu aibe.Isvadoje gautasis medis vadinams minimaliu jungianciuoju medziu (karkasu).Karkasinio medzio isvedimo budai1 budas. Jungiame grafe G = (V,E) fiksuokime virsune x e V ir virsuniu aibe suskaidykime i nepersikertancias aibes Vi = {y e V : d(x, y) = i}, i = 0, 1, . . . , s < oo. Jei yi 2 Vi , tai egzistuoja x−yi takas xz1…zi−1yi. Pastebekime, kad Vj ≠ (tuscia aibe), j = 0, 1, …, i, kai i > 0. Taigi, bet kuriam yi e Vi rasime y‘i−1 e Vi−1. Is, gal but, keliu galimybiu pasirinkime viena. Kai y perbegs V , priskirtieji y‘ (artimesni pradiniam taskui) ir y sudarys junguji grafa T = (V,E‘), E‘ = {yy‘ : y e V, y ≠ x}. Kadangi i y patenkama tik is vieno tasko, jis neturi ciklu. Taigi, T – karkasinis medis.2 (indukcinis) budas. Imkime x e V . Tada T1 := ({x}, (tuscia aibe)) – medis. Tarkime, kad jausukonstravome medziu seka T1C T2 C • • • C Tk C G ir medzio Ti eile yra i. Jei k < n = |V |, tai egzistuoja pora (y, z) tokia, kad z e V (Tk), y e V V (Tk), cia V (Tk) – Tk virsuniu aibe, ir zy e E. Priesingas atvejis priestarautu grafo G jungumui. Apibrezkime Tk+1 = (V (Tk) U {y},E(Tk) U {zy}). Baigtiniame grafe sis procesas baigtinis. Jis baigiasi, kai k = n. Medi galime charakterizuoti ir pagal jo skaitinius parametrus: eile ir didumu.

3. Viena optimizavimo problemaUzdavinys Reikia suprojektuoti pigiausia vandentiekio tinkla, jungianti visas miestelio sodybas, kada zinomos visu trasu tarp namu kainos. Jeigu gamtines kliutys yra neiveikiamos, galima laikyti, kad trasos per sia kliuti kaina yra begaline. Formalizuojant galima isivaizduoti, kad turime pilnaji n grafa G = (V,E) ir apibrezta funkcija f : E -> R^+.Reikia isvesti karkasini medi (vesti kelias linijas i ta pacia sodyba visada bus brangiau) T = (V,E‘) toki, kad bendra kaina F(T) = (∑ xy2E0 ) (xy) butu maziausia. Si medi vadinkime ekonomisku. Uzdavinio sprendimo algoritmai1 algoritmas:a) imame briauna e = xy e E su maziausia kaina, f(e) = min(xy e E)f(xy); b) is likusiu briaunu isrenkame pigiausia; c) procesa kartojame su salyga, kad isrenkamos briaunos nesudarytu ciklo. Procesas baigtinis, o gautasis grafas, kaip maksimalus beciklis grafas, pagal 2.2 teoremos c) punkta bus karkasinis medis. Gautojo medzio ekonomiskuma isnagrinesime veliau.2 algoritmas:a) imame briauna e = xy e E su didziausia kaina, f(e) = max(xy2E)f(xy) ir ja atimame is grafo G; b) ta pati kartojame su grafu G − e; c) procesa baigiame, kai kitas briaunos atemimas padidintu grafo jungumo klasiu skaiciu.Gautasis grafas, kaip minimalus jungus grafas, pagal 2.2 teoremos b) punkta bus karkasinis medis.3 algoritmas:a) imame bet kokia virsune x1 e V ; b) imame viena is pigiausiu incidenciu x1 briauna‘ x1x2 e E, x2 e V {x1}; c) rade x1, . . . , xk ir briaunas xixj , i < j≤k ieskome x = xk+1 e V {x1, . . . , xk}, tokios, kad kaina f(xk+1xi) su kazkokiu i ≤ k butu minimali. Procesas baigiasi, kai k = n, o briaunu skaicius lygus n − 1. Taip gavome karkasini medi.1 teorema. Virsuje aprasytieji algoritmai duoda ekonomiskus medzius. Jei kainosfunkcija yra injektyvi, tai ekonomiskasis medis yra vienintelis.Irodymas. Tarkime, jog T – ekonomiskas medis, turintis maksimalu skaiciu bendru briaunu su T1, medziu, gautu naudojant 1 algoritma. Jei E(T) ≠ E(T1), imkime pirma briauna xy is T1, bet nepatekusia i T. Medyje T irgi yra x − y takas, sakykim P, kurio bent viena briauna, tegu uv, nepatenka i T1. Renkant xy, si briauna uv buvo viena is kandidaciu, todel f(xy)≤f(uv). Sudarykime nauja karkasini medi T‘ = T − uv + xy. Jo kaina F(T‘) = F(T) − f(uv) + f(xy) ≤ F(T), todel ir naujasis medis yra ekonomiskas. Bet jis turi dar daugiau bendru briaunu su T1, nei T. Priestara irodo, kad T = T1. 2 bei 3 algoritmais gautu medziu ekonomiskumas irodomas panasiais samprotavimais. Nagrinekime vienati, kai visos briaunu kainos skirtingos. Taikome matematine indukcija grafo eiles atzvilgiu. Kai n = 2, 3, teiginys trivialus. Padare prielaida, jog teorema teisinga visiems n ≥ 4 eiles grafams, nagrinedami (n + 1) eiles pilnaji grafa, skelkime virsuniu aibe i dvi dalis V = V1 ∩ V2, su n1, n2 ≥ 2 virsuniu, n1 + n2 = n + 1 ir nagrinekime indukuotosius pografius. Juose egzistuoja vieninteliai ekonomiski karkasiniai medziai T1, T2. Raskime min (x2V1/y2V2) f(xy).Tarkime, si minimali kaina igyjama briaunoje xy, jungiancioje abu pografius. Isitikinkime,kad medis T4 := T1 U T2 + xy yra ekonomiskas. Tarkime, T – ekonomiskas medis. Jei T4 ≠T, tai vienintele briauna is T4, nepatekusi i T, gali buti tik xy. Medyje T turi buti kita briauna uv, jungianti T1 su T2. Bet tada f(xy) < f(uv) ir medzio T − uv + xy kaina butu grieztai mazesne, nei T. Priestara irodo ekonomisko medzio vienati.

Pastaba. Vienaties irodymas duoda dar viena karkasinio medzio konstravimo buda: kai briaunu kainos skirtingos, galima grafa skaidyti i mazesnius ir juose ieskoti karkasiniu medziu, o veliau juos sujungti.

4. Grafo parametru rysiai1 (Euler’io) lema. Grafo virsuniu laipsniu suma yra lyginis skaicius.Irodymas. Pakanka pastebeti, jog kiekviena briauna, turedama du galus, inesa 2 vienetus i suma (1) (∑x2V)δ(G) = 2|E| 1 isvada. Nelyginio laipsnio virsuniu kiekis grafe yra lyginis skaicius.2 isvada. Tarkime d(G) = 1/(|V |) (∑x2V)δ(x) − − vidutinis grafo laipsnis, o ε = |E|/|V | – vidutinis briaunu skaicius, tenkantis vienai virsunei. Tada ε (G) = d(G)/2.Irodymas. (1) suma lygi |V |d(G). Lema islieka teisinga ir bendresniems grafams.2 lema. Tarkime, kad G‘ = (V‘,E‘) ir G“ = (V“,E‘), V‘ V“ = (tuscia aibe), – du pilnieji grafai su |V‘| = n1, |V“| = n2, n1 + n2 = n. Grafo G‘U G“ didumas didziausias, kai n1 = n − 1, o n2 = 1.Irodymas. Dabar grafe G‘UG“ turime (n1(n1 − 1))/2 + (n2(n2 − 1))/2 briaunu. Apskaiciuokime, kaip keiciasi bendras briaunu skaicius, jei viena virsune didesni grafa padidintume, o kita, mazesniji, – sumazintume. Tegu n1≥n2. Gautasis briaunu skaicius butu lygus (n1(n1 + 1))/2 + ((n2 − 1)(n2 − 2))/2, o skirtumas – n1 + 1 − n2 ≥ 1.Taigi, kartojant panasia procedura pasieksime maksimalu bendra briaunu skaiciu, kai n1 =n − 1, n2 = 1.1 teorema. Jei n – grafo eile, m – didumas, o k – jo komponenciu kiekis, tai (1.1) n − k ≤ m ≤1/2 (n − k)(n − k + 1).Irodymas. Pirmaja nelygybe irodysime, taikydami matematine indukcija m ≥ 0 atzvilgiu. Kai m = 0, turime nulini grafa su n jungumo klasiu. Tad, nelygybe triviali. Tegu m1 < m2 < • • • – n eiles grafu G, turinciu k jungumo klasiu, didumai su savybe: ismetus dar viena briauna is G, padidetu jo jungiu komponenciu skaicius. Kai mj−1 ≤ m < mj , kairioji is (1.1) nelygybiu isplauks is nelygybes, kai m = mj−1. Todel pakanka nelygybe irodyti tik siai sekai. Tarkime, jog nelygybe irodyta grafui su mj−1 briauna, ir nagrinekime atveji |E| = mj . Kadangi dabar kiekviena briauna yra tiltas, ismetus kazkuria is ju gauname grafa, kuriam galioja indukcijos prielaida. Tegu tai – grafas G‘ = (V‘,E‘), |V‘| = n, |E‘| = mj − 1.Jis turi k + 1 klase, todel n − (k + 1) ≤ mj − 1. Is cia isplaukia pirmoji is (1.1) nelygybiu. Vertindami m is virsaus, nagrinekime pati ”blogiausia” atveji, kai kiekviena is jungumo klasiu yra pilnieji pografiai. Pritaike lema kiekvienai siu klasiu porai, gauname, kad bendras briaunu kiekis m bus maksimalus, kai viena is ju yra labai didele, o likusios – tusti grafai. Todel tada n-os eiles grafe su k jungumo klasiu, pografiu eiles yra n − k + 1, , 1, . . . , 1. Taigi, maksimalus briaunu skaicius lygus((n − k + 1)(n − k))/2 Isvada. Jei n eiles grafas turi daugiau nei 1/2 (n−1)(n−2) briaunu, tai jis yra jungusis.2 teorema. n-os eiles jungusis grafas yra medis tada ir tik tada, kada jo didumas lygus n − 1.Irodymas. Pagal kairiaja (1.1) nelygybe jungiajame n eiles grafe yra ne maziau, negu n − 1 briauna. Jeigu ju butu daugiau, grafas turetu tureti cikla . Taigi, teoremos salyga yra butina. Jos pakankamumas akivaizdus.1 isvada. n-os eiles grafo jungianciojo medzio didumas lygus n − 1.2 isvada. n-os eiles misko is k medziu didumas lygus n − k.

5. Grafo planarumasVaizduojant grafus plokstumoje ir breziant briaunas apsiribojama Zordano kreivemis. Grafus, kuriuos galima pavaizduoti plokstumoje, taip, kad skirtingos briaunos neliestu viena kitos ne virsuniu taskuose, vadiname planariaisiais. Pati plokstumoje isvesta grafa vadiname ploksciuoju grafu.Plokstumos sritys, apribotos plokscio grafo briaunomis ir virsunemis, vadinamos grafo veidais. Visi plokstieji grafai turi viena begalini veida. Ploksciasis grafas kartu su savo veidais vadinamas zemelapiu. Tada veidus geriau vadinti valstybemis.1 teorema (L.Euler, 1752). Jei G – jungus zemelapis, n – jo eile, m – didumas ir f – valstybiu skaicius, tai n-m+f=2. |> Indukcija f atzvilgiu. Jei f = 1, tai grafas neturi ciklu. Vadinasi, jis yra medis. Todel musu teiginys isplaukia is 3.2 teoremos isvados. Tariame, kad teorema irodyta del zemelapiu su mazesniu uz f > 1 skaiciumi valstybiu. Pastebekime, jog grafas turi ciklu. Imkime bet kuria ciklo briauna ir atimkime is grafo. Dvi valstybes, kurios buvo atskirtos ciklo, susijungia i viena. Todel naujasis zemelapis tures viena valstybe maziau. Jam pritaikome indukcine prielaida. <|2 teorema. Planarusis n>=3 eiles jungus grafas turi m<=3n – 6 briaunu. Jei toks grafas turi maziausio ilgio 3<=g Taikome matematine indukcija grafo eiles n atzvilgiu. Maziems n teiginys patikrinams betarpiskai. Tarkime, kad teorema irodyta visiems n – 1 eiles grafams, ir ju virsuniu spalvinimui panaudota ne daugiau Δ(G) + 1 spalvu. Is n eiles grafo atimkime viena virsune v ir pasinaudokime indukcijos prielaida. Nudaze grafa G-v, griztame prie G. Virsunes, gretimos v, yra nudazytos ne daugiau kaip Δ(G) + 1 spalvu. Ju yra ne daugiau kaip Δ(G). Vadinasi, viena spalva yra nepanaudota. Ja nudaze v, baigiame teoremos irodyma.<|

Lema. Kiekvienas planarus grafas turi ne didesnio kaip penktojo laipsnio virsune. |> Galime nagrineti tik jungius planarius n>=3 eiles grafus. Jei δ(v)>=6 kiekvienai virsunei v$V , tai is lygybes (Σv$V)δ(v)=2m, cia m – grafo didumas, isplaukia 6n<=2m. Tai priestarauja 5.2 teoremos isvadai, teigianciai, kad planariajam jungiam grafui m<=3n-6, kai n>=3. <|2 teorema. Kiekvienas planarusis grafas yra penkiaspalvis. |> irodyme remsimes indukcijos principu. Kai n<=5, teiginys trivialus. Tarkime, kad ji jau irodem kievienam planariajam grafui, kurio eile mazesne uz n. Pagal lema galime isskirti virsune v su δ(v)<=5. Jei δ(v) < 5, Grafui G-v pritaikome indukcijos prielaida ir nudazome jo virsunes, panaudodami 5 spalvas. Virsunei v gretimos virsunes nuspalvinamos maziau nei 5 spalvomis. Sutaupytaja spalva nudazome v ir taip baigiame uzduoti. Tegu δ(v)=5. Nagrinekime v gretimasias virsunes v1, v2, v3, v4, v5. Bent dvi is ju yra negretimos tarpusavyje. Tegu v1 ir v2 negretimos virsunes. Nagrinekime sutrauktaji grafa G’=G{vv1, v2}. Pagal indukcijos prilaida jam nuspalvinti pakako i spalvu. Taip ir nudazykime G’. Dabar isplete G’ iki G, matome, kad gretimosios v virsunes sutaupo viena spalva, kuria galime nuspalvinti pacia v.Isvada. Kiekvienas zemelapis yra penkiaspalvis.3 teorema. Kiekvienas zemelapis yra keturspalvis.

7. Medziu skaiciusGrafa su sunumeruota virsuniu aibe vadinsime numeruotoju grafu.1 ( Cayley’io) teorema. Is viso galime sudaryti n^(n-2) neizomorfisku numeruotu n eiles medziu. |> (Prufer’io) Tarkime G – nagrinejamu medziu aibe. Kadangi seku aibes {(a1,…,an-2):1<=ai<=n, 1<=i<=n – 2}=:A galia yra n^(n-2), pakaks rasti bijektyvu atvaizdi A –> G. Kai n<=2, teiginys akivaizdus. Tegu toliau n > 2. Medziui G=(V,E), kurios virsuniu aibe sunumeruota, V={x1,…,xn}, vienareiksmiskai priskirsime seka α=(a1,…,an-2)$A, vadinama medzio Prufer’io kodu. Pradekime nuo medzio galines virsunes, kurios laipsnis lygus 1. Tokios virsunes egzistuoja, nes kiekviena briauna turi dvi virsunes ir todel (n Σi=1) δ (xi) = 2(n – 1). Is keliu tokiu virsuniu isrinkime ta, kurios indeksas yra maziausias. Tegu tai virsune xb1 , o a1 – indeksas virsunes, gretimos pirmajai. Grafas G-xb1 yra n-1 eiles medis, todel procesa galima kartoti, kol virsuniu, likusiu grafe, skaicius yra didesnis uz 2. Kai sis skaicius lygus 2, mes jau esame sudare vienintele seka (a1,…,an-2). <|Pora (G,G’) pavadinkime junginiu.Isvada. Yra n^(n-1) sakniniu n eiles medziu.Binareisiais medziais vadiname medzius, kurie turi viena 2-ojo laipsnio virsune, vadinama saknimi, o kitu virsuniu laipsniai yra 3 (jos vadinamos vidinemis virsunemis) arba 1 (sios virsunes vadinamos lapais). Binarusis medis turi tureti n! lapu.2 teorema. Teisingas rekurentusis sarysis CN =(N-1 Σk=1)CkCN-k, C1 = 1. Be to, CN =1/N((2N-2)//(N-1)).

8. Grafu teorijos ir algebros sarysiaiKvadratine matrica A=((aij )), 1<=i, j<=n, vadiname multigrafo gretimumo matrica.Matrica BG=B=(bij), 1<=i<=n, 1<=j<=m, vadiname multigrafo (grafo) incidentumo matrica, jei bij =1, jei i virsune yra incidenti j briaunai, kuri nera kilpa, bij=2, jei i virsune yra incidenti j briaunai, kuri yra kilpa, bij=0, jei i virsune nera incidenti j briaunai.1 teorema. Tarkime G – numeruotas multidigrafas be kilpu, A ir B – jo gretimumo ir incidentumo matricos atitinkamai. Tada BB’=D-A. Cia ’ zymi matricos transponavima, o D –diagonali matrica, kurios istrizaineje yra is eiles surasyti virsuniu laipsniai. |> Jei cij – matricos BB’ bendrasis narys, tai cij=(mΣl=1)bilbjl. Todel, kai i <> j, sandauga bilbjl lygi 0 arba -1. Pastaroji lygybe yra teisinga tik tuo atveju, kai xixj = el. Sudedant pagal l, -1 dauginsis is tokio kaiciaus, kiek yra briaunu, jungianciu xi ir xj. Kai i = j, cii yra matricos istrizaines narys. Matrica A turi nuline istrizaine. Cij suma lygi briaunu, isvestu is xi skaiciui. <|Standartine baze bus funkciju rinkinys f1,…,fn, kai funkcija fj apibreziama lygybemis fj(xi)=δij. Cia δij – Kronekerio simbolis. Kai L perbegs visus grafo ciklus, gausime aibe funkciju {gL}, ju tiesinis apvalkas Z(G) erdveje F1(G) vadinamas ciklu poerdviu. Jo dimensija dimZ(G) vadinama grafo G ciklomaciuoju skaiciumi.2 teorema. Briaunu funkciju erdve – tiesiogine tarpysavyje ortogonaliu poerdviu Z(G) ir U(G) suma. Jei grafas G turi n virsuniu, m briaunu ir k jungumo klasiu, tai dimZ(G)=m-n+k, dimU(G)=n-k.

Kirchhoff’o potencialu desnis. Jei C fundamentaliuju ciklo vektoriu sudaryta matrica, o ¯p – potencialu skirtumu vektorius stulpelis, tai C¯p = 0.