Algoritmica Grafurilor

Notiță
6/10 (1 vot)
Domeniu: Calculatoare
Conține 13 fișiere: doc
Pagini : 13 în total
Cuvinte : 7217
Mărime: 126.08KB (arhivat)
Cost: 3 puncte
An 1 Sem 2 - FMI

Extras din document

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)

xÎR <=>r(x)³1

|R|=S(x Î S) r(x)

|R|=p => R este o p-multiparte peste S

2.Puteri ale unei multimi

S!=VID, p ap N³0

p!=0

Sp={( x1,…,xp)/ x1,…,xp ap S} – multimea p-vectorilor peste S. Pt notatia x1…xp =m0, Sp= multimea p-cuvintelor peste S;

S(p)={X/X Í S, |X|=p} – multimea p-partilor lui S

S<p>={X/X este p-multiset peste S} – multimea p-multipartilor peste S

S0=m. cuvintelor fara litere=cuv. vid; S(0)= {Æ}; S<0>= {Æ}

S*= S0U S1U S2U… = toate cuv. peste S (vocabularul peste S)

S(*)=S(0)US(1)…US(n), n=|S|

S<*>= S<0>U S<1>U…

3.Graf

V-mult finita si nevida

V sn mult varfurilor

G=(V,E) sn graf orientat dc arcele au sens

E=multiset peste V2 (sn mult arcelor)

G=(V,E) sn graf neorientat dc arcele nu au sens

E=multiset peste V<2> (sn mult muchiilor)

G=(V,E) sn graf simplu dc E ÍV(2)

E sn mult muchiilor

Exemple

V={a,b,c}

V2={aa,ab,ac,ba,bb,bc,ca,cb,cc}

{exemplu de graf orientat}

V<2> {exemplu de graf neorientat}

V(2) (ex de graf simplu)

Grad

G=(V,E) graf orientat

Fie e ÎE

x e not cu e- (sn origine, vf initial)

y e not cu e+ (sn terminus, vf final)

x Î V. dG-(x)=gradul int al vf x in rap cu graful G

=|{e/e Î E, e+=x}|

dG+(x)=gradul ext al vf x in rap cu graful G

=|{e/e ap E, e-=x}|

dG(x)= dG-(x)+ dG+(x)=gradul vf x(buclele cresc si gradul int si gradul ext)

Preview document

Algoritmica Grafurilor - Pagina 1
Algoritmica Grafurilor - Pagina 2
Algoritmica Grafurilor - Pagina 3
Algoritmica Grafurilor - Pagina 4
Algoritmica Grafurilor - Pagina 5
Algoritmica Grafurilor - Pagina 6
Algoritmica Grafurilor - Pagina 7
Algoritmica Grafurilor - Pagina 8
Algoritmica Grafurilor - Pagina 9
Algoritmica Grafurilor - Pagina 10
Algoritmica Grafurilor - Pagina 11
Algoritmica Grafurilor - Pagina 12
Algoritmica Grafurilor - Pagina 13

Conținut arhivă zip

  • Algoritmica Grafurilor
    • 10AlgortimicaGrafurilor.doc
    • 11AlgortimicaGrafurilor.doc
    • 12AlgortimicaGrafurilor.doc
    • 13 14AlgortimicaGrafurilor.doc
    • 1AlgortimicaGrafurilor.doc
    • 2AlgortimicaGrafurilor.doc
    • 3AlgortimicaGrafurilor.doc
    • 4AlgortimicaGrafurilor.doc
    • 5AlgortimicaGrafurilor.doc
    • 6AlgortimicaGrafurilor.doc
    • 7AlgortimicaGrafurilor.doc
    • 8AlgortimicaGrafurilor.doc
    • 9AlgortimicaGrafurilor.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...

Subiecte Rezolvate Date la Colocviul de Programarea Calculatoarelor

Subiecte date la Colocviul de Programarea Calculatoarelor 1. Sa se afiseze produsul vectorilor AT*B int A[]={1,2,3}; int B[]={4,5,6}; 2. Sa se...

Drumuri de Cost Minim și Maxim

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

Proiectarea Algoritmilor

1. INTRODUCERE ÎN PROIECTAREA ALGORITMILOR 1.1. Definiţii Un algoritm este o metodă de rezolvare pas cu pas a problemelor. O problemă este...

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

Inginerie Software

Fazele dezvoltării unui produs software 1 Ce este ingineria programării? 2. Fazele ingineriei programării 2.1. Faza de analiză 2.2. Faza de...

Ai nevoie de altceva?