En teoría de grafos , un grafo de tolerancia es un grafo no dirigido en el que cada vértice puede ser representado por un intervalo cerrado y un número real llamado su tolerancia, de tal manera que dos vértices son adyacentes en el gráfico siempre que sus intervalos se superpongan en una longitud que es al menos el mínimo de sus dos tolerancias. [1] Esta clase de gráficos fue introducida en 1982 por Martin Charles Golumbic y Clyde Monma, quienes los usaron para modelar problemas de programación en los que las tareas a modelar pueden compartir recursos por períodos de tiempo limitados. [2]
Cada gráfico de intervalo es un gráfico de tolerancia. [3] El gráfico de complemento de todo gráfico de tolerancia es un gráfico perfectamente ordenable , de lo que se deduce que los propios gráficos de tolerancia son gráficos perfectos . [4]
Es NP-completo para determinar si un gráfico dado es un gráfico de tolerancia. [5] Sin embargo, debido a que los gráficos de tolerancia son gráficos perfectos, muchos problemas algorítmicos que son difíciles en otras clases de gráficos, incluido el coloreado de gráficos y el problema de la camarilla , se pueden resolver en tiempo polinomial en gráficos de tolerancia. [3]