Пороговый граф

Пороговый граф (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] называется пороговым.

Литература

[Лекции]