Isomorfisme de grafs

De Viquipèdia

En teoria de grafs, un isomorfisme de graf és una funció f bijectiva entre els vèrtex de dos grafs G i H.

amb la propietat de que qualsevol dos vèrtex u i v de G son adjacents si i només si f(u) i f(v) són adjacents en H.

Si es pot construir un isomorfisme entre dos grafs, llavors diem que aquests dos grafs són isomòrfics. La determinació de si dos grafs són isomòrfics o no és coneguda com el problema d'isomorfisme de grafs. El problema d'isomorfisme de grafs es manifesta en diverses aplicacions pràctiques. Tant en investigació química com en disseny de circuits és important la construcció de bases de dades de grafs; en aquest cas, volem saber si el nou graf que estem introduïnt és el mateix que un que ja existeix, per a estalviar emmagatzemament i detectar correspondències entre dades.

A més de la seva importància per a aquestes aplicacions, el problema d'isomorfisme de grafs és una curiositat en teoria de la complexitat computacional ja que és un dels pocs problemes llistats per Plantilla:Harvtxt com a pertanyents a NP, però no conegut per ser en temps polinòmic ni NP-complet, encara que l'isomorfisme per moltes classes especials de graphs pot ser resolt en temps polinòmic i en la pràctica l'isomorfisme de grafs pot ser sovint resolt eficientment. ^[1]

Una generalització, el el problema d'isomorfisme de subgrafs és una generalització NP-completa.

[edita] Exemple

Els dos grafs que es mostren a continuació son isomorfs, tot i que semblen dibuixos molt diferents, degut a l'existència de la bijecció descrita a la columna dreta.

Graf G	Graf H	Un isomorfisme entre G i H
		f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7