Хордальный граф: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Хордальный граф''' (''[[Chordal graph]]'') | '''Хордальный граф''' (''[[Chordal graph]]'') — [[граф]], не содержащий [[индуцированный подграф|индуцированных подграфов]], [[изоморфизм графов|изоморфных]] [[цикл|циклу]] <math>\,C_{k}</math> для всех <math>k \geq 4</math>. Другими словами, в хордальном графе любой цикл длины больше 3 имеет [[хорда|хорду]] (отсюда и название). | ||
[[граф]], не содержащий [[индуцированный подграф|индуцированных подграфов]], [[изоморфизм графов|изоморфных]] [[цикл|циклу]] | |||
<math>C_{k}</math>для всех <math>k \geq 4</math>. Другими словами, в хордальном графе любой | |||
цикл длины больше 3 имеет [[хорда|хорду]] (отсюда и название). | |||
Хордальные графы называются | Хордальные графы называются | ||
также ''[[триангулированный граф|триангулированными]]''. Подклассами хордальных графов являются | также ''[[триангулированный граф|триангулированными]]''. Подклассами хордальных графов являются | ||
''[[дерево|деревья]], [[интервальный граф|интервальные графы]], [[расщепляемый граф|расщепляемые графы]], [[строго хордальный граф|строго хордальные графы]], [[дважды хордальный граф|дважды хордальные графы]], [[ | ''[[дерево|деревья]], [[интервальный граф|интервальные графы]], [[расщепляемый граф|расщепляемые графы]], [[строго хордальный граф|строго хордальные графы]], [[дважды хордальный граф|дважды хордальные графы]], хордальные [[граф сравнимости|графы сравнимости]]'' и др. | ||
Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи | Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи | ||
решаются полиномиальными [[алгоритм|алгоритмами]] в этом классе, хотя эти же задачи для произвольных графов являются ''[[NP-Полная задача|NP-полными]]''. | решаются полиномиальными [[алгоритм|алгоритмами]] в этом классе, хотя эти же задачи для произвольных графов являются ''[[NP-Полная задача|<math>\mathcal{NP}</math>-полными]]''. | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А. Хордальные графы и их свойства //Проблемы систем информатики и программирования. — Новосибирск: ИСИ СО РАН, 1998. | |||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
* Golumbic M.C. Algorithmic graph theory and perfect graphs. — New York: Academic Press, 1980. | |||
Текущая версия от 15:08, 29 сентября 2011
Хордальный граф (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.