/ Biblioteca / Cursuri / Agronomie > Grafuri

Grafuri

Imagine preview
(9/10 din 1 vot)
pdf

Acest curs prezinta Grafuri.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 8 fisiere pdf de 507 de pagini (in total).

Profesor: Șl. Dr. Ing. Șerban Radu

Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Agronomie

Descarcă acum

Extras din document

Problema drumului de lungime minimă din orice vârf

-

Problema se referă la aflarea costului minim din orice vârf către oricare alt vârf, folosind muchii multiple

-

Aceasta se numește problema drumului de lungime minimă din orice vârf (all-pairs shortest path problem)

Algoritmul lui Floyd

-

Algoritmul lui Warshall reprezintă o modalitate rapidă de a crea un tabel care indică vârfurile în care se poate ajunge dintr-un anumit vârf, într-unul sau mai mulți pași

-

O abordare similară pentru grafuri ponderate este folosită de algoritmul lui Floyd, descoperit de Robert Floyd în 1962

Observații

-

Matricea de adiacență indică costurile tuturor căilor cu o singură muchie

-

Se dorește extinderea acestei matrici pentru a indica costurile tuturor căilor, indiferent de lungimea lor

-

De exemplu, se poate ajunge de la B la C cu un cost de 30 (10 de la B la D și 20 de la D la C)

Observații

-

Similar algoritmului lui Warshall, se modifică matricea de adiacență

-

Se examinează fiecare celulă de pe fiecare rând

-

Dacă există o pondere pozitivă, de exemplu 30 la intersecția liniei C cu coloana A, atunci se analizează coloana C, deoarece C reprezintă linia unde se află 30

Observații

-

Dacă se găsește o celulă în coloana C, de exemplu 40 la linia D, atunci există o cale de la C la A cu o pondere de 30 și o cale de la D la C cu o pondere de 40

-

Se poate deduce că există o cale cu două muchii de la D la A, cu o pondere de 70

Observații

-

Linia A este vidă

-

Pe linia B este 70 în coloana A și 10 în coloana D, dar coloana B este vidă, deci muchiile care încep din B nu pot fi combinate cu nicio muchie care se termină în B

Observații

-

În linia C se află 30 pe coloana A

-

În coloana C se află 20 pe linia D

-

Muchia de la C la A are o pondere de 30

-

Muchia de la D la C are o pondere de 20

-

Se obține calea de la D la A cu ponderea de 50

Observații

-

Linia D arată o situație interesantă - se poate micșora un cost existent deja

-

Pe linia D există 50 în coloana A

-

Pe linia B există 10 în coloana D

-

Există o cale de la B la A cu costul 60

-

Cu toate acestea, există deja costul 70 pe linia B, în coloana A

Observații

-

Deoarece 60 e mai mic decât 70, se înlocuiește 70 cu 60

-

În cazul căilor multiple de la un vârf la altul, tabelul indică calea de cost minim

Observații

-

Implementarea algoritmului lui Floyd este similară algoritmului lui Warshall

-

În locul inserării valorii 1 în tabel, cum se procedează în algoritmul lui Warshall, când se găsește o cale cu două muchii, se adaugă costul căii cu două muchii și se inserează suma costurilor celor două muchii în tabel

Fisiere in arhiva (8):

  • Algoritmul lui Floyd.pdf
  • EXPLORAREA GRAFURILOR.pdf
  • GRAFURI.pdf
  • GRAFURI PONDERATE.pdf
  • Grafuri Quiz 3.pdf
  • Introducere in Teoria Grafurilor+Raspunsuri.pdf
  • Quiz Grafuri 2.pdf
  • SORTAREA TOPOLOGICA.pdf
Descarcă Acest curs

Altii au mai descarcat

  • Ecotehnica Cultivarii Tutunului si Hameiului

    TIPUL DE SOL DIN REGIUNEA BUCURESTI Soluri de tip hidromorf si brun-roscate Caracteristici :...

    Lepidoptere

    FLUTURELE ALB AL VERZEI - PIERIS BRASSICAE Fluturele alb al verzei este raspandit in...

  • Tehnologia Obtinerii Berii

    Berea este o bautura alcoolica nedistilata, obisnuita prin fermentarea cu drojdie a unui must...

    Tehnologia Cresterii Cabalinelor

    1.Importanta cresterii cabalinelor Munca sau forta de tractiune este principala productie de...

  • Cultura Capsunului

    Căpşunul este o plantă semiierboasă, perenă, ce creşte sub formă de tufă cu înălţimea de 15-40...

    Plante Medicinale

    Plantele medicinale sunt acea categorie de specii vegetale care acumulează în unele părţi ale...

  • Bonitarea Terenului

    Calitatea terenurilor. Definire. Concepţii 1.Să ne definim termenii ! _________ Teritoriu...

    Floricultura

    Floricultura - este ştiinţa şi ramura horticulturii care se ocupă cu studiul particularităţilor...