Пороговый граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Пороговый граф''' (''Threshold graph'') - Пусть <math>IG</math> --- множество, элементами кот...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Пороговый граф''' (''Threshold graph'') - | '''Пороговый граф''' (''[[Threshold graph]]'') - | ||
Пусть <math>IG</math> --- множество, элементами которого служат все независимые | Пусть <math>IG</math> --- множество, элементами которого служат все независимые | ||
подмножества вершин графа <math>G</math> и пустое множество; если существуют | подмножества [[вершина|вершин]] [[граф|графа]] <math>G</math> и пустое множество; если существуют | ||
такие неотрицательные вещественные числа <math>\alpha_{1}, \; \alpha_{2}, | такие неотрицательные вещественные числа <math>\alpha_{1}, \; \alpha_{2}, | ||
\; \ldots, \; \alpha_{n}, \; \beta</math>, что множество всех | \; \ldots, \; \alpha_{n}, \; \beta</math>, что множество всех | ||
Версия от 15:27, 23 декабря 2009
Пороговый граф (Threshold graph) - Пусть [math]\displaystyle{ IG }[/math] --- множество, элементами которого служат все независимые подмножества вершин графа [math]\displaystyle{ G }[/math] и пустое множество; если существуют такие неотрицательные вещественные числа [math]\displaystyle{ \alpha_{1}, \; \alpha_{2}, \; \ldots, \; \alpha_{n}, \; \beta }[/math], что множество всех [math]\displaystyle{ (0,1) }[/math]-решений неравенства
[math]\displaystyle{ \alpha_{1}x_{1} + \alpha_{2}x_{2} + \ldots + \alpha_{n}x_{n} \leq \beta }[/math]
совпадает с множеством характеристических векторов элементов множества [math]\displaystyle{ IG }[/math], то граф [math]\displaystyle{ G }[/math] называется пороговым.
Литература
[Лекции]