Izomorfizem grafov

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

Izomorfízem gráfov G in H je v teoriji grafov takšna bijektivna preslikava med množico točk G in H:

da sta poljubni dve točki u in v grafa G sosednji v G, če in samo če sta ƒ(u) in ƒ(v) sosednji v H. Ta vrsta bijektivne preslikave se običajno opiše kot »bijektivna preslikava, ki ohranja točke« v soglasju s splošno predstavo o izomorfizmu kot bijektivni preslikavi, ki ohranja strukturo.

Če med dvema grafoma G in H obstaja izomorfizem, sta grafa med seboj izomorfna, kar se označi kot . V primeru, če je bijektivna preslikava preslikava grafa v samega sebe, torej kadar sta G in H kar en in isti graf, se ta bijektivna preslikava imenuje avtomorfizem grafa G.

Izomorfizem grafov je ekvivalenčna relacija na grafih in kot taka razdelili razred vseh grafov v ekvivalenčne razrede. Množica med seboj izomorfnih grafov se imenuje razred izomorfizmov grafov.

Spodaj prikazana grafa sta izomorfna čeprav sta njuni sliki različni.

graf G graf H izomorfizem
med G in H
permutacija
izomorfizma
Graph isomorphism a.svg Graph isomorphism b.svg f(a) = 1

f(b) = 6

f(c) = 8

f(d) = 3

f(g) = 5

f(h) = 2

f(i) = 4

f(j) = 7

Različice grafov[uredi | uredi kodo]

V zgornji definiciji so mišljeni neusmerjeni neoznačeni neuteženi grafi. Pojem izomorfizma se lahko uporabi tudi na vse druge različice pojma grafa z dodajanjem zahtev za ohranitev odgovarjajočih dodatnih elementov strukture: smeri lokov, teže povezav, itd. z naslednjo izjemo.

Izomorfizem označenih grafov[uredi | uredi kodo]

Za označene grafe se rabita dve definiciji.

Po eni definiciji je izomorfizem bijektivna preslikava točk, ki ohranja povezave in hkrati ohranja oznake.[1][2]

Po drugi definiciji je izomorfizem bijektivna preslikava točk, ki ohranja povezave in ohranja ekvivalenčne razrede oznak, točke z ekevivalentnimi (oziroma enakimi) oznakami se preslikajo v točke z ekvivalentnimi oznakami in obratno, enako z oznakami povezav.[3]

Graf z dvema točkama, označenima z 1 in 2, ima na primer en avtomorfizem po prvi definiciji in dva avtomorfizma po drugi definiciji.

Druga definicija se privzema v določenih primerih, ko imajo grafi edinstvene oznake običajno vzete iz množice celih števil 1,...,n, kjer je n število točk grafa, ki se rabijo le za enolično označitev točk. V takšnih primerih sta dva označena grafa izomorfna, če sta izomorfna odgovarjajoča osnovna neoznačena grafa, drugače bi bila definicija izomorfizma trivialna.

Motivacija[uredi | uredi kodo]

Formalna predstava »izomorfizma«, oziroma »izomorfizma grafov«, zavzema neformalno predstavo o tem, da imajo nekateri objekti »enako strukturo«, če se zanamerijo posamezne različnosti »atomskih« komponent obravnavanih objektov. Kadar je posameznost »atomskih« komponent (točk in povezav za grafe) pomembna za pravilno reprezentacijo tistega kar modelirajo grafi, se model izboljša z naložitvijo dodatnih omejitev na strukturo ali pa se uporabijo drugi matematični objekti: digrafi, označeni grafi, obarvani grafi, drevesa s korenom ipd. Relacija izomorfizma se lahko definira tudi za vse te posplošitve grafov: izomorfna bijektivna preslikava mora ohranjati elemente strukture, ki definira obravnavano vrsto objekta: loke, oznake, barve točk/povezav, koren dreves s korenom, itd.

Pojem »izomorfizma grafov« omogoča razlikovanje invariant grafov, ki pripadajo strukturam samih grafov, od invariant, ki so povezane z reprezentacijami grafov: slike grafov, podatkovne strukture za grafe, označevanje grafov itd. Če ima na primer graf točno en cikel, potem imajo tudi vsi grafi v njegovem izomorfnem razredu točno en cikel. Na drugi strani v splošnem primeru, kadar so točke grafa predstavljene s celimi števili 1, 2,... N, potem je lahko izraz:

različen za dva izomorfna grafa.

Whitneyjev izrek[uredi | uredi kodo]

Izjema Whitneyjevega izreka: ta dva grafa nista izomorfna, imata pa izomorfna povezavna grafa.

Whitneyjev izrek izomorfizma grafov,[4] ki ga je podal Hassler Whitney, pravi, da sta dva povezana grafa izomorfna, če in samo če sta izomorfna njuna povezavna grafa, z eno izjemo: K3, polnega grafa na 3-točkah in polnega dvodelnega grafa K1,3 (šape), ki med seboj nista izomorfna, njun povezavni graf pa je K3. Whitneyjev izrek se lahko posploši na hipergrafe.[5]

Prepoznavanje izomorfizma grafov[uredi | uredi kodo]

Čeprav se lahko izomorfizem grafov raziskuje na klasični matematični način, kot pokaže Whitneyjev izrek, se kot problem obravnava algoritemsko. Računski problem prepoznavanja izomorfizma dveh grafov se imenuje problem izomorfizma grafov.

Med praktične uporabe spadajo: kemoinformatika, matematična kemija (identifikacija spojin) in avtomatizacija načrtovanja elektronike (EDA, preverjanje enakovrednosti različnih predstavitev konstrukcij elektronskih vezij).

Problem izomorfizma grafov je en od standardnih problemov v računski teoriji zahtevnosti in pripada razredu NP. Ni pa znano ali pripada (oziroma ali velja (problem P = NP|P ≠ NP]]) eni od njenih zelo znanih disjunktnih množic: P in NP-polnost. Je eden od skupaj 12-ih problemov, navedenih v delu Gareyja in Johnsona Computers and Intractability iz leta 1979[6] in njegova zahtevnost ostaja nerešena. Znano je, da če je problem NP-poln, se polinomska hierarhija zruši na končni nivo.[7]

Novembra 2015 je László Babai, matematik in računalnikar z Univerze v Chicagu, najavil dokaz, da je problem izomorfizma grafov rešljiv v kvazipolinomskem času. Njegovo delo še ni potrjeno.[8][9]

Posplošitev problema, problem izomorfizma podgrafa, je NP-poln.

Glavna področja raziskovanja problema so načrtovanje hitrih algoritmov in teoretični izsledki njegove računske zahtevnosti tako za splošni problem kot za posebne razrede grafov.

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]