Well-covered graph: различия между версиями

Перейти к навигации Перейти к поиску
Отмена правки 10256 участника AlexM (обсуждение)
Нет описания правки
(Отмена правки 10256 участника AlexM (обсуждение))
 
Строка 4: Строка 4:
minimum, cardinality of a maximal ''independent set'' of <math>G</math>. A
minimum, cardinality of a maximal ''independent set'' of <math>G</math>. A
graph is mathcalled ''' well-covered''' if for this graph <math>i = \beta
graph is mathcalled ''' well-covered''' if for this graph <math>i = \beta
and \beta + \Delta = \lceil2\sqrt{n} - 1\rceil</math>. The problem of
</math> and <math>\beta + \Delta = \lceil2\sqrt{n} - 1\rceil</math>. The problem of
determining whether or not a graph is '' not'' well-covered is
determining whether or not a graph is '' not'' well-covered is
''NP''-complite.
''NP''-complite.
12

правок

Навигация