Drumuri de Cost Minim și Maxim

Proiect
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 32 în total
Cuvinte : 2721
Mărime: 874.40KB (arhivat)
Cost: 4 puncte
Profesor îndrumător / Prezentat Profesorului: Prof. Ing. Stan Maria

Cuprins

1. ARGUMENT

2. GRAFURI

3. DRUMURI INTR-UN GRAF

a. Drumuri minime

b. Drumuri maxime

Extras din document

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

Drumuri de Cost Minim și Maxim - Pagina 1
Drumuri de Cost Minim și Maxim - Pagina 2
Drumuri de Cost Minim și Maxim - Pagina 3
Drumuri de Cost Minim și Maxim - Pagina 4
Drumuri de Cost Minim și Maxim - Pagina 5
Drumuri de Cost Minim și Maxim - Pagina 6
Drumuri de Cost Minim și Maxim - Pagina 7
Drumuri de Cost Minim și Maxim - Pagina 8
Drumuri de Cost Minim și Maxim - Pagina 9
Drumuri de Cost Minim și Maxim - Pagina 10
Drumuri de Cost Minim și Maxim - Pagina 11
Drumuri de Cost Minim și Maxim - Pagina 12
Drumuri de Cost Minim și Maxim - Pagina 13
Drumuri de Cost Minim și Maxim - Pagina 14
Drumuri de Cost Minim și Maxim - Pagina 15
Drumuri de Cost Minim și Maxim - Pagina 16
Drumuri de Cost Minim și Maxim - Pagina 17
Drumuri de Cost Minim și Maxim - Pagina 18
Drumuri de Cost Minim și Maxim - Pagina 19
Drumuri de Cost Minim și Maxim - Pagina 20
Drumuri de Cost Minim și Maxim - Pagina 21
Drumuri de Cost Minim și Maxim - Pagina 22
Drumuri de Cost Minim și Maxim - Pagina 23
Drumuri de Cost Minim și Maxim - Pagina 24
Drumuri de Cost Minim și Maxim - Pagina 25
Drumuri de Cost Minim și Maxim - Pagina 26
Drumuri de Cost Minim și Maxim - Pagina 27
Drumuri de Cost Minim și Maxim - Pagina 28
Drumuri de Cost Minim și Maxim - Pagina 29
Drumuri de Cost Minim și Maxim - Pagina 30
Drumuri de Cost Minim și Maxim - Pagina 31
Drumuri de Cost Minim și Maxim - Pagina 32

Conținut arhivă zip

  • Drumuri de Cost Minim si Maxim.doc

Alții au mai descărcat și

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...

Turbo Pascal - Metoda Backtracking - Tehnica Greedy

Aparitia limbajului Pascal este un raspuns la criza care a aparut in domeniul programarii calculatoarelor , la sfarsitul anilor ’60 . Limitarile...

Grafuri Neorientate

GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...

Referat Ingineria Programarii - Arbori si Grafuri

Problema 1 Fie G un graf conex cu n varfuri. Fiecarui arc (i,j) i se pune in corespondenta un cost c[i][j]. Sa se listeze toti arborii acestui...

Algoritmica Grafurilor

Curs 1 1.Notatii.Definitii Multiset – S multime finita, S!=VID R=(S,r) r:S->N³0, r=functie multiplicitate r:S->{0,1} => def partilor lui S (R)...

Arhitectura Calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

Algoritmi și Structuri de Date

Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...

Elemente de Teoria Grafurilor

ELEMENTE DE TEORIA GRAFURILOR SI ANALIZA DRUMULUI CRITIC •Concepte fundamentale.Modelarea prin grafuri a proceselor economice. •Drumuri de...

Ai nevoie de altceva?