Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов и информатике задача сэндвича с графами - это проблема поиска графа, который принадлежит к определенному семейству графов и «зажат» между двумя другими графами, один из которых должен быть подграфом, а другой должен быть суперграф искомого графа.

Задачи сэндвича с графами обобщают проблему проверки принадлежности данного графа семейству графов и привлекают внимание благодаря своим приложениям и как естественное обобщение задач распознавания. [1]

Формулировка проблемы [ править ]

Точнее, учитывая набор вершин V , обязательный набор ребер E 1 и больший набор ребер E 2 , граф G  = ( V ,  E ) называется сэндвич- графом для пары G 1  = ( V ,  E 1 ) , G 2  = ( V ,  E 2 ), если E 1 ⊆ E ⊆ E 2 . Задача сэндвича графа для свойства Π определяется следующим образом: [2] [3]

Задача графического сэндвича для собственности Π :
Экземпляр: множество вершин V и краевые множества Е 1 ⊆ E 2 ⊆ V × V .
Вопрос: существует ли граф G = ( V , E ) такой, что E 1 ⊆ E ⊆ E 2 и G удовлетворяет свойству Π?

Проблема распознавания для класса графов (удовлетворяющих свойству Π) эквивалентна конкретной задаче сэндвича графа, где E 1  =  E 2 , то есть необязательный набор ребер пуст.

Вычислительная сложность [ править ]

Проблема графы сэндвича NP-полная , когда Π является свойством быть хордой графа , сопоставимость граф , граф перестановка , хорда двудольного графа , или цепь граф . [2] [4] Это может быть решено за полиномиальное время для расщепленных графов , [2] [5] пороговых графов , [2] [5] и графов, в которых каждые пять вершин содержат не более одного индуцированного пути с четырьмя вершинами . [6] Статус сложности также был установлен для H-свободных проблемы графа сэндвич для каждой из четырех вершин графов H . [7]

Ссылки [ править ]

  1. ^ Голумбик, Мартин Чарльз; Тренк, Энн Н. (2004), «Глава 4. Графики интервального зондирования и сэндвич-задачи», Tolerance Graphs , Cambridge, pp. 63–83..
  2. ^ a b c d Голумбик, Мартин Чарльз; Каплан, Хаим; Шамир, Рон (1995), "Graph проблемы сэндвич", J. Алгоритмы , 19 : 449-473, DOI : 10,1006 / jagm.1995.1047.
  3. ^ Голумбик, Мартин Чарльз (2004), Алгоритмическая теория графов и совершенные графы , Анналы дискретной математики, 57 (2-е изд.), Elsevier, стр. 279 CS1 maint: обескураженный параметр ( ссылка ).
  4. ^ де Фигейредо, CMH; Faria, L .; Klein, S .; Шритаран, Р. (2007), "О сложности задач сэндвича для сильно хордовых графов и хордовых двудольных графов", Теоретическая информатика , 381 (1–3): 57–67, DOI : 10.1016 / j.tcs.2007.04 .007 , Руководство по ремонту 2347393 .
  5. ^ а б Махадев, NVR; Пелед, Ури Н. (1995), Пороговые графы и связанные темы , Annals of Discrete Mathematics, 57 , North-Holland, стр. 19–22.
  6. ^ Дантас, S .; Klein, S .; Мелло, КП; Morgana, A. (2009), "Проблема граф Сэндвич для P 4 -sparse графов", Дискретная математика , 309 : 3664-3673, DOI : 10.1016 / j.disc.2008.01.014.
  7. ^ Дантас, Симона; де Фигейредо, Селина М.Х.; Маффре, Фредерик; Тейшейра, Рафаэль Б. (2013), «Сложность задач о сэндвичах с запрещенными подграфами и задача о сэндвичах с перекосом разбиения», Дискретная прикладная математика : доступно онлайн 11 октября 2013 г., doi : 10.1016 / j.dam.2013.09.004.

Дальнейшее чтение [ править ]

  • Дантас, Симона; де Фигейредо, Селина М.Х.; да Силва, Мурило В.Г.; Тейшейра, Рафаэль Б. (2011), «О запрещенной проблеме индуцированного сэндвича подграфа», Дискретная прикладная математика , 159 : 1717–1725, DOI : 10.1016 / j.dam.2010.11.010.