La coincidencia 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 comparación de gráficos es una herramienta importante en estas áreas. [2] En estas áreas comúnmente se supone que la comparación se realiza entre el gráfico de datos y el gráfico del modelo .
El caso de la coincidencia exacta de gráficos se conoce como problema de isomorfismo de gráficos . [1] El problema de hacer coincidir exactamente un gráfico con una parte de otro gráfico se llama problema de isomorfismo de subgrafo .
La coincidencia de gráficos inexacta se refiere a problemas de coincidencia cuando la coincidencia exacta es imposible, por ejemplo, cuando el número de vértices en los dos gráficos es diferente. En este caso es necesario encontrar la mejor combinación 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 gráficos de datos con un número de vértices mucho mayor que en los gráficos del modelo con los que se espera que coincidan los datos. En el caso de gráficos atribuidos , incluso si el número de vértices y aristas es el mismo, la coincidencia aún puede ser inexacta. [1]
Dos categorías de métodos de búsqueda son las que se basan en la identificación de pares de vértices posibles e imposibles entre los dos gráficos y los métodos que formulan la coincidencia 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 comparación de gráficos. [4] [5] La clase de algoritmos se denomina coincidencia de gráficos tolerante a errores. [5]