2
$\begingroup$

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$.

The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex while every other layer contains exactly $M$ vertices. Vertices are numbered independently in each layer by integers from 0 to M - 1. For each pair of vertices which are in the adjacent layers ($i$ and $i + 1$ for any $i$ ($0 <= i <= n$)), there exists an edge. The vertex which is in the layer with smaller number is the initial vertex for such edge and the other one is the terminal vertex.

So the graph initially is something like this :

Let us assume N = 4 And M=3

enter image description here

Here A node is in layer 0 and N th node is in layer N+1 that is 5

Layer 1 has nodes = {B,C,D}
Layer 2 has nodes = {E,F,G}
Layer 3 has nodes = {H,I,J}
Layer 4 has nodes = {K,L,M}

Now we know that number of paths to go from A(that is first layer) to N(that is last layer) is $M^N$

Now suppose we add K more edges. Each edge connects two vertices which are in the different layers, no matter the adjacent layers or not. Also, each edge is directed from left to right (as well as all previously existing edges).

Like say we add an edge between Layer 1 Node 3 that is D to Layer 3 Node 3 that is J then graph look like this :

enter image description here

How many ways are there to reach from leftmost layer(0) to the rightmost layer(N+1) after adding these K edges ?

Note : Two paths are considered different if there is, at least, one edge which belongs to exactly one path. However, we are allowed to traverse the same set of vertices. In that case, there should be a multiple edge in the graph. It is also possible if some edge added connects two adjacent layers.

For example : It can also be like this :

enter image description here

In this case both edges are considered as different . So we need to count these total ways.

My Attempt : I know that if suppose we add a single edge between layers at A from start and B from end then it introduces M^(A-1)*M^(N-B) new paths. But problem arise when their are other edges added after that edge.

Example : Let N=4 , M=2 and K=2

There are 16 ways to get from the layer #0 to the layer #5. Now we have added edges.

Let first edge added is between (Layer 2,Node 1) to (Layer 5,Node 0) then there are 2 ways to get from the layer #0 to the layer #5 using this edge (0, 0 -> 1, 0 -> 2, 1 -> 5, 0 and 0, 0 -> 1, 1 -> 2, 1 -> 5, 0)

Let second edge added is between (Layer 0,Node 0) to (Layer 4,Node 0) then there is 1 way to get from the layer #0 to the layer #5 using this edge (0, 0 -> 4, 0 -> 5, 0)

So total is 16+2+1=19 ways

Edit : To make question precise we can assume that we are given N , M and K

Also then we are given K extra edges. Each edge is of form Layer1 , Node1 , Layer2 , Node 2 which shows that a edge between Node 1 of Layer 1 is directed toward Layer 2 Node 2.

How many paths are their now to reach last layer from starting layer ?

$\endgroup$
  • $\begingroup$ Um, where is the question here? $\endgroup$ – Henning Makholm Feb 10 '15 at 11:55
  • 1
    $\begingroup$ @HenningMakholm Question is we need to count number of ways to reach last layer from 0th layer if we are provided K new edges where each edge is of type L1 N1 L2 N2 that connects (Layer 1 , Node 1) to (Layer 2, Node 2 ) $\endgroup$ – user3786422 Feb 10 '15 at 12:19
  • 1
    $\begingroup$ That doesn't sound like a question. It doesn't even have a question mark anywhere. What are you asking? $\endgroup$ – Henning Makholm Feb 10 '15 at 14:15
  • 1
    $\begingroup$ @HenningMakholm I am not getting what problem are you facing in understanding it $\endgroup$ – user3786422 Feb 10 '15 at 16:23
  • 3
    $\begingroup$ @user3786422: Presumably you’re asking for a general result giving the number of paths when some edges are added. Unfortunately, the question doesn’t seem to be well-posed: the answer appears to depend very strongly on just what edges are added. $\endgroup$ – Brian M. Scott Feb 10 '15 at 18:41
1
$\begingroup$

As stated in the comments, the answer depends on which edges are added.

However, I think this will help you in what you are doing:

Compute the adjacency matrix $A$ of your graph. The entry $a_{i,j}$ is 1 if there is an edge from vertex $i$ to vertex $j$. The magic comes when you compute a power of the matrix. The $(i,j)$-th entry of $A^n$ counts how many paths go from vertex $i$ to vertex $j$ in exactly $n$ steps. For your problem, you need to compute $A^{N+1}$, because that is the number of steps needed to reach from the left vertex all the way to the right.

$\endgroup$
  • 1
    $\begingroup$ Except with added edges the number of steps is less than $N+1$ for some paths. So you would need to compute $A^2$ and $A^3$ and so on, adding the corresponding entry as you go. Not to mention that this will take $\mathcal{O}((NM)^4)$ time to compute. A better computational approach is to simply iterate through the graph one layer at a time (or any topological order) and just sum the number of paths from each parent. $\mathcal{O}(NM^2 + K)$. $\endgroup$ – Andrew Szymczak Feb 11 '15 at 15:21

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.