CATEGORII DOCUMENTE |
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:
O firma de instalatii electrice studiaza
posibilitatea de legare a 6 consumatori (C1, , C6) la punctul de alimentare
(A). Conditiile tehnice de instalare permit stabilirea unui numar de 11
legaturi, date impreuna cu costurile aferente in graful de mai jos.
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:
S |
WS1 |
WS2 |
WS3 |
WS4 |
WS5 |
WS6 |
WS7 |
|
S | ||||||||
WS1 |
|
|||||||
WS2 | ||||||||
WS3 | ||||||||
WS4 | ||||||||
WS5 | ||||||||
WS6 | ||||||||
WS7 |
Sa se traseze graful asociat.
Sa se rezolve problema si sa se traseze arborele solutie.
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2043
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved