Page 2 of 2
Posted: Sat Aug 05, 2006 8:33 am
by chrismoh
Hi Dimitar,
it solves the problem because
(1) Do a DFS traversal, generate the DFS tree.
The initial number of edges you start with is equal to the number of edges in the tree, which is equal to the number of vertices - 1, if the graph is connected.
Since the algorithm only decreases the number of edges, but never increases it, the number of edges will never be more than (or even equal) to the number of vertices.
So in your case above, the tree will have 3 edges ( (1,2) (2,3) (3,4) ), and the algorithm kicks out edge (2,3) and then terminates, so the final answer is ( (1,2) (3,4) ).
Posted: Sat Aug 05, 2006 10:15 am
by Dimitar
Now I got it
Thanks for the help!
Posted: Sun Aug 06, 2006 5:32 pm
by bugzpodder
mf wrote:in Chinese postman you can run a min-cost matching on a general graph with vertices the odd degree vertices in the original graph and cost the shortest path between the vertices because you are allowed to count the cost of any edge more than once or twice - here you can only count the cost of an edge once.
Think a bit deeper. In a minimum cost matching, no two shortest paths can have a common edge. (See figure 6.16 on
this page.)
So you won't erase an edge more than once
unless we are talking about different problems (since it isnt entirely clear) for the IOI problem you cant assign the net flow passing through each vertices properly. so you cant solve the IOI problem using min-cost. also, as i said in my earlier post, removing an edge twice equals to not removing it at all. What you do is alternate the edges in a path (if its removed, put it back in and vice versa).
Posted: Sun Aug 06, 2006 6:12 pm
by mf
bugzpodder wrote:unless we are talking about different problems (since it isnt entirely clear)
My comment was about the problem in the first post of this thread, not about IOI's.
Posted: Thu Aug 10, 2006 7:10 pm
by Pasa Yildirim
Hello chrismoh!
Well, for sample graph from IOI task, DFS will give following edges:
Code: Select all
Orginal:
+
|
|
|
+------+
| | \
| | +
| | /
+------+
DFS:
+ (1)
|
|
|
+ (2) + (5)
| | \
| | + (6)
| |
+ (3)--+ (4)
By your algo, edge 5 have an even degree, now remove (4, 5).
Now, 3 has an even number, so remove (2, 3) (as I understood the algo :D )
This yields me to wrong answer -- am I worng or ...? :D
Regrads --PY
Posted: Thu Aug 10, 2006 8:03 pm
by Dimitar
Why wrong answer?
In the solution you have the edges (1,2), (3,4) and (5,6). Every vertex is of odd degree (1), so this solution is correct.
Posted: Thu Aug 10, 2006 10:36 pm
by Pasa Yildirim
OK, works for me :D, thank you!