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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 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.

Версия от 15:33, 3 марта 2017

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.