Qch
- 2
- 0
Hello,
I really need help solving the following problem. I only begin to get familiar with graphs and might have missed something, but I do not know how to solve this. Ok here goes, and sorry for my English in advance.
There is undirected, unweighted graph G = (V, E). Every edge in this graph is road segment, every vertex - crossroad.
Pooh lives in vertex "A" and Tigra in vertex "n - 1", where "n" is total number of vertexes. Winnie goes to his neighbor every week, but forgets to take his honey pot with him. That is why he decided that he will hide his honey pots near the road segments in a tree. But he is so f** lazy, that he wants to hide them in limited places.
The task is to implement the most effective algorithm, which will be able to find smallest possible edges set, at which Pooh will be able to hide his honey pots, that guarantee, that each path from vertex A to vertex B contains at least one of the edges.
So, in other words, whichever road Pooh would take he must be able to seat and eat his honey at least once.
What is already done:
I have already wrote an algorithm to find ALL paths from Pooh's home till Tigra's home. And now I'm stuck.
I know that:
1. if vertex A has more edges than last vertex - we burry honey pots near Tigra's house.
2. if vertex A has less edges than last vertex - we burry honey pots near Pooh's house.
3. I do not know what to do next.
So, if we have the following graph:
(1, 3), (3, 2), (3, 4), (2, 5), (2, 5)
and Pooh lives in 1 and Tigra in 5 than we burry a pot at (1, 3), because this road definitely will be taken (rule #1 works).
Assume that Pooh lives in 5 and Rigra in 1, than rule #2 applies.
But, what if we have the following graph, where we have the same number of edges from Tigra's and Pooh's house?
May be above algorithm is not right at all.
Any ideas?
Thank you in advance.
I really need help solving the following problem. I only begin to get familiar with graphs and might have missed something, but I do not know how to solve this. Ok here goes, and sorry for my English in advance.
There is undirected, unweighted graph G = (V, E). Every edge in this graph is road segment, every vertex - crossroad.
Pooh lives in vertex "A" and Tigra in vertex "n - 1", where "n" is total number of vertexes. Winnie goes to his neighbor every week, but forgets to take his honey pot with him. That is why he decided that he will hide his honey pots near the road segments in a tree. But he is so f** lazy, that he wants to hide them in limited places.
The task is to implement the most effective algorithm, which will be able to find smallest possible edges set, at which Pooh will be able to hide his honey pots, that guarantee, that each path from vertex A to vertex B contains at least one of the edges.
So, in other words, whichever road Pooh would take he must be able to seat and eat his honey at least once.
What is already done:
I have already wrote an algorithm to find ALL paths from Pooh's home till Tigra's home. And now I'm stuck.
I know that:
1. if vertex A has more edges than last vertex - we burry honey pots near Tigra's house.
2. if vertex A has less edges than last vertex - we burry honey pots near Pooh's house.
3. I do not know what to do next.
So, if we have the following graph:
(1, 3), (3, 2), (3, 4), (2, 5), (2, 5)
and Pooh lives in 1 and Tigra in 5 than we burry a pot at (1, 3), because this road definitely will be taken (rule #1 works).
Assume that Pooh lives in 5 and Rigra in 1, than rule #2 applies.
But, what if we have the following graph, where we have the same number of edges from Tigra's and Pooh's house?
May be above algorithm is not right at all.
Any ideas?
Thank you in advance.