воскресенье, 9 ноября 2014 г.

Количество компонент связности образующих элементарные циклы в случайном графе

Рассмотрим случайный обыкновенный граф на n вершинах в котором каждое ребро существует независимо от остальных с вероятностью p. Тогда для таких графов среднее количество subject'ов длины k>2 будет: