Definiții de bază
Graficul orientat G = (V, E) constă din setul de vârfuri V și setul de arce E. Vârfurile sunt de asemenea numite noduri. iar arcele sunt muchii orientate. Arcul este reprezentabil sub forma unei perechi ordonate de vârfuri (v, w). unde vertexul v este denumit originea. și w este sfârșitul arcului.
Neorientat grafG = (V, E) este format dintr-un set finit de vârfuri V și o multitudine de muchii E. In contrast cu graficul direcționat, în cazul în care fiecare muchie (v, w) corespunzătoare perechii dezordonate de noduri: if (v, w) - neorientat muchie, atunci ( v, w) = (w, v).
Un vârf X este considerat a fi incident la o margine G dacă o margine conectează acest vârf la un alt vârf.
În problema celei mai scurte căi, avem un graf ponderat orientat G = (V, E) cu funcție reală de greutate w: E R
Greutatea traseului p = (v0, v1, vk) este suma greutăților margini care intră în această cale:
Greutatea celei mai scurte căi de la u la v este, prin definiție,
Cea mai scurtă cale de la u la v este orice cale p de la u la v. pentru care
Un grafic este numit degenerat. dacă nu are muchii.
Vârfurile sunt numite adiacente. dacă există o margine care le conectează.
Un grafic gol este numit gol. Un grafic este numit complet, în care fiecare două vârfuri sunt adiacente.
Un ciclu în care toate nodurile, cu excepția primei și ultimei, sunt pereche distincte, se numește un ciclu simplu.
Se spune că un grafic este conectat. dacă pentru oricare dintre cele două noduri există o cale care leagă aceste vârfuri.
Șuruburi cu greutate negativă
Uneori, greutatea coastelor poate fi negativă. Este important, dacă există cicluri de greutate negativă. În cazul în care pornește din punctul lui se poate ajunge la un ciclu de greutate negativ, atunci este posibil pentru a ocoli acest ciclu la infinit, iar greutatea va fi reduse, astfel încât cele mai scurte trasee nu există pentru nodurile acestui ciclu: În acest caz, se poate presupune că greutatea unui drumul cel mai scurt este - ∞.
Dacă nu există cicluri de greutate negativă, atunci orice ciclu poate fi aruncat fără a extinde traseul. Căile fără cicluri sunt finite, deci greutatea celei mai scurte căi este bine definită.
Reprezentarea celor mai scurte căi într-un algoritm
Este adesea necesar nu numai să se calculeze greutățile celor mai scurte căi, ci și să se găsească singure aceste căi. Fie G = (V, E) un grafic dat. Pentru fiecare vârf, ne vom aminti predecesorul său. Precursorul unui vârf este fie un alt vârf, fie NIL. La finalizarea algoritmilor, lanțul predecesorilor. începând cu un vârf arbitrar v. va fi cea mai scurtă cale de la s la v. astfel că dacă ≠ NIL, Print-Path (G, s, v) imprimă calea cea mai scurtă de la s la v.
Înainte de terminarea operării algoritmilor, lanțurile obținute prin iterațiile π. nu neapărat căi mai scurte, dar putem considera subgraful orientat al precedentei Gπ = (Vπ, E π). definită după cum urmează: vârfurile Gπ sunt acele noduri ale lui G. în care predecesorul este diferit de NIL, plus vârful original: Vπ = [v] ≠ NIL> s>. Marginile Gπ sunt săgeți indicând de la π [v] ≠ NIL la v. E π = [v], v) E. vVπ \ s >>.
Un copac cu cele mai scurte căi cu o rădăcină în s este un subgraf orientat G '= (V', E ').
unde V 'V și E' E. pentru care:- V 'este mulțimea de noduri accesibile de la vârful s.
- G este un copac cu rădăcini.
- pentru fiecare vV 'calea de la s la v în graficul G' este calea cea mai scurtă de la s la v în grafic G.
Acest site a fost creat cu uCoz
Articole similare
Trimiteți-le prietenilor: