4624
правки
Пороговый граф: различия между версиями
Материал из WikiGrapp
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Пороговый граф''' (''Threshold graph'') - Пусть <math>IG</math> --- множество, элементами кот...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 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. | |||
