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

Материал из WikiGrapp
Перейти к:навигация, поиск

Пороговый граф (Threshold graph) — Пусть \,IG — множество, элементами которого служат все независимые подмножества вершин графа \,G и пустое множество; если существуют такие неотрицательные вещественные числа \alpha_{1}, \; \alpha_{2},
\; \ldots, \; \alpha_{n}, \; \beta, что множество всех \,(0,1)-решений неравенства

\alpha_{1}x_{1} + \alpha_{2}x_{2} + \ldots + \alpha_{n}x_{n} \leq
\beta

совпадает с множеством характеристических векторов элементов множества \,IG, то граф \,G называется пороговым.

Литература

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