minimum edge for deletion

[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) ).

[Dimitar]

Now I got it

Thanks for the help!

[bugzpodder]

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).

[mf]

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.

[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

[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.

[Pasa Yildirim]

OK, works for me :D, thank you!