Grafice încărcate

Un grafic încărcat este un grafic orientat D = (V, X), pe a cărui set de arce este definită o anumită funcție. care se numește funcția de greutate.

Figura deasupra arcului (a se vedea figura 5) este greutatea arcului (prețul arcului).







Notație: pentru orice cale P a unui grafic orientat încărcat D, cu l (Π), suma lungimilor arcilor care intră pe calea P. (Fiecare arc este numărat de câte ori intră în calea Π).

Cantitatea l este numită lungimea căii.

Dacă alegem greutăți egale cu 1, ajungem la graficul descărcat.







O cale într-un grafic orientat încărcat de la vârful v la vârful w. unde v ¹ w. se numește minim. dacă are cea mai mică lungime.

Traseul minim în graficul încărcat este definit în mod similar.

Introducem matricea lungimilor arcului C (D) = [cij] de ordine n. și

Proprietățile căilor minime într-un grafic orientat încărcat

1) Dacă pentru "arc, atunci" calea minimă (rută) este un lanț simplu;

2) dacă calea minimă (traseu) este, atunci pentru "i, j. Calea (traseul) este de asemenea minimă;

3) dacă - calea minimă (rută) între căi (rute) de la v la w. care conține nu mai mult de k +1 arce (marginile), apoi - calea minimă (rută) de la v la u între căile (rutele) care nu conțin mai mult de arce (margini).







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: