Хордальный граф: различия между версиями

'''Хордальный граф''' (''[[Chordal graph]]'') — [[граф]], не содержащий [[индуцированный подграф|индуцированных подграфов]], [[изоморфизм графов|изоморфных]] [[цикл|циклу]] <math>\,C_{k}</math> для всех <math>k \geq 4</math>. Другими словами, в хордальном графе любой цикл длины больше 3 имеет [[хорда|хорду]] (отсюда и название).

''[[дерево|деревья]], [[интервальный граф|интервальные графы]], [[расщепляемый граф|расщепляемые графы]], [[строго хордальный граф|строго хордальные графы]], [[дважды хордальный граф|дважды хордальные графы]], хордальные [[граф сравнимости|графы сравнимости]]'' и др.

решаются полиномиальными [[алгоритм|алгоритмами]] в этом классе, хотя эти же задачи для произвольных графов являются ''[[NP-Полная задача|<math>\mathcal{NP}</math>-полными]]''.

* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998.

* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.