Išplėstinė paieška
 
 
 
Pradžia>Matematika>Grafų izomorfizmas
   
   
   
naudingas 0 / nenaudingas 0

Grafų izomorfizmas

  
 
 
1234567891011
Aprašymas

Įvadas. Grafas. Grafų izomorfizmas. Žymėtieji grafai. Žymėtųjų grafų skaičius. Izomorfinių grafų skaičius. Grafų izomorfizmo nustatymo uždavinys. Pavyzdžiai. Papildomi izomorfinių grafų pavyzdžiai. Neizomorfinių grafų pavyzdžiai. Sąvokų paaiškinimas.

Ištrauka

Inžinierius braižo elektros tinklo schemas, istorikas – geneologinius medžius, chemikas sudarinėja medžiagos struktūros formules, dispečeris – produkcijos išvežiojimo planus. Kas yra bendra jų veikloje? Visi jie braižo schemas, sudarytas iš taškų, kurie sujungti atkarpomis arba kreivėmis. Kitaip sakant – grafus.
GRAFAS - tai viršūnių (taškų) bei briaunų (linijų) rinkinys, kurį galima įsivaizduoti kaip figūrą. Briauna turi jungti dvi grafo viršūnes (išskirtinais atvejais – vieną – su savimi pačia).

Grafų teorijos pradininku laikomas L.Oileris (1707–1783), išsprendęs gerai žinomą uždavinį apie Karaliaučiaus tiltus:
Per Karaliaučiaus miestą teka Prėgliaus upė, kurioje yra dvi salos: A ir B . Šios salos su kairiuoju ir dešiniuoju upės krantais K ir D bei tarpusavyje sujungtos septyniais tiltais (žr. pav.). reikia nustatyti, ar galima rasti tokį maršrutą, kuriuo einant būtų galima pereiti visus tiltus tik po vieną kartą ir grįžti į tą pačią vietą.

Nesigilinsiu į Karaliaučiaus tiltų uždavinio sprendimą. Aš panagrinesiu Grafų izomorfizmą.

GRAFŲ IZOMORFIZMAS

Apibrėžimas. Grafai G=(VG,UG) ir H=(VH,UH) yra izomorfiniai , jei:
1) |VG|=|VH|,
2) |UG|=|UH| ir
3) yra toks aibės VG atvaizdis (bijekcija)  į aibę VH, kad, jei v1 ir v2 yra gretimos grafo G viršūnės, tai (v1) ir (v2) yra gretimos grafo H viršūnės.
Jei grafai yra izomorfiniai, tai rašome GH. Pavyzdžiui, 1pav. pavaizduoti du izomorfiniai grafai, 2 pav. du neizomorfiniai grafai. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2006-06-08
DalykasMatematikos referatas
KategorijaMatematika
TipasReferatai
Apimtis9 puslapiai 
Literatūros šaltiniai4
Dydis95.88 KB
AutoriusMarius
Viso autoriaus darbų1 darbas
Metai2006 m
Klasė/kursas1
Mokytojas/DėstytojasDoc. V. Sirijus
Švietimo institucijaŠiaulių Universitetas
FakultetasMatematikos ir informatikos fakultetas
Failo pavadinimasMicrosoft Word Grafu izomorfizmas [speros.lt].doc
 

Panašūs darbai

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Referatai
  • 9 puslapiai 
  • Šiaulių Universitetas / 1 Klasė/kursas
  • Doc. V. Sirijus
  • 2006 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą