Išplėstinė paieška
 
 
 
Pradžia>Matematika>Diskrečioji matematika (8)
   
   
   
naudingas 0 / nenaudingas 0

Diskrečioji matematika (8)

  
 
 
1234
Aprašymas

Paprastieji grafai. Grafo papildinys,dalis,pografis,sugrafas. Grafų izomorfizmas. Grafo viršūnės laipsnis,viršūnių laipsnių vektorius. Vienalytis grafas, dažniau pasitaikantys grafai. Veiksmai su grafais. Grafo invariantai. Grafo tankis,retumas,chromatinis skaičius. Jungus grafas,grafo Chadvigerio skaičius. Grafo invariantai F,E,G,H. Grafo gretutinumo matrica,dvejetainis kodas. Grafo nusakymas viršūnių aibėmis. F(L) nustatymas. E(L) nustatymas. G(L) nustatymas. Maršrutas,grandinė,paprastoji grandinė grafe,ciklas. Maršrutai grafe,lema apie juos,jungumas. Kionig teorema apie chromatinį skaičių. Šarnyrai,sąsmauka. Blokai, teorema apie blokus. Grafo blokai, teorema apie grafo blokus. T blokai. Brukso teorema. Medis. Teoremos apie medžių savybes. Porų derinys, didintuvas. Lemos apie grafų plonų viršūnių skaičių. Mengerio teorema. Multigrafai, jų nusakymo būdai. Multigrafo izomorfizmas. Oilerio teorema. Teorema apie neatkertamas ir supinamas viršūnes. Bendro pavidalo baigtiniai grafai. Orientuotas grafas (dalinai orientuotas grafas). Algoritmai. Algoritmų blok-schemos. Tiuringo mašina. Tiuringo mašinos darbas. Tiuringo mašinos pavyzdžiai. Ekvivalentumas.

Ištrauka

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’(x x’ ; y y’) 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). ...

Rašto darbo duomenys
Tinklalapyje paskelbta2012-01-10
DalykasMatematikos špera
KategorijaMatematika
TipasŠperos
Apimtis6 puslapiai 
Literatūros šaltiniai0
Dydis119.26 KB
AutoriusTriumfas
Viso autoriaus darbų3 darbai
Metai2011 m
Klasė/kursas2
Mokytojas/DėstytojasPraninskas
Švietimo institucijaKlaipėdos Universitetas
FakultetasGamtos ir matematikos mokslų fakultetas
Failo pavadinimasMicrosoft Word Diskrecioji matematika (8) [speros.lt].doc
 

Panašūs darbai

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Šperos
  • 6 puslapiai 
  • Klaipėdos Universitetas / 2 Klasė/kursas
  • Praninskas
  • 2011 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą