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

Для доказательства теоремы 2 вначале запишем дисперсию в виде суммы ковариаций, а затем применим технику сжатия вершин, выполняющую слияние нескольких вершин в одну супер-вершину со схожим вероятностным поведением, для вычисления ковариаций. При помощи метода моментов второго порядка (см. [ 1 ]) можно вычислить порог для существования независимых множеств размера.

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

Дано: случайный граф пересечений <math>G_{n,m,p} \;</math>.

Требуется: найти независимое множество вершин Am.

   1. положить A0 := V; положить L := M;

   2. for i: = 1 to m do

   3. begin