Los gráficos se usan 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, comúnmente se asume que la comparación es entre el gráfico de datos y el gráfico del modelo .
El caso de coincidencia exacta de gráficos se conoce como problema de isomorfismo de gráficos . [1] El problema de la coincidencia exacta de un gráfico con una parte de otro gráfico se llama problema de isomorfismo de subgrafo .
El emparejamiento de gráficos inexactos se refiere a problemas de emparejamiento cuando el emparejamiento exacto es imposible, por ejemplo, cuando el número de vértices en los dos gráficos es diferente. En este caso se requiere encontrar la mejor coincidencia posible. Por ejemplo, en las aplicaciones de reconocimiento de imágenes , los resultados de la segmentación de imágenes en el procesamiento de imágenes normalmente producen gráficos de datos con un número de vértices mucho mayor que en los gráficos de 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 puede ser solo inexacta. [1]
Dos categorías de métodos de búsqueda son los 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 grafos tolerantes a errores. [5]