~ info project ~

Mai 5, 2010

Graful unui vârf. Mulţimile Γ şi ω

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:41 pm
Tags: , , , , ,

Gradul exterior al unui vârf x, notat d*(x), reprezintă numărul arcelor care ies din nodul x, adică numărul arcelor de forma (x,z) ε U.

Analog, se defineşte gradul interior al unui vârf x, notat d-(x), ca fiind numărul arcelor care intră în nodul x (de forma (y,x) ε U).

Exemplu:

În graful reprezentat în figura*, pentru nodul x=2, avem:

d*(2) =3 → există trei arce care ies din nodul 2, şi anume : u2=(2,1), u4=(2,3) şi u5 = (2,4).

d-(2) =1 → în nodul 2 intră un singur arc, în speţă arcul u3=(3,2).

Se mai definesc următoarele mulţimi:

→ mulţimea nodurilor ce constituie extremităţi finale ale arcelor care pleacă din nodul x. Pe scurt, mulţimea succesorilor lui x;

→ mulţimea nodurilor ce constituie extremităţi iniţiale ale arcelor care pleacă din nodul x. Pe scurt, mulţimea predecesorilor lui x;

Exemplu:

În graful din figura, pentru nodul x=2, avem:

– Γ+(2) = {1,3,4} → urmare a faptului că muchiile care pleacă din nodul 2 sunt (2,1), (2,3) şi (2,4), putem spune că mulţimea succesorilor nodului 2 este {1,3,4}.

– Γ(2) = {3} → în nodul 2 intră doar muchia (3,2), deci mulţimea predecesorilor lui 2 conţine doar nodul 3.

ω+(x) = {u = (x,y)| u ε U} → mulţimea arcelor care ies din nodul x;

ω-(x) = {u = (y,x)| u ε U} → mulţimea arcelor care intră în nodul x;

Exemplu:

În graful din figura, pentru nodul 2, avem:

ω+(x) = {(2,1), (2,3), (2,4)}, ω-(x) = {(3,2)}

*figura = graful orientat din postarea anterioară

Lasă un comentariu »

Niciun comentariu până acum.

RSS feed for comments on this post. TrackBack URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

Blog la WordPress.com.

%d blogeri au apreciat asta: