cme

Cosmin Poieana, A5
IT - employee Foundation F', Est
Arbore partial de cost minim


--------
Algoritm
--------
    Fie un graf G ponderat, neorientat si conex. APM creeaza din acest graf un
graf partial cu toate proprietatile de mai sus, dar fara cicluri (arbore),
selectand muchiile de cost minim.
Mai multe detalii: http://en.wikipedia.org/wiki/Minimum_spanning_tree

--------
Scenariu
--------
    Se vrea a se construi un sistem de cai ferate "speciale" pentru
niste trenuri neconventionale, cu gabarite depasite, specializate
in transportul de diverse marfuri. Construirea unor astfel de sine
(si a dependentelor din motive de securitate) este foarte costisitoare
si trebuie sa existe posibilitatea ca din orice oras sa se poata ajunge
in oricare alt oras ce face parte din sistem. Timpul pentru a ajunge de
la sursa la destinatie nu este luat in calcul, asa ca ne concentram
asupra minimizarii costului construirii unui astfel de arbore, unde
nodurile reprezinta orasele, iar muchiile caile in sine.

---
Rol
---
    Ca angajat la fundatia F' as putea lucra in echipa cu doi dintre "colegii mei":
        #1. Leoca Constantin Mihail    [email protected]
            Greatest common divisor    Manager Foundation F'
        #2. Munteanu Cristian          [email protected]
            Quicksort                  IT - employee Foundation F'
deoarece algoritmul descris mai sus, fiind unul greedy, foloseste o sortare (#2)
pentru ordonarea muchiilor in functie de cost (ponderi) si pentru ca infrastructura
retelei de transport este alcatuita din mai multe segmente, iar pentru reducerea
costurilor, lungimea acestor segmente trebuie maximizata, deci folosirea unui
'cel mai mare divizor comun' (#1).
De asemenea, din echipa pot face parte si alti membri, mai ales cei cu
agentiile de turism, pentru a extinde afacerea.