Drumuri in grafuri (II) (Networks - Minimum Spanning Tree)

Drumuri in grafuri (II) (Networks - Minimum Spanning Tree)

Se da un graf neorientat avand m noduri si n arce. Pentru arce se defineste o masura (de exemplu: cost, distanta). Se pune problema conectarii tuturor nodurilor astfel incat suma totala a valorilor arcelor utilizate sa fie minima.

Se obtine astfel - arborele drum minim.

Date de intrare:

numarul de arce [2 100]

pentru fiecare arc se indica:

numarul nodului de start;

numarul nodului final;

valoarea masurii arcului (distanta, cost);

Observatie:

Graful fiind neorientat nu conteaza ordinea in care sunt indicate extremitatile arcelor.

Exemplu:

Rezolvare

Se numeroteaza nodurile A 1, C1 2, , C6 7 si se introduc informatiile necesare celor 11 arce de exemplu: - arcul 1 :(1, 2) cu valoarea 20.

Este indiferenta ordinea de introducere a informatiilor despre arce.

Solutia este data in pagina 61.

Problema propusa:

O firma de calculatoare doreste instalarea unei retele arborescente formata dintr-un server (S) si 7 statii de lucru (WS1, , WS7). Conditiile tehnice de instalare permit stabilirea unui numar de 14 legaturi (arce). Costurile de instalare sunt date in matricea de mai jos:

Sa se traseze graful asociat.

Sa se rezolve problema si sa se traseze arborele solutie.