Аннотация:
Дистанционным графом $G(n,2,1)$ называется граф, вершины которого отождествляются с двухэлементными подмножествами множества $\{1,2,\dots,n\}$, а ребро между вершинами проведено в том случае, если соответствующие подмножества имеют ровно один общий элемент. Случайный подграф $G_p(n,2,1)$ в модели Эрдеша–Реньи получается включением каждого ребра графа $G(n,2,1)$ с вероятностью $p$ независимо от остальных ребер. Найдена нижняя оценка числа независимости случайного подграфа $G_{1/2}(n,2,1)$.
УДК:
621.391.1+519.1
Поступила в редакцию: 25.02.2017 После переработки: 04.05.2017