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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «Граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три....»)
(нет различий)

Версия от 09:28, 13 декабря 2024

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

Страницы в категории «Хордальные графы»

Показано 7 страниц из 7, находящихся в данной категории.