Алгоритм распознавания принадлежности хордального графа классу графов C

Abstract

Граф G называется полярным, если существует такое разбиение его множества вершин VG на части A и B, что все связные компоненты порожденного подграфа G(B) и дополнительного )(AG являются полными графами [1]. Известно, что проблема распознавания полярности – NP-полная [1]. Выходом из сложившейся ситуации является попытка ее решения в более узких классах графов. Граф G принадлежит классу C, если множество VG можно разбить на два подмножества A и B, что порожденный подграф G(A) – пустой, а в G(B) степени вершин равны 0, либо 1 [1]. Однако и задача распознавания принадлежности графа классу C является NP-полной [1]. Поэтому на исходный граф накладывается еще одно ограничение: хордальность. В результате разработан полиномиальный алгоритм распознавания принадлежности хордального графа классу C.