Diskrečiosios matematikos teorija

 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. • n(L) = (x) grafo L viršūnių skaičių , o m(l) = (u) briaunų skaičių. • Grafas L paprastasis yra neorientuotas. Kadangi briaunos yra nesutvarkytos viršūnių poros • Paprastame grafe L nėra kilpų, kadangi pagal savo apibrėžimą yra sudarytos tik iš skirtingų elementų porų. • Paprastasis grafas L neturi kartotinių briaunų , laikomos vienu ir tuo pačiu aibės elementu , tada ir tik tada , kai x = z ir y= t arba x =t ir y = z . bet tada abi poros reiškia tą patį aibės U elementą. Tai yra vieną ir tą pačią grafo L briauną jungiančią jo viršūnes x ir y. Sugrafas gaunamas iš pradinio grafo šalinant tik kai kurias briaunas. Nešalinant viršūnių 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 kitaip tariant sudarant pografį L‘ iš grafo L šalinamos aibės x \ x‘ ir tik tos briaunos, kurios incidentiškos šalinamai viršūnei. 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 Grafai , kai ( n) ir (n yra paprasti ta prasme, kad jų negalima išreikšti kokių kitų grafų suma ar sandauga 7. Grafo invariantai. Normalu kelti klausima kokios grafu charakteristikos invariantishkos izomorfizmo atzvilgiu. Grafo L invarianto pavyzdžiai jau yra. Viršūnių skaičius n(L), briaunų skaičius m (L), laipsnių vektorius s(L)( Tegu f atvaizdis kiekvienam grafui L priskiriantis elementą f( L) iš aibės M. Čia M, bet kurios prigimties aibė. Nors ištikrųjų M elementais dažniausiai būna skaičiai, skaičių sistemos, vektoriai,matricos. atvaizdį f vadinsime invariantu, jei izomorfiškiems grafams jo reikšmės sutampa t.y bet kuriems L1 ir L‘, kad L seka f(L)= f(L‘) 8. Grafo tankis,retumas,chromatinis skaičius. Grafo L tankiu vadinamas didžiausio pilnojo pografio viršūnių skaidžiausio pilnojo pografio viršūnių skaičius. Invariantiškumas seka iš to,kad esant dviejų grafų izomorfizmui kiekvienam vieno grafo viršūnių poaibiui generuojančiam vieną pilną grafą atitinkamai kitame grafe poaibis su tuo pačiu viršūnių skaičiumi generuoja taip pat pilnąjį grafą. Grafo L retumu vadinamas didžiausio bebriaunio L pografio viršūnių skaičiusKitaip tariant grafo L retumu laikome didžiausią jo poromis negretimų viršūnių skaičių. Mažiausio , kuriam grafą L galima taisyklingai nuspalvinti spalvomis vadinsime 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. Aišku, kad η(L), tai didžiausias poromis nesikertančios klasių x1, x2,... skaičius į kurias galima išskaidyti viršūnių aibę x taip, kad kiekviena klasė generuotų jungų pografį. Ir bet kurioms dviems klasėms egzistuotų bent viena briauna, jungianti vienos klasės viršūnę su kitos klasės viršūne. Nejungiam grafui chadvigerio skaičius apibrėžiamas kaip didžiausias jo jungumo komponenčių chadvigerio skaičių. η (En)=1; η(Fn)=n; η(Cn)=3 (n≥3). 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 . Pagal kiekvieną iš jų ir viršūnių skaičių galima atkurti vieną iš gretutinumo matricų, o pagal ją ir patį grafą izomorfizmo tikslumu. 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-jai priklausanciai nuo grafo L kurios reikesmes nebe skaiciai o daugianariai nuo kintamojo x, rekursija vygdoma pagal grafa L. 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. L nera pilnas grafas ir x ir y kazhkokios dvi negretimos virsunes L ir xy grafas gautas is grafo prijungiant briauna xy, o L

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!