Grafų izomorfizmo skaičiavimas

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.
Koks yra n viršūnių žymėtųjų ir izomorfinių grafų skaičius.
Žymėtųjų grafų skaičius. Didžiausias n viršūnių grafo briaunų skaičius yra lygus . Tada grafų, turinčių k briaunų, skaičius yra lygus . Vadinasi, visų n viršūnių žymėtųjų grafų skaičius .
Izomorfinių grafų skaičius. Yra žinoma Pojos formulė: gn asimptotiškai lygu !. Žodžiai “asimptotiškai lygu“ reiškia, kad
.
Iš pirmo žvilgsnio atrodo, kad žymėtųjų n viršūnių grafų yra n! daugiau negu abstrakčių n viršūnių grafų. Šis faktas atrodo intuityviai aiškus, nes egzistuoja lygiai n! būdų, kaip priskirti žymes viršūnėms, kurių skaičius yra n. Tačiau šio teiginio klaidingumą rodo tai, kad ne iš kiekvieno abstraktaus grafo gauname n! žymėtųjų grafų. Pavyzdžiui, visi žymėtieji tuštieji grafai yra lygūs; paprastoji trijų viršūnių grandinė duoda tris, o...

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!