# Re: Graph theory problem

• From: Barb Knox <see@xxxxxxxxx>
• Date: Tue, 22 Aug 2006 10:24:46 +1200

In article <1156194250.826872.126270@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Rij" <rij.ghosh@xxxxxxxxx> wrote:

Let G have even no. of nodes. I want to eventually merge all nodes into
1. At each step, I will merge any two nodes. The cost of each merge is
the weight
of the edge common to the two vertices. The cost at each step is the
sum of the cost of all such merges. I want to minimize the cost over
all the steps.

So, the total cost after all the steps is the sum of the weights of all
the edges that have been eliminated. Since eventually you want to end
up with just 1 node, you will eliminate ALL edges except the one edge
(if any) from that node to itself. So, pick a node with no edge to
itself, or if there isn't any then a node with the minimum-weight such
edge, and let that be your final node. Then ANY pattern of merges
ending with just that node will have the same cost, which is the minimum.

Does this sound like any common graph theoretic problem? You can assume
edges are undirected and the graph to be fully connected if that makes
life easy.
.

## Relevant Pages

• Re: Griffin Calls STS, ISS "Mistakes"
... >>the weight and cost advantages of a disposable tank. ... (OTOH, if you used tripropellant engines in the orbiter, you ... >Drop tanks will be ar cheaper to design and build than even the most ...
(sci.space.policy)
• Re: Cessna BRS
... airframe capable of a 1320 lbs gross weight. ... The CT is the kind of competition Cessna has to go up against. ... I thought about a BRS in the Zenith I'm building. ... Repacking cost is not an "unknown" or particularly hard to find ...
(rec.aviation.homebuilt)
• Re: Traveling salesman, idea, easy to program?
... B is the same cost as B to A. ... Traveling Salesman is about *cost* of travel between the cities, ... Distance is in actuality one weight that is always there, ...
(comp.lang.java.programmer)
• Re: Sunday Mercury Comps c/d Midday September 1,2005
... WIN YOUR WEIGHT IN BEER ... > 'Waggle Dance Mercury' in the subject box. ... > number,house number postcode.Texts cost 25p ...
(uk.rec.competitions)
• Re: D8 manuals - RIP ?
... Borland to optionally provide printed sets at an extra cost). ... Then to potentially include the reference material in just ... Weight I can't argue with-- books do add weight, ...
(borland.public.delphi.non-technical)