Diferencia entre revisiones de «Isomorfismo de grafos»

44 bytes añadidos ,  hace 12 años
m (robot Añadido: fr:Isomorphisme de graphes)
Dos grafos con [[matriz de adyacencia|matrices de adyacencia]] respectivas ''A'' y ''B'' serán isomofos si y solo si existe una [[matriz permutación]] ''P'' tal que ''B = P A P<sup>-1</sup>''.<ref>Jonathan L. Gross, Jay Yellen.''Handbook of Graph Theory''. CRC Press, 2004. ISBN 158488090</ref>
== Problema del isomorfismo de grafos ==
{{AP|Problema de isomorfismo de subgrafos}}
La determinación de si dos grafos con el mismo número de vértices n y aristas son isomorfos o no se conoce como el '''problema del isomorfismo de grafos'''. Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n! biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, al menos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a [[cota superior asintótica|O(e<sup>n</sup>)]].