Случайные метрические графы
Вот вам для затравки небольшой сюжет, про теорему Фриза
https://www.sciencedirect.com/science/article/pii/0166218X85900587Я хз, можно ли его вывести из асимптотической теории, про которую написано ниже, но не удивлюсь, если так это и делается. Я вообще не знаю особо результатов из тервера, которые бы не доказывлись применением преобразования Лапласа/Фурье.
Рассмотрим полный граф на n вершинах и независимо припишем его ребрам случайные длины - из равномерного распределения на [0,1]. Тогда при n-->∞ длина минимального остовного дерева (MST) такого графа равна константе Апери ζ(3) (дзета-функции от 3, сумма обратных кубов натуральных чисел). Ну, более строгая формулировка, что для любого ε>0 вероятность того, что длина MST не лежит в интервале [ζ(3)-ε, ζ(3)+ε] стремится к нулю.
И так-то, когда в первый раз видишь эту теорему, думаешь, WTF? Если длина ребра в среднем равна 1/2, то казалось бы остовное дерево должно иметь длину что-то вроде n/2, почему она вообще констнанта.
Но тут, конечно, можно разобраться. У нас порядка n^2/2 ребер, случайно натыканных из отрезка. Ясно, что для минимального дерева нужно брать те ребра, которые покороче, их нужно n-1 штук. Но n самых коротких ребер будут кучковаться где-то в отрезке [0,1/n), поэтому сумма их длин получается порядка константы.
Отсюда неудивителен общий факт, доказанный Фризом. Условие, что длины ребер взяты из равномерного распределения - вообще не важно. Важно, что распределение длин F(x) удовлетворяет условию F'(0+0)=1. В общем случае (если F(0+0)=0), то длина MST равна ζ(3)*F'(0+0).
Таким образом, для глобального свойства - длины MST - важно только свойство распределения длин вблизи нуля. Как ведут себя длинные ребра - не важно, потому что они в MST просто не попадут.
То, что в пределе получается именно такая константа - безумно красивый результат, кмк. Довольно легко, кстати, прогается. Приятное поле для экспериментов.