minimum edge for deletion

Let's talk about algorithms!

Moderator: Board moderators

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

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

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

Post by Dimitar »

Now I got it :)

Thanks for the help!

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:

Post 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

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

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

Pasa Yildirim
New poster
Posts: 14
Joined: Mon Mar 07, 2005 7:10 pm
Location: Bosnia and Herzegovina
Contact:

Post by Pasa Yildirim »

OK, works for me :D, thank you!

Post Reply

Return to “Algorithms”