47
правок
Well-covered graph: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
ALEXM (обсуждение | вклад) Нет описания правки |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
Let <math>\beta</math>, respectively <math>i</math>, denote the maximum, respectively | Let <math>\beta</math>, respectively <math>i</math>, denote the maximum, respectively | ||
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 </math> | ||
and <math>\beta + \Delta = \lceil2\sqrt{n} - 1\rceil</math>. The problem of | 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. | ||