Veo una pregunta sobre Grafo Isomorfo. la pregunta es:
¿El gráfico de la primera línea no es isomorfo con cuál de los de la segunda línea?
¿Cómo podemos encontrar un grafo isomorfo sin conocer algún mapa geométrico (como rotar o ...)?
Respuestas
¿Demasiados anuncios?
Creo que el método más sencillo sería reconocer el grafo dado como un pentágono con dos vértices no adyacentes conectados (ya que a $5$ -es isomorfa a una estrella simple $5$ -ciclo; un pentágono). La conexión no es una arista única, sino una arista que se ha convertido en dos aristas colocando un punto en el medio.
Puedes identificar que tres de los cuatro gráficos se pueden construir de esta misma manera.
Alternativamente, el $4$ El gráfico de la segunda fila es el único con un $6$ -ciclo, pero eso es un poco más difícil de ver para mí, personalmente.
Shabaz
Puntos
403
Todos los grafos tienen dos vértices de orden tres y cuatro de orden dos. El último gráfico tiene los dos vértices de orden tres conectados por una arista, mientras que el resto no. Por tanto, no es isomorfo a ningún otro. No he demostrado que el resto sean isomorfos, pero es suficiente para la pregunta.
fgysin
Puntos
3253
Los algoritmos actuales no resuelven el isomorfismo de grafos de forma eficiente en el peor de los casos. El mejor resultado es un algoritmo de Babai, Kantor y Luks que se ejecuta en $2^{O(\sqrt{n \log n})}$ tiempo [Babai, Kantor y Luks, Computational complexity and the classification of finite simple groups, 1983].
Si no te importa el peor de los casos, existen algoritmos heurísticos que funcionan en tiempo lineal para todos los grafos excepto para una proporción exponencialmente pequeña. Véase [Practical graph isomorphism II, McKay y Piperno, 2013].
