Arbori Partiali de Cost Minim

Proiect
9/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 50 în total
Cuvinte : 4426
Mărime: 1.09MB (arhivat)
Cost: 5 puncte
Profesor îndrumător / Prezentat Profesorului: Prof. Ing. Stan Maria
ptr atestat

Cuprins

I. Arbori

II. Arbori Partiali De Cost Minim

III. Determinarea Arborilor Partiali De Cost Minim

IV. Algoritmul Lui Kruskal

V. Algoritmul Lui Prim

Extras din document

I. Arbori

Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un drum unic.

Definitia este valabila si pentru cazul unui graf neorientat, alegerea unei radacini fiind insa in acest caz arbitrara: orice arbore este un arbore cu radacina, iar radacina poate fi fixata in oricare varf al sau. Aceasta, deoarece dintr-un varf oarecare se poate ajunge in oricare alt varf printr-un drum unic.

Cand nu va fi pericol de confuzie, vom folosi termenul “arbore”, in loc de termenul corect “arbore cu radacina”. Cel mai intuitiv este sa reprezentam un arbore cu radacina, ca pe un arbore propriu-zis. In Figura 3.1, vom spune ca beta este tatal lui delta si fiul lui alpha, ca beta si gamma sunt frati, ca delta este un descendent al lui alpha, iar alpha este un ascendent al lui delta. Un varf terminal este un varf fara descendenti. Varfurile care nu sunt terminale sunt neterminale. De multe ori, vom considera ca exista o ordonare a descendentilor aceluiasi parinte: beta este situat la stanga lui gamma, adica beta este fratele mai varstnic al lui gamma.

Orice varf al unui arbore cu radacina este radacina unui subarbore constand din varful respectiv si toti descendentii sai. O multime de arbori disjuncti formeaza o padure.

Intr-un arbore cu radacina vom adopta urmatoarele notatii. Adancimea unui varf este lungimea drumului dintre radacina si acest varf; inaltimea unui varf este lungimea celui mai lung drum dintre acest varf si un varf terminal; inaltimea arborelui este inaltimea radacinii; nivelul unui varf este inaltimea arborelui, minus adancimea acestui varf.

Reprezentarea unui arbore cu radacina se poate face prin adrese, ca si in cazul listelor inlantuite. Fiecare varf va fi memorat in trei locatii diferite, reprezentand informatia propriu-zisa a varfului (valoarea varfului), adresa celui mai varstnic fiu si adresa urmatorului frate. Pastrand analogia cu listele inlantuite, daca se cunoaste de la inceput numarul maxim de varfuri, atunci implementarea arborilor cu radacina se poate face prin tablouri paralele

Au fost studiate diferite tipuri de arbori binari, adică arbori pentru care e-gradul fiecărui nod este mai mic sau egal cu 2. Arborii care au e-gradul mai mare sau egal cu 2 se numesc arbori multicăi.

Dacă se doreşte să se prezinte descendenţa unei persoane din punct de vedere al strămoşilor, i se asociază persoanei doi părinţi, obţinându-se un arbore binar.

Preview document

Arbori Partiali de Cost Minim - Pagina 1
Arbori Partiali de Cost Minim - Pagina 2
Arbori Partiali de Cost Minim - Pagina 3
Arbori Partiali de Cost Minim - Pagina 4
Arbori Partiali de Cost Minim - Pagina 5
Arbori Partiali de Cost Minim - Pagina 6
Arbori Partiali de Cost Minim - Pagina 7
Arbori Partiali de Cost Minim - Pagina 8
Arbori Partiali de Cost Minim - Pagina 9
Arbori Partiali de Cost Minim - Pagina 10
Arbori Partiali de Cost Minim - Pagina 11
Arbori Partiali de Cost Minim - Pagina 12
Arbori Partiali de Cost Minim - Pagina 13
Arbori Partiali de Cost Minim - Pagina 14
Arbori Partiali de Cost Minim - Pagina 15
Arbori Partiali de Cost Minim - Pagina 16
Arbori Partiali de Cost Minim - Pagina 17
Arbori Partiali de Cost Minim - Pagina 18
Arbori Partiali de Cost Minim - Pagina 19
Arbori Partiali de Cost Minim - Pagina 20
Arbori Partiali de Cost Minim - Pagina 21
Arbori Partiali de Cost Minim - Pagina 22
Arbori Partiali de Cost Minim - Pagina 23
Arbori Partiali de Cost Minim - Pagina 24
Arbori Partiali de Cost Minim - Pagina 25
Arbori Partiali de Cost Minim - Pagina 26
Arbori Partiali de Cost Minim - Pagina 27
Arbori Partiali de Cost Minim - Pagina 28
Arbori Partiali de Cost Minim - Pagina 29
Arbori Partiali de Cost Minim - Pagina 30
Arbori Partiali de Cost Minim - Pagina 31
Arbori Partiali de Cost Minim - Pagina 32
Arbori Partiali de Cost Minim - Pagina 33
Arbori Partiali de Cost Minim - Pagina 34
Arbori Partiali de Cost Minim - Pagina 35
Arbori Partiali de Cost Minim - Pagina 36
Arbori Partiali de Cost Minim - Pagina 37
Arbori Partiali de Cost Minim - Pagina 38
Arbori Partiali de Cost Minim - Pagina 39
Arbori Partiali de Cost Minim - Pagina 40
Arbori Partiali de Cost Minim - Pagina 41
Arbori Partiali de Cost Minim - Pagina 42
Arbori Partiali de Cost Minim - Pagina 43
Arbori Partiali de Cost Minim - Pagina 44
Arbori Partiali de Cost Minim - Pagina 45
Arbori Partiali de Cost Minim - Pagina 46
Arbori Partiali de Cost Minim - Pagina 47
Arbori Partiali de Cost Minim - Pagina 48
Arbori Partiali de Cost Minim - Pagina 49
Arbori Partiali de Cost Minim - Pagina 50

Conținut arhivă zip

  • Arbori Partiali de Cost Minim.doc

Alții au mai descărcat și

Controlul Proceselor Neliniare Utilizând Automate Programabile

Introducere Odata cu progresul tehnicii, calculatoarele au devenit elemente esentiale pentru implementarea sistemelor de reglare automata....

Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...

Mentinerea Distantei intre 2 Vehicule

Menţinerea automată a distanţei optime între automobile Acest proiect tratează problema menţinerii distanţei optime între două autovehicule pe...

Verificarea Automata a Vorbitorului

Subiectul acestei lucrari il reprezinta verificarea automata a vorbitorului. In tratarea lucrarii nu s-a luat in consideratie verificarea...

Algoritmi de Rutare

Algoritmii de rutare pot fi diferenţiaţi după obiectivul particular dorit, impactul asupra reţelei şi resurselor ruterului, metricile folosite....

Arbori

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRARII . DOMENIUL (N CARE SE (NCADREAZA LUCRAREA (n momentul de fata prelucrarea informatiilor de orice...

Structuri de Date și Algoritmi

1. Conceptul de dată În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine...

Structuri de Date

CURS 1. - STRUCTURI DE DATE Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii....

Ai nevoie de altceva?