Аноним

Пороговый граф: различия между версиями

Материал из WikiGrapp
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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> что множество всех
<math>(0,1)</math>-решений неравенства
<math>\,(0,1)</math>-решений неравенства


<math>\alpha_{1}x_{1} + \alpha_{2}x_{2} + \ldots + \alpha_{n}x_{n} \leq
<math>\alpha_{1}x_{1} + \alpha_{2}x_{2} + \ldots + \alpha_{n}x_{n} \leq
Строка 10: Строка 10:


совпадает с множеством характеристических векторов элементов множества
совпадает с множеством характеристических векторов элементов множества
<math>IG</math>, то граф <math>G</math> называется ''пороговым''.
<math>\,IG,</math> то граф <math>\,G</math> называется ''пороговым''.
==Литература==
==Литература==
[Лекции]
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.