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

Материал из WikiGrapp
Версия от 16:27, 9 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Хордальный граф''' (''Chordal graph'') - граф, не содержащий индуцированных подграф...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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

Литература

[Golumbic],

[Лекции],

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