cómo determinar si dos gráficos no son isomorfos

Question

¿Cuáles son algunas buenas formas de determinar si dos gráficos de aspecto razonablemente sencillo no son isomorfos? Sé que se puede comprobar su ciclo o alguna propiedad extraña (para ciertos grafos), pero ¿hay otros trucos para hacerlo?

Answer 1

Como probablemente sepa, el isomorfismo de grafos se sospecha que es un problema difícil (y no se conocen algoritmos eficientes que resuelvan el problema). Sin embargo, tampoco se sabe que el problema sea NP-Hard.

Las formas más fáciles de demostrar el no isomorfismo rápidamente son

• ver si las cardinalidades del conjunto de vértices difieren
• ver si las cardinalidades de los conjuntos de aristas difieren
• comparar secuencias de grados
• comparar el número de componentes conectados (suponiendo grafos no dirigidos)

Hay otras innumerables comprobaciones que se pueden hacer en tiempo polinómico, a menudo mediante aplicaciones de DFS. Pero ninguna garantizará que pasar la comprobación implica que los grafos son isomorfos.

Hay algoritmos aleatorios que se pueden ejecutar para comprobar el no isomorfismo: básicamente prueban partes aleatorias del grafo con la esperanza de encontrar algo raro. Busca en Google "Monte carlo graph isomorphism" si quieres más detalles.

Answer 2

Varios invariantes ya se han mencionado. También hay algunos invariantes naturales que se derivan de las propiedades del "álgebra lineal" del matriz de adyacencia del gráfico, en particular valores propios del gráfico y los vectores propios.

Estas invariantes han sido muy estudiadas. Aunque, por desgracia, no son lo suficientemente potentes como para establecer el no isomorfismo en todos los casos, son útiles desde el punto de vista computacional, ya que existe un software muy eficiente para tratar con matrices grandes.

Answer 3

Utilizar un ordenador. El programa "Nauty and Trace" ofrece un procedimiento computacional para resolver este problema. Este paquete de código abierto está disponible en http://pallini.di.uniroma1.it/ .

Otro enlace útil puede ser http://www.dharwadker.org/tevet/isomorphism/

Answer 4

Con la práctica, a menudo se puede decir rápidamente que los gráficos no son isomorfos. Cuando los grafos G y H son isomorfos tienen el mismo número cromático, si uno tiene un circuito euleriano o hamiltoniano también lo tiene el otro, si G es plano también lo es H, si uno es conectado también lo es el otro. Si uno tiene dibujos de los dos gráficos, nuestros sistemas visuales están tan acostumbrados a encontrar patrones que ver que los dos gráficos tienen alguna propiedad que no comparten a menudo hace que sea fácil mostrar que los gráficos no son isomorfos.

Answer 5

comprobar la correspondencia entre vértices y bordes en dos gráficos diferentes..

para los vértices del mismo grado comprueba el grado de los vértices adyacentes si los grados son homogéneos en ambos gráficos entonces el gráfico es isomorfo...