Имеет ли граф, представленный матрицей смежности, хотя бы одно связующее дерево?

Question

Я путешествую по математике и алгоритмам уже два дня, но у меня нет больше идей. У меня есть матрица смежности, и у меня есть матрица Лапласяна. Я хочу проверить, является ли этот график согласованным, ИЛИ есть ли у него связующее дерево.

Я работал с теоремой Кирхгофа, и она работает для меня, но она слишком медленная (более секунды с матрицей 10x10). Могу ли я изменить теорему Кирхгофа, чтобы проверить, имеет ли мое матричное остовное дерево (НЕ сколько)?

Я пытаюсь узнать что-то новое, поэтому я не хочу использовать DFS и действительно хочу использовать матрицу смежности.

Answer 1

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

• Мы представляем связующее дерево как массив 'par', где каждый узел указывает на своего родителя в tree.
• 'par' инициализируется, когда все узлы имеют себя в качестве родителя.
• У нас есть функция find_root, которая следует за цепочкой указателей 'par', пока не достигнет узла, для которого par[node] == node
• Мы пропустим oop по всем ссылкам; в прямой матрице смежности это будет: for i in nodes: for j in nodes: if i!=j: if adjacent[i][j] then:
  • k = find_root(i)
  • `l = find_ root (j)
  • par[k] = l // это помещает дерево i как родного брата в j в дереве j
  • в конце, мы проверяем, есть ли у каждого узла одинаковые root

Таким образом, создается одно или несколько деревьев. Эти деревья можно использовать для кластеризации узлов в связанные группы.

Для алгоритма basi c важным ускорением является не только установка par[k] = l, но также par[i] = l и par[j] = l. root будет найден ранее в следующий раз. Если график не направленный, необходимо обработать только один из adjacent[i][j] или adjacent[j][i].