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

About these ads

Scrie un comentariu »

Niciun comentariu până acum.

Feed RSS pentru acest post. TrackBack URI

Lasă un răspuns

Completeaza detaliile de mai jos sau apasa click pe una din imagini pentru a te loga:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Schimbă )

Twitter picture

You are commenting using your Twitter account. Log Out / Schimbă )

Facebook photo

You are commenting using your Facebook account. Log Out / Schimbă )

Google+ photo

You are commenting using your Google+ account. Log Out / Schimbă )

Connecting to %s

The Rubric Theme. Bloguieşte pe WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: