1249
правок
KVN (обсуждение | вклад) (Новая страница: «Граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три....») |
KVN (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
Граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три. | [[Граф]] называется [[Хордальный граф|хордальным]], если каждый из его [[Цикл|циклов]], имеющих четыре [[Ребро|ребра]] и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Другими словами, хордальный граф — это граф без [[Порожденный подграф|порождённых]] циклов длины более чем три. | ||
Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи в этом классе графов решаются полиномиальными алгоритмами, хотя эти же задачи для произвольных графов являются NP-полными. | Важным свойством хордальных графов является тот факт, что многие классические экстремальные задачи в этом классе графов решаются полиномиальными алгоритмами, хотя эти же задачи для произвольных графов являются [[NP-Полная задача|NP-полными]]. |