Случайное минимальное остовное дерево
В математике случайное минимальное остовное дерево может быть сформировано путем назначения независимых случайных весов из некоторого распределения ребрам неориентированного графа , а затем построения минимального остовного дерева графа.
Когда заданный граф является полным графом на n вершинах, а веса ребер имеют непрерывную функцию распределения , производная которой в нуле равна D > 0 , то ожидаемый вес его случайных минимальных остовных деревьев ограничен константой, а не растет как функция n . Точнее, эта константа стремится в пределе (по мере того, как n стремится к бесконечности) к ζ (3)/ D , где ζ — дзета-функция Римана , а ζ (3) ≈ 1,202 — константа Апери . Например, для весов ребер, равномерно распределенных на единичном интервале , производная равна D = 1 , а предел — просто ζ (3) . [1] Для других графов ожидаемый вес случайного минимального остовного дерева можно вычислить как интеграл, включающий полином Тутте графа. [2]
В отличие от равномерно случайных остовных деревьев полных графов, для которых типичный диаметр пропорционален квадратному корню из числа вершин, случайные минимальные остовные деревья полных графов имеют типичный диаметр, пропорциональный кубическому корню. [3] [4]
Случайные минимальные остовные деревья графов сетки могут использоваться для моделей проникновения и перколяции потока жидкости через пористую среду [5] и для генерации лабиринтов [6] .
Ссылки
- ^ Фризе, AM (1985), «О значении задачи случайного минимального остовного дерева», Дискретная прикладная математика , 10 (1): 47–56 , doi : 10.1016/0166-218X(85)90058-7 , MR 0770868
- ^ Стил, Дж. Майкл (2002), «Минимальные остовные деревья для графов со случайными длинами ребер», в Шовен, Брижит; Флажоле, Филипп ; Гарди, Даниэль; Моккадем, Абделькадер (ред.), Математика и информатика II: алгоритмы, деревья, комбинаторика и вероятности, Труды 2-го коллоквиума, Версаль-Сен-Кантен, Франция, 16–19 сентября 2002 г. , Тенденции в математике, Базель: Birkhäuser, стр. 223–245 , doi :10.1007/978-3-0348-8211-8_14, ISBN 978-3-0348-9475-3
- ^ Гольдшмидт, Кристина , Случайные минимальные остовные деревья, Математический институт, Оксфордский университет , получено 13 сентября 2019 г.
- ^ Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina ; Miermont, Gregory (2017), «Предел масштабирования минимального остовного дерева полного графа», Annals of Probability , 45 (5): 3075–3144 , arXiv : 1301.1664 , doi : 10.1214/16-AOP1132
- ^ Duxbury, PM; Dobrin, R.; McGarrity, E.; Meinke, JH; Donev, A.; Musolff, C.; Holm, EA (2004), "Сетевые алгоритмы и критические многообразия в неупорядоченных системах", Computer Simulation Studies in Condensed-Matter Physics XVI: Proceedings of the Fifteenth Workshop, Athens, GA, USA, February 24–28, 2003 , Springer Proceedings in Physics, vol. 95, Springer-Verlag, pp. 181–194 , doi :10.1007/978-3-642-59293-5_25, ISBN 978-3-642-63923-4.
- ^ Фолтин, Мартин (2011), Автоматизированная генерация лабиринтов и взаимодействие с человеком (PDF) , Дипломная работа, Брно: Университет Масарика, Факультет информатики.
 | Эта статья по теории графов — заглушка . Вы можете помочь Википедии, расширив ее. |
