~ 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.

Feed RSS pentru acest articol. TrackBack URI

Lasă un răspuns

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

WordPress.com Logo

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

Twitter picture

Comentezi folosind contul tău Twitter. Log Out / Schimbă )

Facebook photo

Comentezi folosind contul tău Facebook. Log Out / Schimbă )

Google+ photo

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

Connecting to %s

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

Urmărește

Fiecare nou articol să fie livrat pe email.

%d blogeri au apreciat asta: