¿Cuál es el significado de decir "dos gráfico vértices están en correspondencia?"

Question

¿Cuáles son las condiciones para que dos gráficos estar en correspondencia?

Sé que es isomorfo - Dos gráficos que contienen el mismo número de vértices del grafo conectado de la misma manera se dice que son isomorfos.

Pero, ¿cómo es isomorfo diferente de la correspondencia? no sólo a la correspondencia significa que el número de vértices debe ser el mismo?

Estaba leyendo este artículo de investigación cuando el autor dice que "asumimos que la conectividad de la relación es simétrica, por lo que las redes pueden ser representados como simétrica ponderado de los gráficos.Vamos a suponer también que los dos gráficos vértices están ya en la correspondencia, y por lo tanto en este trabajo no se aborda la comparación gráfica de problema"

Fuente: David K. Hammond, Yaniv Gur, Chris R. Johnson, 2013 IEEE Conferencia Mundial sobre la Señal y el Procesamiento de la Información, "Gráfico de la distancia de difusión: Una diferencia de medida para ponderado de gráficos basados en el gráfico Laplaciano exponencial del núcleo" https://www.sci.utah.edu/publications/hammond13/Hammond_GlobalSIP2013.pdf

Answer 1

La pregunta es: ¿Qué hace el gráfico correspondiente significa en este contexto? Al final de la citada frase es una cita de "Treinta Años De juego Gráfico En el Reconocimiento de patrones". Que el artículo dice:

El gráfico correspondiente es el proceso de encontrar una correspondencia entre los nodos y las aristas de los dos gráficos que satisfaga a algunos (más o menos estrictos) restricciones de garantizar que los similares de las subestructuras en una gráfica se asignan a similar subestructuras en el otro.

Eso es vaga, por lo que el artículo a continuación, se rompe el gráfico correspondiente a los diversos problemas concretos: gráfico de isomorfismo, subgrafo isomorfismo, monomorphism, homomorphism, máximo común subgrafo, y inexacta versiones que reducir algunos costos.

Su artículo no parece estar interesado en los detalles. Así que, para hacer corta una larga historia, es sólo un bijection de un conjunto de vértices para el otro. De hecho, este bijection incluso no se hizo explícito; el resto del artículo se asume que los dos gráficos tienen el mismo vértice conjunto.