Isomorfisme de grafs

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

${\displaystyle f:V(G)\rightarrow V(H)}$

amb la propietat de què qualsevol dos vèrtex u i v de G són 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 introduint é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 Garey & Johnson (1979) 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 grafs 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 problema d'isomorfisme de subgrafs és una generalització NP-completa.

Exemple

Els dos grafs que es mostren a continuació són 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
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$

Dos grafs amb matrius d'adjacència respectives A i B seran isomorfes si i només si existeix una matriu permutacióPtal queB = PAP ^-1 .^[2]

Referències

1. McKay 1981
2. Jonathan L. Gross, Jay Yellen.Handbook of Graph Theory. CRC Press, 2004. ISBN 1584880902