Ответом будет не алгоритм, а формула, но все же это вроде бы по теме.Есть N вершин. Генерируем V случайных (но разных) ребер. Сколько в среднем будет компонент связности у полученного графа? Принимаются не только точные формулы, но и ссылки, относительно грубые оценки и т.п..
7:54p
Еще одна интересная задачка.Есть здоровое множество M={x1,..,xm} и функция f: M*M->{0,1}, которая говорит, похожи 2 элемента или нет.Надо разбить множество на минимальное количество подмножеств из попарно похожих элементов.Т.е. разбить граф по вершинам на наименьшее количество клик :) Понятно что поиск наибольшоей клики - NP-полон, но вдруг эта задача решается другим способом... Во всяком случае, жадный алгоритм, использующий поиск наибольшей клики - не прокатывает.