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

Совокупность M иногда называется ''множеством меток'', а ее элементы – ''метками''. Обозначим за <mathL_l</math> для <math>l \in M</math> множество вершин, выбравших метку l.

В силу зависимостей от ребер эта модель способна более точно (по сравнению с моделью случайных графов Бернулли <math>G_{n,p}</math>, предполагающей независимость от ребер) абстрагировать многие практические задачи. Кроме того, Филл, Шайнерманн и Сингер-Коэн в работе [3] показали, что для некоторых диапазонов параметров n; m;p (m = na, a > 6) пространства <math>G_{n, m, p}</math> и <math>G_{n,p} \;</math> являются эквивалентными в том смысле, что суммарное вариационное расстояние между переменными случайного графа имеет предел, равный 0. Николетсис, Раптопулос и Спиракис [ ] предложили две новых модели, а именно модель случайных графов пересечений общего вида Gn m *,p = [p1; p2; pm] и модель регулярных случайных графов пересечений Gn^m^,X > 0, использующих различные способы случайного присвоения меток вершинам, но применяющих одно и то же правило вхождения ребер. Модель Gn m -i является обобщением равномерной модели, в котором каждая метка i 2 M выбирается независимо с вероятностью pi, тогда как в модели С "тд каждая вершина выбирает случайное подмножество M, содержащее в точности A меток.

Авторы в работе [ ] сначала рассматривают существование независимых множеств вершин заданной мощности в случайных графах пересечений общего вида и приводят точные формулы для среднего значения и дисперсии числа независимых множеств вершин мощности k. Кроме того, они представляют и анализируют три алгоритма с полиномиальным временем выполнения (от числа меток m и от числа вершин n) для построения больших независимых множеств вершин в случае, когда входным значением является экземпляр модели <math>G_{n,m,p} \;</math>. В данной работе впервые были рассмотрены алгоритмические вопросы для этих моделей случайных графов.