О наибольшей длине пути в одном классе направленных графов.
1892-е заседание.
-
С. Г. Фосс
О наибольшей длине пути в одном классе направленных графов.
Рассматривается граф с 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 существует (по крайней мере, по вероятности). Мы обсудим некоторые его занимательные свойства.
Источник: Объединенный семинар «Вероятность и математическая статистика»