#математическийанархизм
Сегодня я, как часто это делаю, вышел на утреннюю прогулку за кофе. Обычно именно во время таких прогулок я размышляю над тем, как математически устроена структура "идеального общества".
В этот раз я размышлял чисто над инженерной задачей - для проверки некоторых моих гипотез нужно научиться нормально сэмплировать связные графы. Первый запрос в гугле ответов особо не дал, поэтому я решил подумать сам, ибо зачем много на прогулке пялиться в телефон, если можно получить удовольствие от размышлений. Вот что у меня пока что получилось.
Одно из определений связного графа - существование остовного дерева. Соответственно, задача свелась к сэмплированию остовных деревьев + сэмплированию остальных ребер. Сэмплировать остальные ребра должно быть несложно, как мне кажется - с вероятностью p включать/не включать каждое из оставшихся ребер. При таком подходе у нас после полной генерации сэмплироваться будут не классы изоморфности графов, но кажется что это не такая большая проблема. А вот что по поводу деревьев...
Почесав репу, вспомнил, что дерево можно записать через последовательность предков, где у корневой вершины предка не будет. Но просто сэмплировать числовые последовательности кажется нельзя, так как тогда часть деревьев даже на пронумерованных вершинах могут получиться одинаковыми (не до конца уверен в этом утверждении, впрочем это и не суть важно). Идея: нулевая вершина - всегда корень, последняя вершина - всегда лист, и для iой вершины выбираем ее предка из вершин от 0 до (i-1). Такой подход точно захватит два краевых случая - дерево с диаметром 2 и с диаметром n-1.
Впрочем, это еще не конец, просто мысли по теме. Для моих целей надо понять, как дополнительно научиться сэмплировать графы с нужными мне спектральными свойствами (пока что оно только одно - количество остовных деревьев, второе свойство слишком нелинейное, мне кажется с ним не получится). Я хочу поизучать то как работает базис циклов и можно ли его применить для этой задачи.
Спасибо за внимание и то, что читаете мою шизу. Конструктивные предложения приветствуются, как и критика
