0
$\begingroup$

I have the following algorithm: Given a single sink, directed acyclic graph $D = (V, E)$,

  1. Associate each node $v \in V$ with a number $r(v) = n_v$

  2. Then, for each neighbor $v \in N^{+}(s)$ of each source node $s$, do $r(v) = r(v) + \displaystyle\sum_\limits{v \in N^{+}(s)}\frac{r(s)}{|N^{+}(s)|}$

  3. Remove each current source node, Repeat step 2 for the new source nodes. Terminate when the sink node is reached.

I am trying to prove that for the sink node $z$, $r(z) = \displaystyle\sum_{v \in V}n_{v}$

But I don't know where to start the proof. Any hint or advice?

$\endgroup$
0
$\begingroup$

I assume that for each vertex $v\in V$ we have $N^+(v)=\{u\in V: (v,u)\in E\}$.

It is natural to start from the beginning of the construction and follow it. We see that the sum $\sum r(v)$ at each step is constant. But at the first step it equals $\sum_{v\in V} n_v$, whereas at the last it equals $r(z)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.