4817
правок
Независимые множества в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Независимые множества в случайных графах пересечений (посмотреть исходный код)
Версия от 08:42, 26 февраля 2020
, 26 февраля 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
Алгоритм: | '''Алгоритм:''' | ||
Дано: случайный граф пересечений <math>G_{n,m,p}</math>. | Дано: случайный граф пересечений <math>G_{n,m,p}</math>. | ||
| Строка 50: | Строка 50: | ||
2. '''for''' i: = 1 '''to''' m '''do''' | 2. '''for''' i: = 1 '''to''' m '''do''' | ||
3. '''begin''' | 3. '''begin''' | ||
4. выбрать случайную метку | 4. выбрать случайную метку <math>l_i \in L</math>; положить <math>L := L - \{ l_i \}</math>; | ||
5. положить | 5. положить <math>D_i := \{ v \in A_{i - 1} : l_i \in S_v \}</math>; | ||
6. if(| | 6. '''if''' <math>(|D_i| \ge 1)</math> '''then''' выбрать случайную вершину <math>u \in D_i</math> и положить <math>D_i := D_i - \{ u \}</math>; | ||
7. положить | 7. положить <math>A_i := A_{i - 1} - D_i</math>; | ||
8. end | 8. '''end''' | ||
9. output | 9. '''output''' <math>A_m</math>; | ||
Следующая теорема рассматривает мощность независимого множества, вычисляемого алгоритмом. При анализе алгоритма используются уравнение Вальда (см. [ ]) для сумм случайного количества случайных переменных, позволяющее вычислить среднее значение | Следующая теорема рассматривает мощность независимого множества, вычисляемого алгоритмом. При анализе алгоритма используются уравнение Вальда (см. [9]) для сумм случайного количества случайных переменных, позволяющее вычислить среднее значение <math>|A_m|</math>, и границы Чернова (см, например, [6]) для концентрации вокруг среднего значения. | ||