Wykres tolerancji

W teorii grafów graf tolerancji jest grafem nieskierowanym , w którym każdy wierzchołek może być reprezentowany przez domknięty przedział i liczbę rzeczywistą zwaną jego tolerancją, w taki sposób, że dwa wierzchołki na grafie sąsiadują ze sobą, ilekroć ich przedziały nakładają się na długość jest co najmniej minimum z ich dwóch tolerancji. Ta klasa grafów została wprowadzona w 1982 roku przez Martina Charlesa Golumbica i Clyde'a Monmę, którzy użyli ich do modelowania problemów z planowaniem , w których modelowane zadania mogą współdzielić zasoby przez ograniczony czas.

Każdy wykres interwałowy jest wykresem tolerancji. Wykres dopełnienia każdego wykresu tolerancji jest wykresem doskonale uporządkowanym , z którego wynika, że ​​same wykresy tolerancji są wykresami doskonałymi .

Określenie, czy dany wykres jest wykresem tolerancji, jest NP-zupełne . Ponieważ jednak wykresy tolerancji są wykresami doskonałymi, wiele problemów algorytmicznych, które są trudne w przypadku innych klas wykresów, w tym kolorowanie wykresów i problem kliki , można rozwiązać w czasie wielomianowym na wykresach tolerancji.