Найти все остовные деревья ориентированного взвешенного графа - PullRequest
1 голос
/ 08 ноября 2011

Я нашел эту бумагу до сих пор.Это устарело?Есть ли более быстрые и лучшие реализации?

Кстати, Википедия говорит, что в неориентированном графе может быть n ^ n-2 связующих деревьев.Сколько связующих деревьев может быть в ориентированном графе?

Ответы [ 2 ]

0 голосов
/ 04 апреля 2013

только для неориентированного графа ....

n ^ n-2 связующего дерева возможны только для полного графа .... чтобы найти общее число связующих деревьев любого графа, вы можете применить этот метод.....

  1. найти матрицу смежности графа.
  2. , если значения столбцов представлены 'i', а записи в строке 'j', то ...
  3. если i = j ..., то значение будет иметь степень вершины
  4. предположим, что между вершинами v1 и v2 есть единственное ребро, тогда значение входа в матрицу будет -1 ...... 7 если есть два ребра, тогда будет -2 ... и так далее ...
  5. после построения матрицы смежности .... исключить любую строку и столбец ... т.е. N-ую строкуи N-й столбец ....
  6. ответом будет общее количество связующих деревьев.
0 голосов
/ 09 ноября 2011

Если вы используете термины из упомянутой вами бумаги и определяете остовное дерево ориентированного графа как дерево с корнем в вершине r, имеющее уникальный путь от r до любой другой вершины, то:

Очевидно, что наихудший случай при направленномГраф имеет наибольшее количество связующих деревьев, является полным графом (для любой пары есть a-> b и b-> a ребра).Если мы «забудем» о направлениях, то получим n ^ {n-2} остовных деревьев, как в случае неориентированных графов.Для любого из этих связующих деревьев у нас есть n опций для выбора корня, и этот выбор однозначно определяет направления ребер, которые мы должны использовать.Нетрудно видеть, что все деревья, которые мы получаем, являются уникальными и не имеют никаких других вариантов.Таким образом, мы получаем n ^ {n-1} остовных деревьев.Строгое доказательство займет время, я надеюсь, что достаточно простого объяснения.

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

...