Mixing
For each edge in a tree, counting paths passing through this edge
$begingroup$
I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (4,6)] Number of paths for each edge:
(1,2)-> 5
(2,3)-> 5
(2,4)-> 9
(4,5)-> 5
(4,6)-> 5
I am not able to think of any algorithm other than brute force (enumerating all paths of tree).
Please provide any linear/quadratic method.
combinatorics algorithms trees
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
$endgroup$
add a comment |
$begingroup$
I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (4,6)] Number of paths for each edge:
(1,2)-> 5
(2,3)-> 5
(2,4)-> 9
(4,5)-> 5
(4,6)-> 5
I am not able to think of any algorithm other than brute force (enumerating all paths of tree).
Please provide any linear/quadratic method.
combinatorics algorithms trees
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
$endgroup$
1
$begingroup$
Shouldn't there be 8 paths including ${4,5}$? Namely one for each combination of "vertex on one side of the chosen edge" (1,2,3, or 4) and "vertex on the other side of the chosen edge" (5 or 6).
$endgroup$
– Henning Makholm
Aug 5 '18 at 5:23
$begingroup$
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
$endgroup$
– Sushil Verma
Aug 5 '18 at 7:26
add a comment |
$begingroup$
I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (4,6)] Number of paths for each edge:
(1,2)-> 5
(2,3)-> 5
(2,4)-> 9
(4,5)-> 5
(4,6)-> 5
I am not able to think of any algorithm other than brute force (enumerating all paths of tree).
Please provide any linear/quadratic method.
combinatorics algorithms trees
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
$endgroup$
I have a tree and for its each edge, I want to know the numbers paths passing through this edge.
For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (4,6)] Number of paths for each edge:
(1,2)-> 5
(2,3)-> 5
(2,4)-> 9
(4,5)-> 5
(4,6)-> 5
I am not able to think of any algorithm other than brute force (enumerating all paths of tree).
Please provide any linear/quadratic method.
combinatorics algorithms trees
combinatorics algorithms trees
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
edited Aug 5 '18 at 7:25
Sushil Verma
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
asked Aug 5 '18 at 5:08
Sushil VermaSushil Verma
406
406
1
$begingroup$
Shouldn't there be 8 paths including ${4,5}$? Namely one for each combination of "vertex on one side of the chosen edge" (1,2,3, or 4) and "vertex on the other side of the chosen edge" (5 or 6).
$endgroup$
– Henning Makholm
Aug 5 '18 at 5:23
$begingroup$
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
$endgroup$
– Sushil Verma
Aug 5 '18 at 7:26
add a comment |
1
$begingroup$
Shouldn't there be 8 paths including ${4,5}$? Namely one for each combination of "vertex on one side of the chosen edge" (1,2,3, or 4) and "vertex on the other side of the chosen edge" (5 or 6).
$endgroup$
– Henning Makholm
Aug 5 '18 at 5:23
$begingroup$
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
$endgroup$
– Sushil Verma
Aug 5 '18 at 7:26
1
1
$begingroup$
Shouldn't there be 8 paths including ${4,5}$? Namely one for each combination of "vertex on one side of the chosen edge" (1,2,3, or 4) and "vertex on the other side of the chosen edge" (5 or 6).
$endgroup$
– Henning Makholm
Aug 5 '18 at 5:23
$begingroup$
Shouldn't there be 8 paths including ${4,5}$? Namely one for each combination of "vertex on one side of the chosen edge" (1,2,3, or 4) and "vertex on the other side of the chosen edge" (5 or 6).
$endgroup$
– Henning Makholm
Aug 5 '18 at 5:23
$begingroup$
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
$endgroup$
– Sushil Verma
Aug 5 '18 at 7:26
$begingroup$
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
$endgroup$
– Sushil Verma
Aug 5 '18 at 7:26
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The answer mentioned above is $mathcal{O}(N)$ for ONE edge but doing it for each one will make it $O(N^2)$.
Although we can compute the answer in O(N) total for all the edges.
I've added pseudocode for the algorithm at the end.
Steps:
1) As we have a tree, we can root it at some node, say node 1.
2) Run a dfs and compute an array subtreeSize, where subtreeSize[i] gives the size of the subtree rooted at node i,(Subtree of a node x contains node x as well as all those nodes which passes through x to reach the root in shortest path).
[I've added the pseudocode for computing subtreeSize array at the end]
3) Now that we have this array computed, for each edge {u,v} we know for sure either of these is a parent and other is the child. Lets say u is parent and v is its child. Now let A = subtreeSize[v], then answer for this edge will be (N - A) * (A).
Why? Because we have these two sets of nodes, lets say we remove the {u,v} edge then the we'll get 2 trees, say all nodes in u side are in set X and all nodes in v side are in set Y. Then we can see that for each node in set X we can make a path to each node in set Y that crosses the {u,v} edge. So total number of paths will be = |X| * |Y|, (|setS| = size of setS). You can achieve this whole step in the same dfs if you notice closely whie computing subtreeSize
pseudocode for the complete O(N) algorithm:
dfs(node, parent):
subtreeSize[node] = 1
for each child c of node do:
dfs(c, node)
subtreeSize[node] = subtreeSize[node] + subtreeSize[c]
answerForEdge[node and parent] = (N - subtreeSize[node])*(subtreeSize[node]) // N is the total number of nodes
return
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
$endgroup$
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
add a comment |
$begingroup$
If the edge is, say, {u,v}, it seems to me that you should be able to do a BFS from u (not including v) and a BFS from v (not including u).
From the BFS from u (omitting v), count the number of vertices you visit and add one to it (for u). This should be the number of paths leading to the u end of the edge (including the trivial path of just starting at u). Call this n(u).
Do the same thing from v (omitting u): count the number of vertices you visit and add one to it (for v). This will be the number of paths leading to the v end of the edge (including the trivial path of starting at v). Call this n(v).
Then you can simply multiply these together to get all the paths passing through edge {u,v}: the product is basically picking a path to u (of which there are n(u) such paths) and then picking a path to v (of which there are n(v) such paths).
BFS, on a tree, runs in O(V), where V is the number of nodes in the tree, so two BFS algorithms also run in time O(V) as well: thus, the algorithm is linear in the number of vertices. Indeed, since the double BFS visits every vertex exactly once, it can be done in V steps precisely.
You'll note that this works with your example: for instance, if we take {2,4}, starting a BFS at 2 gives us 2 vertices, namely 1 and 3, so:
n(2) = 2 + 1 = 3.
(Remember we add 1 for vertex 2 itself.)
Then, starting a BFS at 4 also gives us 2 vertices, namely 5 and 6, so:
n(4) = 2 + 1 = 3
(Remember that we add 1 for vertex 4 itself.)
Thus, the total number of paths through edge {2,4} is:
n(2) * n(4) = 3 * 3 = 9.
answered Aug 5 '18 at 11:51
vorpalvorpal
113
$endgroup$
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872647%2ffor-each-edge-in-a-tree-counting-paths-passing-through-this-edge%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The answer mentioned above is $mathcal{O}(N)$ for ONE edge but doing it for each one will make it $O(N^2)$.
Although we can compute the answer in O(N) total for all the edges.
I've added pseudocode for the algorithm at the end.
Steps:
1) As we have a tree, we can root it at some node, say node 1.
2) Run a dfs and compute an array subtreeSize, where subtreeSize[i] gives the size of the subtree rooted at node i,(Subtree of a node x contains node x as well as all those nodes which passes through x to reach the root in shortest path).
[I've added the pseudocode for computing subtreeSize array at the end]
3) Now that we have this array computed, for each edge {u,v} we know for sure either of these is a parent and other is the child. Lets say u is parent and v is its child. Now let A = subtreeSize[v], then answer for this edge will be (N - A) * (A).
Why? Because we have these two sets of nodes, lets say we remove the {u,v} edge then the we'll get 2 trees, say all nodes in u side are in set X and all nodes in v side are in set Y. Then we can see that for each node in set X we can make a path to each node in set Y that crosses the {u,v} edge. So total number of paths will be = |X| * |Y|, (|setS| = size of setS). You can achieve this whole step in the same dfs if you notice closely whie computing subtreeSize
pseudocode for the complete O(N) algorithm:
dfs(node, parent):
subtreeSize[node] = 1
for each child c of node do:
dfs(c, node)
subtreeSize[node] = subtreeSize[node] + subtreeSize[c]
answerForEdge[node and parent] = (N - subtreeSize[node])*(subtreeSize[node]) // N is the total number of nodes
return
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
$endgroup$
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
add a comment |
$begingroup$
The answer mentioned above is $mathcal{O}(N)$ for ONE edge but doing it for each one will make it $O(N^2)$.
Although we can compute the answer in O(N) total for all the edges.
I've added pseudocode for the algorithm at the end.
Steps:
1) As we have a tree, we can root it at some node, say node 1.
2) Run a dfs and compute an array subtreeSize, where subtreeSize[i] gives the size of the subtree rooted at node i,(Subtree of a node x contains node x as well as all those nodes which passes through x to reach the root in shortest path).
[I've added the pseudocode for computing subtreeSize array at the end]
3) Now that we have this array computed, for each edge {u,v} we know for sure either of these is a parent and other is the child. Lets say u is parent and v is its child. Now let A = subtreeSize[v], then answer for this edge will be (N - A) * (A).
Why? Because we have these two sets of nodes, lets say we remove the {u,v} edge then the we'll get 2 trees, say all nodes in u side are in set X and all nodes in v side are in set Y. Then we can see that for each node in set X we can make a path to each node in set Y that crosses the {u,v} edge. So total number of paths will be = |X| * |Y|, (|setS| = size of setS). You can achieve this whole step in the same dfs if you notice closely whie computing subtreeSize
pseudocode for the complete O(N) algorithm:
dfs(node, parent):
subtreeSize[node] = 1
for each child c of node do:
dfs(c, node)
subtreeSize[node] = subtreeSize[node] + subtreeSize[c]
answerForEdge[node and parent] = (N - subtreeSize[node])*(subtreeSize[node]) // N is the total number of nodes
return
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
$endgroup$
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
add a comment |
$begingroup$
The answer mentioned above is $mathcal{O}(N)$ for ONE edge but doing it for each one will make it $O(N^2)$.
Although we can compute the answer in O(N) total for all the edges.
I've added pseudocode for the algorithm at the end.
Steps:
1) As we have a tree, we can root it at some node, say node 1.
2) Run a dfs and compute an array subtreeSize, where subtreeSize[i] gives the size of the subtree rooted at node i,(Subtree of a node x contains node x as well as all those nodes which passes through x to reach the root in shortest path).
[I've added the pseudocode for computing subtreeSize array at the end]
3) Now that we have this array computed, for each edge {u,v} we know for sure either of these is a parent and other is the child. Lets say u is parent and v is its child. Now let A = subtreeSize[v], then answer for this edge will be (N - A) * (A).
Why? Because we have these two sets of nodes, lets say we remove the {u,v} edge then the we'll get 2 trees, say all nodes in u side are in set X and all nodes in v side are in set Y. Then we can see that for each node in set X we can make a path to each node in set Y that crosses the {u,v} edge. So total number of paths will be = |X| * |Y|, (|setS| = size of setS). You can achieve this whole step in the same dfs if you notice closely whie computing subtreeSize
pseudocode for the complete O(N) algorithm:
dfs(node, parent):
subtreeSize[node] = 1
for each child c of node do:
dfs(c, node)
subtreeSize[node] = subtreeSize[node] + subtreeSize[c]
answerForEdge[node and parent] = (N - subtreeSize[node])*(subtreeSize[node]) // N is the total number of nodes
return
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
$endgroup$
The answer mentioned above is $mathcal{O}(N)$ for ONE edge but doing it for each one will make it $O(N^2)$.
Although we can compute the answer in O(N) total for all the edges.
I've added pseudocode for the algorithm at the end.
Steps:
1) As we have a tree, we can root it at some node, say node 1.
2) Run a dfs and compute an array subtreeSize, where subtreeSize[i] gives the size of the subtree rooted at node i,(Subtree of a node x contains node x as well as all those nodes which passes through x to reach the root in shortest path).
[I've added the pseudocode for computing subtreeSize array at the end]
3) Now that we have this array computed, for each edge {u,v} we know for sure either of these is a parent and other is the child. Lets say u is parent and v is its child. Now let A = subtreeSize[v], then answer for this edge will be (N - A) * (A).
Why? Because we have these two sets of nodes, lets say we remove the {u,v} edge then the we'll get 2 trees, say all nodes in u side are in set X and all nodes in v side are in set Y. Then we can see that for each node in set X we can make a path to each node in set Y that crosses the {u,v} edge. So total number of paths will be = |X| * |Y|, (|setS| = size of setS). You can achieve this whole step in the same dfs if you notice closely whie computing subtreeSize
pseudocode for the complete O(N) algorithm:
dfs(node, parent):
subtreeSize[node] = 1
for each child c of node do:
dfs(c, node)
subtreeSize[node] = subtreeSize[node] + subtreeSize[c]
answerForEdge[node and parent] = (N - subtreeSize[node])*(subtreeSize[node]) // N is the total number of nodes
return
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
edited Jan 13 at 6:16
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
answered Jan 12 at 5:27
Jayant SharmaJayant Sharma
214
214
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
add a comment |
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
$begingroup$
Welcome to Mathematics Stack Exchange community! The quick tour will help you get the most benefit from your time here. Also, please use MathJax for your equations.
$endgroup$
– dantopa
Jan 12 at 5:32
add a comment |
$begingroup$
If the edge is, say, {u,v}, it seems to me that you should be able to do a BFS from u (not including v) and a BFS from v (not including u).
From the BFS from u (omitting v), count the number of vertices you visit and add one to it (for u). This should be the number of paths leading to the u end of the edge (including the trivial path of just starting at u). Call this n(u).
Do the same thing from v (omitting u): count the number of vertices you visit and add one to it (for v). This will be the number of paths leading to the v end of the edge (including the trivial path of starting at v). Call this n(v).
Then you can simply multiply these together to get all the paths passing through edge {u,v}: the product is basically picking a path to u (of which there are n(u) such paths) and then picking a path to v (of which there are n(v) such paths).
BFS, on a tree, runs in O(V), where V is the number of nodes in the tree, so two BFS algorithms also run in time O(V) as well: thus, the algorithm is linear in the number of vertices. Indeed, since the double BFS visits every vertex exactly once, it can be done in V steps precisely.
You'll note that this works with your example: for instance, if we take {2,4}, starting a BFS at 2 gives us 2 vertices, namely 1 and 3, so:
n(2) = 2 + 1 = 3.
(Remember we add 1 for vertex 2 itself.)
Then, starting a BFS at 4 also gives us 2 vertices, namely 5 and 6, so:
n(4) = 2 + 1 = 3
(Remember that we add 1 for vertex 4 itself.)
Thus, the total number of paths through edge {2,4} is:
n(2) * n(4) = 3 * 3 = 9.
answered Aug 5 '18 at 11:51
vorpalvorpal
113
$endgroup$
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
add a comment |
$begingroup$
If the edge is, say, {u,v}, it seems to me that you should be able to do a BFS from u (not including v) and a BFS from v (not including u).
From the BFS from u (omitting v), count the number of vertices you visit and add one to it (for u). This should be the number of paths leading to the u end of the edge (including the trivial path of just starting at u). Call this n(u).
Do the same thing from v (omitting u): count the number of vertices you visit and add one to it (for v). This will be the number of paths leading to the v end of the edge (including the trivial path of starting at v). Call this n(v).
Then you can simply multiply these together to get all the paths passing through edge {u,v}: the product is basically picking a path to u (of which there are n(u) such paths) and then picking a path to v (of which there are n(v) such paths).
BFS, on a tree, runs in O(V), where V is the number of nodes in the tree, so two BFS algorithms also run in time O(V) as well: thus, the algorithm is linear in the number of vertices. Indeed, since the double BFS visits every vertex exactly once, it can be done in V steps precisely.
You'll note that this works with your example: for instance, if we take {2,4}, starting a BFS at 2 gives us 2 vertices, namely 1 and 3, so:
n(2) = 2 + 1 = 3.
(Remember we add 1 for vertex 2 itself.)
Then, starting a BFS at 4 also gives us 2 vertices, namely 5 and 6, so:
n(4) = 2 + 1 = 3
(Remember that we add 1 for vertex 4 itself.)
Thus, the total number of paths through edge {2,4} is:
n(2) * n(4) = 3 * 3 = 9.
answered Aug 5 '18 at 11:51
vorpalvorpal
113
$endgroup$
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
add a comment |
$begingroup$
If the edge is, say, {u,v}, it seems to me that you should be able to do a BFS from u (not including v) and a BFS from v (not including u).
From the BFS from u (omitting v), count the number of vertices you visit and add one to it (for u). This should be the number of paths leading to the u end of the edge (including the trivial path of just starting at u). Call this n(u).
Do the same thing from v (omitting u): count the number of vertices you visit and add one to it (for v). This will be the number of paths leading to the v end of the edge (including the trivial path of starting at v). Call this n(v).
Then you can simply multiply these together to get all the paths passing through edge {u,v}: the product is basically picking a path to u (of which there are n(u) such paths) and then picking a path to v (of which there are n(v) such paths).
BFS, on a tree, runs in O(V), where V is the number of nodes in the tree, so two BFS algorithms also run in time O(V) as well: thus, the algorithm is linear in the number of vertices. Indeed, since the double BFS visits every vertex exactly once, it can be done in V steps precisely.
You'll note that this works with your example: for instance, if we take {2,4}, starting a BFS at 2 gives us 2 vertices, namely 1 and 3, so:
n(2) = 2 + 1 = 3.
(Remember we add 1 for vertex 2 itself.)
Then, starting a BFS at 4 also gives us 2 vertices, namely 5 and 6, so:
n(4) = 2 + 1 = 3
(Remember that we add 1 for vertex 4 itself.)
Thus, the total number of paths through edge {2,4} is:
n(2) * n(4) = 3 * 3 = 9.
answered Aug 5 '18 at 11:51
vorpalvorpal
113
$endgroup$
If the edge is, say, {u,v}, it seems to me that you should be able to do a BFS from u (not including v) and a BFS from v (not including u).
From the BFS from u (omitting v), count the number of vertices you visit and add one to it (for u). This should be the number of paths leading to the u end of the edge (including the trivial path of just starting at u). Call this n(u).
Do the same thing from v (omitting u): count the number of vertices you visit and add one to it (for v). This will be the number of paths leading to the v end of the edge (including the trivial path of starting at v). Call this n(v).
Then you can simply multiply these together to get all the paths passing through edge {u,v}: the product is basically picking a path to u (of which there are n(u) such paths) and then picking a path to v (of which there are n(v) such paths).
BFS, on a tree, runs in O(V), where V is the number of nodes in the tree, so two BFS algorithms also run in time O(V) as well: thus, the algorithm is linear in the number of vertices. Indeed, since the double BFS visits every vertex exactly once, it can be done in V steps precisely.
You'll note that this works with your example: for instance, if we take {2,4}, starting a BFS at 2 gives us 2 vertices, namely 1 and 3, so:
n(2) = 2 + 1 = 3.
(Remember we add 1 for vertex 2 itself.)
Then, starting a BFS at 4 also gives us 2 vertices, namely 5 and 6, so:
n(4) = 2 + 1 = 3
(Remember that we add 1 for vertex 4 itself.)
Thus, the total number of paths through edge {2,4} is:
n(2) * n(4) = 3 * 3 = 9.
answered Aug 5 '18 at 11:51
vorpalvorpal
113
edited Aug 6 '18 at 13:07
answered Aug 5 '18 at 11:51
vorpalvorpal
113
answered Aug 5 '18 at 11:51
vorpalvorpal
113
answered Aug 5 '18 at 11:51
vorpalvorpal
113
113
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
add a comment |
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
vorpal the solution mentioned by you will be O(n^2) not O(n) as you have to do it for each edge.
$endgroup$
– manofp
Aug 8 '18 at 4:20
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
@manofp It will be a linear time. Think. Hint: use post order traversal
$endgroup$
– Sushil Verma
Aug 10 '18 at 17:39
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
$begingroup$
A tree over n vertices has exactly n-1 edges, so it's not O(n^2) but O(n). For generic graphs, it is O(V + E), where V is the number of vertices and E is the number of edges. In this case, E = V-1, so O(V + (V-1)) = O(V) as desired.
$endgroup$
– vorpal
Aug 28 '18 at 22:51
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872647%2ffor-each-edge-in-a-tree-counting-paths-passing-through-this-edge%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Shouldn't there be 8 paths including ${4,5}$? Namely one for each combination of "vertex on one side of the chosen edge" (1,2,3, or 4) and "vertex on the other side of the chosen edge" (5 or 6).
$endgroup$
– Henning Makholm
Aug 5 '18 at 5:23
$begingroup$
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
$endgroup$
– Sushil Verma
Aug 5 '18 at 7:26