Подсчет количества посещений ребра в минимальном остовном дереве для всех путей от вершины u до v, где u! = V - PullRequest
Новая
       9

Подсчет количества посещений ребра в минимальном остовном дереве для всех путей от вершины u до v, где u! = V

0 голосов
/ 05 февраля 2019

С учетом MST-поиска для всех путей, начиная с u и заканчивая v , где u! = V, сколько раз проходилось каждое ребро в графе. Например, ребро AC в графе может быть пройдено при достижении от A до C или от A до B, где C может лежать на пути от A к B. Следовательно, AC пересекается дважды. Нам нужно посчитать всеобходы для каждого ребра в графе.Кто-нибудь может мне помочь с алгоритмом?

1 Ответ

0 голосов
/ 05 февраля 2019

Учитывая минимальное остовное дерево M = { V , E } и ребро (i,j), пусть L = { V L , E L } и R = { V R , E R } - два подграфа (дерева), созданные путем удаления ребра (i,j) из M .Край (i,j) будет пересекаться только путями (u,v), где u находится в L , а v находится в R (или наоборот).Поскольку все вершины в L связаны со всеми вершинами в R , а все пути от вершины u до вершины v являются уникальными, число раз, когда ребро (i,j) равноперечеркнуто: | V L | × | V R |.

Найти количество вершин на одномна стороне каждого ребра все, что требуется, - это один обход в глубину, начинающийся с произвольного узла, возвращающий nodeCount, который является суммой nodeCount для каждого дочернего элемента + 1 для текущего узла.Следовательно, nodeCount для конечных узлов равно 1.

Родительская вершина удаляется из списка смежности, переданного в рекурсивных вызовах ее дочерних узлов, чтобы узлы не учитывались несколько раз.

Таким образом, если мы достигли вершины p из вершины R , как показано в этом подграфе, 

        R
        |
        |
        p
       / \
      /   \
     c1   c2

nodeCount, возвращенный в R , будетбыть 1 + nodeCount(c1) + nodeCount(c2).Если оба c1 и c2 являются конечными узлами, возвращаемое значение nodeCount будет равно 3.

В конце этого процесса каждое из значений nodeCountвозвращается число узлов на стороне одна соответствующего ребра.Число узлов на другой стороне этого ребра будет определяться как N - nodeCount, где N - количество вершин в MST.Число путей через этот край будет 

nodeCount * (N - nodeCount)

Вот некоторый псевдокод, который, надеюсь, немного прояснит ситуацию: 

CountNodes(A, r)
   // Given adjacency matrix A, returns the number of nodes 
   // reachable from node r (including r itself)
   nodeCount = 1   // include root node in count

   // rows/columns in A for visited nodes should be all 0
   // so that we don't count this node multiple times
   // update node r as visited before recursive call to CountNodes
   A[r,] = 0
   A[,r] = 0

   if the number of unvisited children of r is 0
      return nodeCount   // r is a leaf, nodeCount = 1
   end if

   for each  node c connected to r
      // get count of nodes in subtree rooted at c
      childCount = CountNodes(A, c)
      PRINT (r,c) = childCount   // display count for current edge 
      nodeCount = nodeCount + childCount   // update count to report to parent
   end for
   return nodeCount

end CountNodes

Как я уже сказал, для начального вызова мы используем произвольныйузел.Неважно, какой из них мы используем, так как все ответы будут эквивалентны (правильный счет с одной стороны каждого края, хотя не обязательно с той же стороной).При первоначальном вызове неявно генерируется фиктивная вершина в качестве родителя первого узла, поэтому nodeCount, возвращаемое в конце, равно N , числу вершин в MST.

Вот примерная матрица смежности для 10 вершин и вывод из функции при запуске с вершины 0: 

A =
   0  1  0  0  0  0  0  0  0  0
   1  0  0  0  1  0  0  0  0  0
   0  0  0  0  0  0  0  0  1  0
   0  0  0  0  0  0  1  0  0  0
   0  1  0  0  0  0  0  1  0  0
   0  0  0  0  0  0  0  0  1  1
   0  0  0  1  0  0  0  1  1  0
   0  0  0  0  1  0  1  0  0  0
   0  0  1  0  0  1  1  0  0  0
   0  0  0  0  0  1  0  0  0  0

(6,3) = 1
(8,2) = 1
(5,9) = 1
(8,5) = 2
(6,8) = 4
(7,6) = 6
(4,7) = 7
(1,4) = 8
(0,1) = 9
return =  10

Поскольку nodeCount для ребра (6,8) равно 4, количество путей, проходящих через ребро(6,8) - это 4 * (10 - 4) = 24.Количество путей через ребро (0,1) будет 9

...