patternMinor
The Number of Paths in a Directed Graph
Viewed 0 times
numberthegraphpathsdirected
Problem
Suppose I have a directed graph $G = (V,E)$. Suppose that $v_1$ and $v_2$ are two nodes in the graph. Am I correct the number of simple paths (that is, it has no cycles) from $v_1$ to $v_2$ is $O(E)$? Is it true for the special case of directed acyclic graphs?
Bob
Bob
Solution
That's not true even for DAGs: consider the following, with all edges directed left-to-right:
There are $2^{|E|/4}$ paths from $x$ to $y$. In a graph with cycles, it can be even worse: consider a clique.
o o o ... o
/ \ / \ / \
x o o ... y
\ / \ / \ /
o o o ... oThere are $2^{|E|/4}$ paths from $x$ to $y$. In a graph with cycles, it can be even worse: consider a clique.
Code Snippets
o o o ... o
/ \ / \ / \
x o o ... y
\ / \ / \ /
o o o ... oContext
StackExchange Computer Science Q#88844, answer score: 3
Revisions (0)
No revisions yet.