Išplėstinė paieška
 
 
 
Pradžia>Informatika>Grafų izomorfizmas (2)
   
   
   
naudingas 0 / nenaudingas 0

Grafų izomorfizmas (2)

  
 
 
1234567891011
Aprašymas

Grafų izomorfizmas. Žymėtieji grafai. Žymėtųjų grafų skaičius. Izomorfinių grafų skaičius. Grafų izomorfizmo nustatymo uždavinys. Pavyzdžiai. Sąvokos.

Ištrauka

Apibrėžimas. Grafai G=(VG,BG) ir H(VH,BH) yra izomorfiniai, jei:
1) |VG|=|VH|
2) |BG|=|BH| 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 . Pavyzdžiui, 1.1. pav. Pavaizduoti trys izomorfiniai grafai, 1.2. pav. du neizomorfiniai grafai.

Aišku, kad grafų izomorfizmas yra ekvivalentiškumas, t.y. izomorfizmas visų grafų aibę išskaido į klases taip, kad vienos klasės grafai tarpusavyje yra izomorfiniai.
Todėl natūralu visus vienos klasės grafus sutapatinti, t.y. visus juos galima pavaizduoti vienu ir tuo pačiu piešiniu. Norėdami pabrėžti, kad nagrinėjami grafai skiriasi izomorfizmo tikslumu, sakome abstraktusis grafas. Šis grafas žymi visą izomorfinių grafų klasę.

Žymėtieji grafai. Daugelyje situacijų reikia skirti izomorfinius grafus. Tam tikslui kiekvienai grafo viršūnei priskiriama žymė, pavyzdžiui, aibės {1,2,3,...,n} skaičius. Toks grafas vadinamas žymėtuoju grafu. Du žymėtieji grafai, turintys tą patį viršūnių skaičių, yra lygūs, jei jų briaunų (lankų) aibės yra lygios ir skirtingi, jei jų briaunų (lankų) aibės yra nelygios. Pavyzdžiui, 1.3. pav. pavaizduoti trys žymėtieji grafai.

Iki šiol mes nagrinėjome žymėtuosius grafus. Todėl ir tolesniame nagrinėjime sakydami žodį grafas suprasime, kad tai žymėtasis grafas, o norėdami kalbėti apie izomorfinius grafus, tai atskirai pabrėšime. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2006-10-16
DalykasInformatikos referatas
KategorijaInformatika
TipasReferatai
Apimtis9 puslapiai 
Literatūros šaltiniai1
Dydis27.67 KB
AutoriusAurimas
Viso autoriaus darbų3 darbai
Metai2006 m
Klasė/kursas1
Mokytojas/DėstytojasDoc. V. Sirius
Švietimo institucijaŠiaulių Universitetas
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. Sirius
  • 2006 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą