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