Mixing
![Find the minimum of $MA + MB$ when $M$ is on the circle [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
For each edge in a tree, counting paths passing through this edge
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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 yesterday
Sushil Verma
406
add a comment |Â
up vote
1
down vote
favorite
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 yesterday
Sushil Verma
406
1
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).
– Henning Makholm
yesterday
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
– Sushil Verma
yesterday
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 yesterday
Sushil Verma
406
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 yesterday
Sushil Verma
406
edited yesterday
asked yesterday
Sushil Verma
406
asked yesterday
Sushil Verma
406
asked yesterday
Sushil Verma
406
406
1
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).
– Henning Makholm
yesterday
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
– Sushil Verma
yesterday
add a comment |Â
1
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).
– Henning Makholm
yesterday
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
– Sushil Verma
yesterday
1
1
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).
– Henning Makholm
yesterday
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).
– Henning Makholm
yesterday
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
– Sushil Verma
yesterday
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
– Sushil Verma
yesterday
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
If the edge is, say, u,v, it seems to me that you should be able to do a BFS from u (ignoring v and its neighbours) and a BFS from v (ignoring u and its neighbours).
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 yesterday
vorpal
12
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
If the edge is, say, u,v, it seems to me that you should be able to do a BFS from u (ignoring v and its neighbours) and a BFS from v (ignoring u and its neighbours).
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 yesterday
vorpal
12
add a comment |Â
up vote
0
down vote
If the edge is, say, u,v, it seems to me that you should be able to do a BFS from u (ignoring v and its neighbours) and a BFS from v (ignoring u and its neighbours).
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 yesterday
vorpal
12
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If the edge is, say, u,v, it seems to me that you should be able to do a BFS from u (ignoring v and its neighbours) and a BFS from v (ignoring u and its neighbours).
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 yesterday
vorpal
12
If the edge is, say, u,v, it seems to me that you should be able to do a BFS from u (ignoring v and its neighbours) and a BFS from v (ignoring u and its neighbours).
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 yesterday
vorpal
12
edited yesterday
answered yesterday
vorpal
12
answered yesterday
vorpal
12
answered yesterday
vorpal
12
12
add a comment |Â
add a comment |Â
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
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
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
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
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
1
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).
– Henning Makholm
yesterday
@HenningMakholm you are correct, I updated the example. Actually 5 is not connected to 6, instead 4 is connected to 6.
– Sushil Verma
yesterday