Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

ARBORELE PARTIAL DE COST MINIM

calculatoare



+ Font mai mare | - Font mai mic



ARBORELE PARTIAL DE COST MINIM



Definitie. Fie G=(V,M) un graf. Se numeste arbore partial, al lui G, un graf partial al sau, care , in plus, este si arboreal.

Exemplu: Daca din graful:

se elimina muchiile [2,4] si [1,3], se obtine un graf partial, care este si arbore(conex si fara cicluri), deci se obtine un arbore partial.

Propozitie. Fie G=(V,M) un graf. Graful G contine un arbore partial daca si numai daca este conex.

Definitie. Fie G=(V,M) un graf conex si H=(V,M1) un arbore partial al sau. Definim costul arborelui partial H ca fiind suma costurilor muchiilor sale.

Exempul: Fie graful din figura de mai jos (costul fiecarei muchii fiind scris pe ea).

Considerand arborele partial al sau, H, care se obtine eliminand muchiile [2,4] [3,4] putem calcula costul sau, conform definitiei de mai sus, astfel: cost(H)=cost([l,2])+cost([l,4])+cost([2,3])=l 1+13+15=39





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1892
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