Категория:Хордальные графы

Граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три. Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи в этом классе графов решаются полиномиальными алгоритмами, хотя эти же задачи для произвольных графов являются NP-полными.