График допуска - Tolerance graph

В теория графов, а график допуска является неориентированный граф в котором каждая вершина может быть представлена закрытый интервал и действительное число, называемое его допуском, таким образом, что две вершины являются смежными в графе всякий раз, когда их интервалы перекрываются на длине, которая по крайней мере является минимумом из их двух допусков.[1]Этот класс графов был введен в 1982 г. Мартин Чарльз Голумбик и Клайд Монма, который использовал их для моделирования планирование задачи, в которых моделируемые задачи могут совместно использовать ресурсы в течение ограниченного времени.[2]

Каждые интервальный график - график допусков.[3] В дополнительный граф каждого графика допусков - это идеально упорядочиваемый график, откуда следует, что сами графики допусков идеальные графики.[4]

это НП-полный чтобы определить, является ли данный график графиком допусков.[5]Однако, поскольку графы допусков являются идеальными графами, многие алгоритмические проблемы, которые трудно решить для других классов графов, включая раскраска графика и проблема клики, можно решить в полиномиальное время на графиках допусков.[3]

использованная литература

  1. ^ Голумбик, Мартин Чарльз; Тренк, Энн Н. (2004), Графики допусков, Кембриджские исследования по высшей математике, 89, Cambridge University Press, Кембридж, стр. xii + 265, Дои:10.1017 / CBO9780511542985, ISBN  0-521-82758-2, Г-Н  2051713
  2. ^ Голумбик, Мартин К.; Монма, Клайд Л. (1982), "Обобщение интервальных графов с допусками", Труды тринадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1982), Congressus Numerantium, 35: 321–331, Г-Н  0725892
  3. ^ а б «Graphclass: толерантность», Информационная система по классам графов и их включениям, получено 2019-09-30
  4. ^ Голумбик, Мартин Чарльз; Monma, Clyde L .; Троттер, Уильям Т. мл. (1984), «Графики допусков», Дискретная прикладная математика, 9 (2): 157–170, Дои:10.1016 / 0166-218X (84) 90016-7, Г-Н  0761599
  5. ^ Мерциос, Джордж Б .; Сау, Игнаси; Закс, Шмуэль (2011), «Распознавание допусков и графиков ограниченных допусков» (PDF), SIAM Журнал по вычислениям, 40 (5): 1234–1257, Дои:10.1137/090780328, Г-Н  2854571