## minimum edge for deletion

Moderator: Board moderators

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
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
New poster
Posts: 8
Joined: Tue Sep 20, 2005 11:42 am
Now I got it Thanks for the help!

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
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).

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
bugzpodder wrote:unless we are talking about different problems (since it isnt entirely clear)

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:
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

Dimitar
New poster
Posts: 8
Joined: Tue Sep 20, 2005 11:42 am