Algoritmica Grafurilor

Imagine preview
(6/10)

Aceasta fituica rezuma Algoritmica Grafurilor.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 13 fisiere doc de 13 pagini (in total).

Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, o poti descarca. Ai nevoie de doar 3 puncte.

Domeniu: Calculatoare

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)

Fisiere in arhiva (13):

  • 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

Alte informatii

An 1 Sem 2 - FMI