La correspondencia de gráficos es el problema de encontrar una similitud entre gráficos . [1]
Los gráficos se utilizan comúnmente para codificar información estructural en muchos campos, incluida la visión por computadora y el reconocimiento de patrones , y la coincidencia de gráficos es una herramienta importante en estas áreas. [2] En estas áreas, se asume comúnmente que la comparación es entre el gráfico de datos y el gráfico del modelo .
El caso de coincidencia exacta de grafos se conoce como problema de isomorfismo de grafos . [1] El problema de coincidencia exacta de un grafo con una parte de otro grafo se denomina problema de isomorfismo de subgrafos .
La coincidencia inexacta de grafos se refiere a problemas de coincidencia en los que la coincidencia exacta es imposible, por ejemplo, cuando el número de vértices en los dos grafos es diferente. En este caso, se requiere encontrar la mejor coincidencia posible. Por ejemplo, en aplicaciones de reconocimiento de imágenes , los resultados de la segmentación de imágenes en el procesamiento de imágenes generalmente producen grafos de datos con un número de vértices mucho mayor que en los datos de los grafos del modelo con los que se espera que coincidan. En el caso de grafos atribuidos , incluso si el número de vértices y aristas es el mismo, la coincidencia puede ser solo inexacta. [1]
Existen dos categorías de métodos de búsqueda: los que se basan en la identificación de emparejamientos posibles e imposibles de vértices entre dos gráficos y los métodos que formulan la correspondencia de gráficos como un problema de optimización . [3] La distancia de edición de gráficos es una de las medidas de similitud sugeridas para la correspondencia de gráficos. [4] [5] La clase de algoritmos se denomina correspondencia de gráficos tolerante a errores. [5]