Независимые множества в случайных графах пересечений: различия между версиями

Один из трех предложенных в работе [7] алгоритмов приведен далее. Алгоритм начинает работу с V (т. е. множества всех вершин графа) в качестве «кандидата» на роль независимого множества. На каждом последующем шаге он выбирает метку и удаляет из текущего кандидата на роль независимого множества все вершины, содержащие эту метку в назначенном им множестве меток, кроме одной. В силу правила вхождения ребер этот подход гарантирует, что после выполнения этой операции для всех меток множества M финальный кандидат на роль независимого множества будет содержать только вершины, не имеющие ребер между ними, и потому по определению будет являться независимым множеством.

   4. выбрать случайную метку <math>l_i \in L</math>; положить <math>L := L - \{ l_i \}</math>;

   5. положить <math>D_i := \{ v \in A_{i - 1} : l_i \in S_v \}</math>;

   6. '''if''' <math>(|D_i| \ge 1)</math> '''then''' выбрать случайную вершину <math>u \in D_i</math> и положить <math>D_i := D_i - \{ u \}</math>;

   7. положить <math>A_i := A_{i - 1} - D_i</math>;

Следующая теорема рассматривает мощность независимого множества, вычисляемого алгоритмом. При анализе алгоритма используются уравнение Вальда (см. [9]) для сумм случайного количества случайных переменных, позволяющее вычислить среднее значение <math>|A_m|</math>, и границы Чернова (см, например, [6]) для концентрации вокруг среднего значения.