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

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

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.