4635
правок
Пороговый граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
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> что множество всех | ||
<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>\,IG,</math> то граф <math>\,G</math> называется ''пороговым''. | ||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||