Diskrečioji matematika - pasiruošimas egzaminui

1. Paprastieji grafai. Paprastuoju grafu L=(X,U) vadiname sutvarkytą aibių porą. Baigtinės netuščios aibės X, kurios elementus vadiname grafo L viršūnėmis ir bet kurios aibės , kurioa elementus vadiname to grafo briaunomis. 2. Grafo papildinys,dalis,pografis,sugrafas. Grafas =(X,U) yra papildantysis grafą L= (X,U),jei turi tą pačią viršūnių aibę X, o jo briaunų aibė =\U sudaryta iš visų tų nesutvarkytų skirtingų viršūnių porų,kurios nėra pradinio grafo L briaunomis. Aišku,kad papildinio papildinys yra pats grafas L. Grafas L’ sudarytas is L’=(X’,U’) vadinamas grafo L=(X,U) dalimi,jei Grafo L=(X,U) dalis L’={X’,U’}vadinama grafo L pografiu, jei Grafo L dalis L’=(X’,U’) vadinama grafo L sugrafu, jei X= X’. 3. Grafų izomorfizmas. Grafai L ir L’ vadinami izomorfiškais,jei tarp jų viršūnių aibių X ir X’ galima nustatyti abipus vienareikšmę atitiktį, išlaikančią viršūnių gretutinumo sąryšį,t.y. tokią atitiktį,kad bet kuriems x,y X ir joms atitinkamoms viršūnėms x’,y’X’(xx’ ; yy’) yra teisinga . Atitiktį vadiname grafų izomorfizmu. 4. Grafo viršūnės laipsnis,viršūnių laipsnių vektorius. Grafo L=(X,U) viršūnės x laipsniu vadinamas jai gretimų viršūnių skaičius. Žymėsime s(L;x). Tarkime,kad L=(X,U), n viršūnių turintis grafas ,o jo viršūnių laipsniai išdėstyti nemažėjimo tvarka. Sutvarkyta sistema() vadinsime grafo L laipsniu vektoriumi ir žymėsime s(L). 5. Vienalytis grafas, dažniau pasitaikantys grafai. Grafas vadinamas vienalyčiu grafu,jei visų jo viršūnių laipsnis yra tas pats. Grafas nusakomas izomorfizmo tikslumu savo laipsniu vektoriumi vadinamas unigrafu. Kai kuriuos dažniau pasitaikančius grafus žymėsime sutartinai (-n viršūnių briaunų neturintis grafas,-pilnas n viršūnių turintis grafas,-paprastas n viršūnių turintis ciklas,-l grandinė) 6. Veiksmai su grafais. Tegul grafai tokie,kad . Tada jų suma Tegul grafai,be to . Grafų sandauga 7. Grafo invariantai. Atvaizdį f (tegul f atvaizdis kiekvienam grafui L,priskiriantis elementą f(L)iš aibės M(M-bet kurios prigimties aibė)) vadinsime invariantu,jei izomorfiškiems grafams jo reikšmės sutampa L ir L’: f(L)=f(L’) 8. Grafo tankis,retumas,chromatinis skaičius. Grafo L tankiu φ(L) vadiname didžiausio pilnojo pografio viršūnių skaičių. Grafo L retumu ε(L) vadiname didžiausio bebriaunio L pografio viršūnių skaičių. Mažiausią γ,kuriam grafą L galima taisiklingai nuspalvinti γ spalvomis,vadiname grafo L chromatiniu skaičiumi. 9. Jungus grafas,grafo Chadvigerio skaičius. Grafas L=(X,U) vadinamas jungiu,jei jų viršūnių aibę negalima išskaidyti poromis nesikertančiomis aibėmis(netuščiomis),kad jokios dvi viršūnės iš skirtingų poaibių nebūtų gretimos. Grafo L Chadvigerio skaičiumi η(L) vadiname didžiausio pilnojo grafo viršūnių skaičių,į kurį galima sutraukti L. 10. Grafo invariantai F,E,G,H pirmų i viršūnių,turinčių pografių skaičius). Aišku, kad -bebriaunių i viršūnių turinčių pografių skaičius, yra i nuspalvinimų skaičius, . -skirtingų grafo L sutraukinų į pilnąjį grafą skaičius, . 11. Grafo gretutinumo matrica,dvejetainis kodas. Sudarome kvadratinę matricą A(L) = turinčią n eilučių ir n stulpelių,apibrėžiama sekančiai: {1,jei i-toji viršūnės gretimos, {0,jei i-toji ir j-toji viršūnės negretimos. Aišku, kad visi 0 ir kad matrica A(L) yra simetriška,t.y. ,ši matrica vadinama grafo L gretutinumo matrica su duotąja viršūnių numeracija. Skaičius ,kurio užraše dvejetainėje sistemoje vienetų skaičius ,dvejetų skaičius ,ketvertų skaičius ir tt.vadinamas gretutinumo matricos A(L) dvejetainiu kodu. Mažiausiai iš šių n! viršūnių numeracijoms atitinkančių grafo L kodų vadiname mini kodu ,o didžiausią maksi kodu . 12. Grafo nusakymas viršūnių aibėmis. Grafo su viršūnėmis 1,2,...n nusakymo būdas glūdi tame,kad kiekvienai iš jų natūralia tvarka rašoma aibė, ir jos esančių viršūnių su kuriomis ji gretima,aibė. 13. F(L) nustatymas. F(L)=F(L\x)+xF(O(L,x)), F reikšmė nuo grafo L išreiškiama tos pačios funkcijos reikšmėmis nuo grafų L\X ir O(L,x). Pirmas iš kurių turi lygiai viena viršūne mažiau nei grafas L. O antrasis – mažiausiai viena viršūne mažiau nei grafas L. Naudojantis šiuo rekurentiniu sąryšiu ir pradine sąlyga F(ø)=1,galima apskaičiuoti daugianarį F(L). 14. E(L) nustatymas. Tam,kad rasti retumą ε(L) galima pasinaudoti analogišku rekurentiniu sąryšiu,kurį tenkintų daugianaris invariantas E(L): E(L)=E(L\x)+xE((L,x)), grafo L pografis generuotas skirtingomis nuo x ir negretimomis jai viršūnėmis. 15. G(L) nustatymas. Gautas rekurentinis sąryšis daugianariui G(L) kartu su pradinėmis sąlygomis i=1,2,…leidžia rasti daugianarį G(L) kiekvienam grafui L. 16. Maršrutas,grandinė,paprastoji grandinė grafe,ciklas. Seka turinti pavidalą vadinama ilgio l maršrutu iš viršūnės . Maršrutas kurio visos briaunos skirtingos vadinamas grandine. Grandinė vadinama paprastoji jei visos jos viršūnės yra skirtingos. Ciklinė grandinė,t.y. su pastebėsime,kad atvejai( l=1,l=2) tokiom grandinėm neįmanomi,vadinama ciklu. 17. Maršrutai grafe,lema apie juos,jungumas. Lema: kiekvienas maršrutas ,atskiru atveju kiekviena grandinė grafe,turi bent vieną paprastąją grandinę,jungiančią tą pačią viršūnių porą. Kiekvienas ciklinis nelyginio ilgio maršrutas turi nelyginio ilgio paprastąjį ciklą,einantį per bet kurią iš anksto nurodytą pradinę briauną. Sakoma,kad grafo L viršūnės x ir y atskirtos,jei grafe L nėra grandinės,kuri jas jungtų ir viršūnės vadinamos jungiomis,jei bent viena tokia grandinė egzistuoja. 18. Kionig teorema apie chromatinį skaičių. Chromatinis skaičius tada ir tik tada,kai grafas L neturi nelyginio ilgio ciklų. 19. Šarnyrai,sąsmauka. Grafo L viršūnė x vadinama šarnyru, jei grafas L\x turi daugiau komponenčių nei grafas L,t.y. k(L\x)>k(L). Grafo L briauna yra vadinama sąsmauka,jei L\u turi daugiau komponenčių nei L. 20. Blokai, teorema apie blokus. Jungus grafas be šarnyrų vadinamas bloku. Teor. Tegul L=(X,U) blokas, skirtingas nuo pilnojo grafo ir paprastojo,tada grafe L egzistuoja viršūnių pora a ir b,turintis savybes: 1) ,3) pografis L\{a,b} jungus. 21. Grafo blokai, teorema apie grafo blokus. Teor. Du grafo blokai gali turėti ne daugiau kaip vieną bendrą viršūnę. Ir tokia viršūnė būtinai yra duotojo grafo šarnyru. Du šarnyrai gali įeiti ne daugiau kaip į vieną bendrą bloką. 22. T blokai. Tegul t grafo L=(X,U) viršūnė,o ta jo komponentė,kuri turi t. Ir tegul : pografio \t komponentės. Grafo pografiai generuoti poaibiais: vadinami grafo L t-blokais. T- blokas nebūtinai yra blokas. 23. Brukso teorema. Tegul ir grafas L=(X,U) neturi komponenčių pavidalo ,o esant 2 taip pat neturi paprastų ciklų turinčių nelyginį ilgį. Tada chromatinis skaičius . 24. Medis. Jungus grafas be ciklų vadinamas medžiu. Medis yra paprastasis grafas. 25. Teoremos apie medžių savybes. Teor. Medis T=(X,U) turi šias savybes (1) k(T)=1 (2) λ(T)=0 (2’) kiekviena briauna grafe T yra sąsmauka (3) m(T)=n(T)-1 (4) bet kurioms dviems viršūnėms x,y X gali egzistuoti ne daugiau vienos grandinės iš x į y,ir tokia grandinė būtinai paprastoji. (5) kiekvienai briaunai sugrafas T\u nejungus. (6) bet kokių dviejų viršūnių x,y X sujungimas nauja briauna atveda į ciklo atsiradimą,atimančią tą briauną. (7) γ(T)=2, kai n(T) 2 (8) viršūnė xX yra šarnyru jei jos laipsnis s(T,x)>1 (9) jei n(T) 2,tai grafe T egzistuoja bent dvi kabančios viršūnės. Teor. Baigtinis neorientuotas grafas yra medis tada ir tik tada kada bet kurioms dviems jo viršūnėms x ir y egzistuoja grandinė iš x į y, be to vienintelė ir todėl ir paprasta. Kai x=y ta grandinė 0 ilgio. Teor. Medis T su n(T) 3 turi kaip kabančias kaip ir nekabančias viršūnes. Pografis gautas iš T šalinant kabančias viršūnes vėl yra medis. 26. Porų derinys, didintuvas. Paprastojo grafo L porų deriniu vadiname tokį jo briaunų aibės U poaibį WU,kuriame jokios dvi briaunos neturi incidentiškos viršūnės. Jei

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!