~ info project ~

Mai 5, 2010

Grafuri orientate – noţiuni de bază

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

Noţiunea de graf orientat.

Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt muchii în graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraş” este neorientat.

Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noţiunea de graf orientat.

Numim graf orientat, o pereche ordonată de mulţimi G=(X,U), unde:

X este o mulţime finită şi nevidă numită mulţimea nodurilor (vârfurilor);

U este o mulţime formată din perechi ordonate de elemente ale lui X, numită mulţimea arcelor (muchiilor)

Observaţii:

Prin noţiunea de perechi ordonate nu trebuie să înţelegem că o muchie este mai mare decât alta, ci pur şi simplu că facem deosebire între o muchie de forma (x,z) şi o alta de forma (y,x). Cu alte cuvinte muchiile sunt diferenţiate prin ordinea de scriere a simbolurilor.

Arcul (x,y) nu este tot una cu arcul (y,x).

Exemplu:

Pentru graful G=(X,U) din figură. avem: X={1, 2, 3, 4} şi U={u1, u2, u3, u4, u5, u6, u7,}= {(1,1), (2,1), (3,2), (2,3), (2,4), (3,4), (3,4)}

arc va fi de forma u= (x,y), unde x se numeşte extremitate iniţială, iar y se  numeşte extremitate finală a arcului. Cu alte cuvinte, “arcul iese din nodul x şi intră în nodul y”. La fel ca la grafurile neorientate, vom spune că nodurile x şi y sunt adiacente, iar arcul u şi nodul x sunt incidente (la fel arcul x şi nodul y). Nodul y se numeşte succesor al lui x, iar nodul x se numeşte predecesor al lui y. Un arc de forma (x,x), care iese din nodul x şi intră tot x, se numeşte buclă.

Exemplu:

În graful din figura de mai sus, avem bucla (1,1).

Într-un graf putem avea două sau mai multe arce identice.

Exemplu:

În graful din figura de mai sus, există două arce identice, u6 = u7 = (3,4)

Definiţie

Se numeşte p-graf, un graf orientat în care numărul arcelor identice este mai mic sau egal cu o valoare dată p.

În cele ce urmează vom analiza numai 1-grafuri fără bucle.

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

Creează un sit web gratuit sau un blog la WordPress.com.

%d blogeri au apreciat asta: