Independence number: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Independence number''' --- число независимости, число внутренней устойчивости, неплотность. For a graph …») |
(нет различий)
|
Текущая версия от 13:57, 19 мая 2011
Independence number --- число независимости, число внутренней устойчивости, неплотность.
For a graph [math]\displaystyle{ G }[/math], independence number [math]\displaystyle{ \beta(G) }[/math] is the size of a maximum independent set of [math]\displaystyle{ G }[/math]. The lower independence number [math]\displaystyle{ i(G) }[/math] is the minimum cardinality of a maximal independent set. (Because an independent set is maximally independent if and only if it is dominating, [math]\displaystyle{ i(G) }[/math] is also called the independent-domination number of [math]\displaystyle{ G }[/math].)
The other name is Stability number.
See also
- Transversal,
- Local independence number.