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)

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)