Хордальный граф

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

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

Литература

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

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

• Golumbic M.C. Algorithmic graph theory and perfect graphs. — New York: Academic Press, 1980.