Extras din notiță
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
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