Well-covered graph: различия между версиями
Перейти к навигации
Перейти к поиску
AlexM (обсуждение | вклад) Нет описания правки |
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. | ||
Текущая версия от 13:39, 25 марта 2012
Well-covered graph --- хорошо покрытый граф.
Let [math]\displaystyle{ \beta }[/math], respectively [math]\displaystyle{ i }[/math], denote the maximum, respectively minimum, cardinality of a maximal independent set of [math]\displaystyle{ G }[/math]. A graph is mathcalled well-covered if for this graph [math]\displaystyle{ i = \beta }[/math] and [math]\displaystyle{ \beta + \Delta = \lceil2\sqrt{n} - 1\rceil }[/math]. The problem of determining whether or not a graph is not well-covered is NP-complite.