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

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

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

Литература

[Golumbic],

[Лекции],

[Евстигнеев/98]