Пороговый граф: различия между версиями
Перейти к навигации
Перейти к поиску
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. | |||
Текущая версия от 09:41, 21 июня 2011
Пороговый граф (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.