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

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


Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи
Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи
решаются полиномиальными алгоритмами в этом классе, хотя эти же задачи для произвольных графов являются ''NP-полными''.
решаются полиномиальными [[алгоритм|алгоритмами]] в этом классе, хотя эти же задачи для произвольных графов являются ''[[NP-Полная задача|NP-полными]]''.
==Литература==
==Литература==
[Golumbic],  
[Golumbic],  

Версия от 18:37, 5 апреля 2010

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

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

Литература

[Golumbic],

[Лекции],

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