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