Создание всех сильно связанных графов с заданной степенью с равной вероятностью

Я ищу способ выборки равномерно из пространства всех строго связанных ориентированных графиков (без самообучений) узлов n и в градусах k=(k_1,...,k_n), 1 <= k_i <= n-1.

Ввод

  • n, количество узлов
  • k = (k_1,...,k_n), где k_i = количество направленных ребер, которые вводят node i (в градусах)

Выход

  • сильно связанный ориентированный граф узлов n (без самопроверки) с заданными в градусах k_1,...,k_n, где каждый возможный такой граф возвращается с вероятностью той же.

Меня особенно интересуют случаи, когда n велико, а k_i мало, поэтому простое создание графика и проверка на сильную связность неосуществимы, потому что вероятность по существу равна нулю.

Я просмотрел всевозможные документы и методы, но не смог найти ничего, что касалось этой проблемы.

Ответы

Ответ 1

Продолжайте создавать случайный путь до тех пор, пока не появится цикл:

node1- > node2- > node3...- > nodek- > noder где r <= k

Теперь замените цикл noder- > noder + 1- > nodek блобом и назовем его blobr. Теперь продолжайте подключать его к остальным узлам (таким образом, чтобы узлы не находились в этом блобе). Каждый раз, когда вы нажимаете на цикл, просто создавайте больший кадр.

В конечном итоге это создаст случайный минимально сильный направленный граф. Затем добавьте случайные ребра для выполнения входящих критериев.

Это, безусловно, создаст все комбинации ваших требований. Я думаю, что все комбинации одинаково вероятны, но я должен думать больше.

Алгоритм: Это примерная схема. Я на самом деле не оставляю здесь структуру графа и не рассматриваю граничные условия, но это должно быть довольно неудобно.

function randomStrongGraph(list<set<node>> chain, set<node> allnodes)
    Node newnode = random(allnodes - head(chain))
    alreadyEncountered = false
    for (i=0,i<chain.length-1;i++)
        if (newnode in chain(i))
            consolidate(chain, i)
            alreadyEncountered = true
            break
    if !alreadyEncountered
        chain.append(new set().add(newnode))    
    randomStrongGraph(chain, allnodes)