Cuprins
- 1. ARGUMENT
- 2. GRAFURI
- 3. DRUMURI INTR-UN GRAF
- a. Drumuri minime
- b. Drumuri maxime
Extras din proiect
Am ales aceasta tema in scopul de a va arata ca si in informatica exista distante (adica ”drumuri”) atat minime cat si maxime intre elementele unui graf fie el orientat sau neorientat.
GRAFURI
Fie o mulţime finită x={x1,x2,…,xn}.Fie Γ XxX, unde XxX este produsul cartezian al mulţimii X cu ea însăşi.
Definiţie. Se numeşte graf orientat perechea ordonată G=(x, Γ).
- Elementele xi є x se numesc noduri sau vârfuri.
- Elementele mulţimii Γ se numesc arce.Un arc (xk,xi)єΓ se notează şi cu [xk,xi].Prin abuz de notaţie, vom scrie: [xk,xi]єΓ.
În concluzie, graful este: G=(x, Γ)= ({x1,x2,x3,x4},{[x1,x2],[x2,x1],[x3,x4],[x3,x2],[x3,x3]}).
Un graf orientat poate fi reprezentat printr-un desen, aşa cum rezultă din imaginea alăturată.
Dacă în graful G=(x, Γ) [x,y]єΓ vom spune că x şi y sunt adiacente, iar vârfurile x şi y sunt incidente cu muchia [x,y].
Dacă Γ=Ø (mulţimea vidă),graful G=(x, Γ) se numeşte graf nul şi reprezentarea lui în plan se reduce la puncte izolate.
Definiţie.Un graf parţial al unui graf orientat dat G=(x, Γ) este un graf G1=(x, Γ1) unde Γ1 Γ un graf partial se obtine dintr-un graf suprimand anumite arcuri.
G=(x, Γ) G1=(x, Γ1)
Definiţie: Un subgraf al unui graf orientat G=(x, Γ) este un graf H=(x, Γ1), unde ,iar muchiile din sunt toate muchiile din care au ambele extremităţi în mulţimea Y.
DRUMURI INTR-UN GRAF
Fie G=(X,U) un graf orientat.Se numeste drum in graful G ,D=(x1,x2,x3,...,xk) o succesiune de varfuri cu proprietatea ca [xi,xi+1]€U , unde 1<=i<=k-1.
Observatii:
- Varfurile x1 si xk sunt numite extremitatile drumului.
Preview document
Conținut arhivă zip
- Drumuri de Cost Minim si Maxim.doc