Scrigroup - Documente si articole

     

HomeDocumenteUploadResurseAlte limbi doc
AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

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

calculatoare



+ Font mai mare | - Font mai mic



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



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 2043
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved