5.4.Minimum Genetic Tree.

Let's assume a network G with cost function for its sides c.That means that c[e(ij)] is a real number and represents the cost for the e(ij) arc.For simplicity we can accept the following:

• There are no arcs for a peak to itself,therefore e(ii) does not belong to the E set for i=1..n.As usually, n is the number of the peaks of G.
• All costs are positive,therefore c[e(ij)]>0 for i<>j.
• We expand the c function to the non existing sides( e(ii) not belonging to the E set for i=1..n) assuming that :
• The cost of the direct access of one peak to itself is zero,c[e(ii)]=0;
• If there is no side connecting V(i) to V(j) that is e(ij) does not belong to the E set,then the direct access from one peak to another costs infinite.The final conclusion is:

  c[e(ij)] ={	0 , if i=j.
  	infinite , if i<>j.

We can easily assume that G is connective.

As cost of a G's undergraph is set the total cost of its sides.We are extremely concerned in the cost of a genetic tree T=(V',E'),where V'=V,that is the positive number:
cost(T)=Sum( c[e(ij)] ) for e(ij) belonging to E'.

We will examine two algorithms,which solve the problem of finding the minimum genetic tree (m.g.t.) that is a genetic tree T which satisfies the following:cost(T) <=cost(T') ,for every genetic tree T' of G.
They are the PRIM and the KRUSKAL algorithm.
(You obviously click on the algorithm you wish to learn more about.)

HTML PAGE DIRECTOR :Papaioannou Panagiotis