2
$\begingroup$

I have an undirected, unweighted graph representing a network. I have a starting node and an end one. My 'network' is reliable if there is no node such that without that node s and t are not reachable i.e. no node is necessary and all nodes have at least one redundant path.

how can I formally verify this? thank you

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "formally verify"? What do you mean that "all nodes have at least one redundant path"? $\endgroup$
    – Igor Rivin
    Sep 9, 2012 at 18:22
  • $\begingroup$ As stated by Igor, you want biconnectivity. A naive way to check this is to check, for each vertex $v$, that $G-v$ is connected. $\endgroup$
    – Andrew D. King
    Sep 10, 2012 at 20:25

2 Answers 2

Reset to default
4
$\begingroup$

If you mean that the network remains connected upon removing any one node, the magic words are "2-vertex-connected graph", or "biconnected graph". An algorithm for determining biconnectivity is described here, though I am sure there are plenty of other places.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Btw, the OP has stated (without proof) a special case of Menger's theorem. $\endgroup$
    – Felix Goldberg
    Sep 9, 2012 at 20:55
0
$\begingroup$

If you want to calculate number of paths from one node to another ,let say from s to t.then you can follow the following approach.

To reach a node t from s , you need to calculate that how many ways are there to reach t from its adjacent vertices . means PathsTo(s,t)=sum(PathsTo(s,u)) , where u are adjacents vertices of t.

as we can see there is a subproblem optimality and overlapping subproblems, so we can use a DP approach to do this in Linear time.

We can do this by modifying our DFS algorithm.

Psuedocode:

declare an array A of size |V| , memset it to NULL array represent , number of ways to reach a node v from s.

Paths(s,t):

if(s==t):

 return 1;

else:

 if(A[t]==NULL):
      A[t]=sum(Paths(s,u)) for all adjacent u of t
 else
      return A[t]

Time complexity is O(V+E) same as DFS.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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