Grafų izomorfizmas

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).
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ą.
Pav.
Nesigilinsiu į Karaliaučiaus tiltų uždavinio sprendimą. Aš panagrinesiu Grafų izomorfizmą.
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.
1 pav. Izomorfiniai grafai
2 pav. 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 skaičius. Toks grafas vadinamas žymėtuoju grafu. 3 pav.
3 pav. Žymėtasis grafas
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, 4 pav. pavaizduoti keturi skirtingi žymėtieji grafai.
4...

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!