Случайное минимальное остовное дерево
В математике случайное минимальное остовное дерево может быть сформировано путем присвоения независимых случайных весов из некоторого распределения ребрам неориентированного графа , а затем построения минимального остовного дерева графа.
Когда данный граф представляет собой полный граф на n вершинах, а веса ребер имеют непрерывную функцию распределения , производная которой в нуле равна D > 0 , тогда ожидаемый вес его случайных минимальных остовных деревьев ограничен константой, а не растет как функция n . Точнее, эта константа стремится в пределе (при стремлении n к бесконечности) к ζ (3)/ D , где ζ — дзета-функция Римана , а ζ (3) ≈ 1,202 — константа Апери . Например, для весов ребер, которые равномерно распределены на единичном интервале , производная равна D = 1 , а предел равен всего лишь ζ (3) . [ 1 ] Для других графов ожидаемый вес случайного минимального остовного дерева можно рассчитать как интеграл, включающий полином Тутте графа. [ 2 ]
В отличие от равномерно случайных остовных деревьев которых полных графов, типичный диаметр пропорционален квадратному корню из числа вершин, случайные минимальные остовные деревья полных графов имеют типичный диаметр, пропорциональный кубическому корню. [ 3 ] [ 4 ]
Случайные минимальные остовные деревья сеточных графов могут использоваться для моделей проникновения перколяции потока жидкости через пористую среду. [ 5 ] и для генерации лабиринта . [ 6 ]
Ссылки
[ редактировать ]- ^ Фриз, AM (1985), «О значении случайной задачи о минимальном остовном дереве», Discrete Applied Mathematics , 10 (1): 47–56, doi : 10.1016/0166-218X(85)90058-7 , MR 0770868
- ^ Стил, Дж. Майкл (2002), «Минимальные остовные деревья для графов со случайной длиной ребер», у Шовена, Бриджит; Флажоле, Филипп; Гарди, Даниэль; Моккадем, Абделькадер (ред.), Математика и информатика II: алгоритмы, деревья, комбинаторика и вероятности, материалы 2-го коллоквиума, Версаль-Сен-Кантен, Франция, 16–19 сентября 2002 г. , Тенденции в математике, Базель: Биркхойзер, стр. 223–245, doi. : 10.1007/978-3-0348-8211-8_14
- ^ Гольдшмидт, Кристина , Случайные минимальные остовные деревья , Математический институт Оксфордского университета , получено 13 сентября 2019 г.
- ^ Аддарио-Берри, Луиджи; Броутен, Николя; Гольдшмидт, Кристина; Мьермон, Грегори (2017), «Предел масштабирования минимального остовного дерева полного графа», Annals of Probability , 45 (5): 3075–3144, arXiv : 1301.1664 , doi : 10.1214/16-AOP1132
- ^ Даксбери, премьер-министр; Добрин Р.; МакГаррити, Э.; Мейнке, Дж. Х.; Донев, А.; Мусольф, К.; Холм, Е.А. (2004), «Сетевые алгоритмы и критические многообразия в неупорядоченных системах», Компьютерное моделирование в области физики конденсированного состояния XVI: материалы пятнадцатого семинара, Афины, Джорджия, США, 24–28 февраля 2003 г. , Springer Proceedings в Физика, вып. 95, Springer-Verlag, стр. 181–194, номер документа : 10.1007/978-3-642-59293-5_25 .
- ^ Фолтин, Мартин (2011), Автоматизированное создание лабиринтов и взаимодействие с людьми (PDF) , Дипломная работа, Брно: Университет Масарика, факультет информатики .
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |