С. Г. Фосс
О наибольшей длине пути в одном классе направленных графов.
Рассматривается граф с n вершинами, занумерованными числами от 1 до n, и содержащий все ребра из меньших вершин в большие.
Каждое ребро (независимо от других) с вероятностью p имеет длину 1 и с вероятностью 1-p длину x, где -\infty \le x \le 1.
Пусть L(x,p,n) - максимальная длина пути в этом графе (т.е. максимальная сумма длин по всем путям).
Предел C(x,p) = \lim L_{x,p,n}/n существует (по крайней мере, по вероятности). Мы обсудим некоторые его занимательные свойства.
