Grafuri Orientate

Curs
7/10 (4 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 20 în total
Cuvinte : 3720
Mărime: 23.78KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Andrei Ion
teorie despre grafuri orientate

Extras din document

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U). ca si in cazul grafurilor neorientate, X este multimea varfurilor sau nodurilor grafului.Multimea U este formata din perechi ordonate de elemente distincte din X, numite arce.Orice arc uÎ U va fi notat prin u=(x,y) cu x,yÎX si x¹y.

Spunem ca varful x este extremitatea initiala a arcului u, iar varful y este extremitatea finala a arcului u. Spre deosebire de cazul grafurilor neorientate, notatiile(x,y) si (y,x) vor desemna doua arce diferite.

Daca graful G contine arcul (x,y) vom spune ca varfurile x si y sunt adiacente in G si amandoua sunt incidente cu arcul (x,y). Deci, un graf orientat G poate fi imaginat ca o multime de varfuri, dintre care unele sunt unite doua cate doua prin arce. Un graf orientat poate fi desenat in plan reprezentand varfurile sale prin puncte si arcele prin sageti care sunt orientate de la extremitatea initiala catre extremitatea finala a fiecarui arc.

Graful orientat G=(X,U) unde:

X={ 1,2, …. ,8} si U={(1,2), (2,3), (3,1), (3,2), (2,4), (4,5), (3,5), (6,8), (8,7), (7,8),(7,6)} se reprezinta ca in figura:

Vom nota arcele asa cum se indica in figura , adica u1=(1,2), u2=(3,1),…., u11=(6,8).

Gradul exterior al unui varf x, notat prin d¬+(x), este numarul arcelor de forma (x,y) cu yÎX. Gradul exterior al unui varf x, notat prin d-(x),este numarul arcelor de forma (y,x) cu yÎX.

Un graf partial al unui graf orientat G=(X,U) se defineste in acelasi mod ca si in cazul neorientat. El este un graf G1=(X,V) unde VÌU, deci este graful G insusi sau se obtine din G prin suprimarea anumitor arce.

Si definitia unui subgraf al unui graf orientat G=(X,U) este asemanatoare cu cazul neorientat.Prin definitie , un subgraf al lui G este un graf H=(Y,V), unde YÌX, iar arcele din V sunt toate arcele din U care au ambele extremitati in multimea de varfuri Y.

Deci un subgraf H al unui graf orientat G este graful G insusi sau se obtine din G prin suprimarea anumitor varfuri si a tuturor arcelor incidente cu acestea .

Vom spune ca subgraful H este indus sau generat de multimea de varfuri Y.

Astfel,subgraful grafului G din figura ,indus de multimea de varfuri Y¬1 ={1,2,4,5} are ca multime de arce multimea V1 ={(1,2), (2,4), (4,5)},iar subgraful indus de multimea de varfuri Y2 ={6,7,8} are multimea arcelor V2={(7,6),(6,8),(7,8),(8,7)}.

Un graf orientat este complet daca oricare doua varfuri sunt adiacente.

In timp ce in cazul neorientat un graf complet cu n varfuri este unic determinat, in cazul orientat exista mai multe grafuri complete cu un numar dat de varfuri.Ele se deosebesc fie prin orientarea arcelor , fie prin faptul ca intre doua varfuri oarecare exista un arc sau doua arce de sensuri contrare.

Un lant al unui graf orientat se defineste ca un sir de arce:

L=[u1,u2,…..,up]

Cu proprietatea ca oricare arc uI din acest sir are comuna o extremitate cu ui-1 , iar cealalta extremitate este comuna cu ui+1 pentru orice i=1,...,p-1.

Daca toate arcele lantului L au aceeasi orientare ,care este data de sensul deplasarii de la x0 catre xr lantul se numeste drum.

Deci un drum intr-un graf orientat G=(X,U) este un sir de varfuri notat :

Preview document

Grafuri Orientate - Pagina 1
Grafuri Orientate - Pagina 2
Grafuri Orientate - Pagina 3
Grafuri Orientate - Pagina 4
Grafuri Orientate - Pagina 5
Grafuri Orientate - Pagina 6
Grafuri Orientate - Pagina 7
Grafuri Orientate - Pagina 8
Grafuri Orientate - Pagina 9
Grafuri Orientate - Pagina 10
Grafuri Orientate - Pagina 11
Grafuri Orientate - Pagina 12
Grafuri Orientate - Pagina 13
Grafuri Orientate - Pagina 14
Grafuri Orientate - Pagina 15
Grafuri Orientate - Pagina 16
Grafuri Orientate - Pagina 17
Grafuri Orientate - Pagina 18
Grafuri Orientate - Pagina 19
Grafuri Orientate - Pagina 20

Conținut arhivă zip

  • Grafuri Orientate.DOC

Alții au mai descărcat și

Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...

Grafuri Neorientate - Euleriene

’’ Ideile, si daca sunt abstracte si daca nu, ca sa le poti manui, trebuie sa le ai. Calculatorul, ca sa-si faca treaba, trebuie sa inteleaga...

Grafuri Neorientate

GRAFURI NEORIENTATE NOTIUNI INTRODUCTIVE NOTIUNI DE BAZA DEFINITIE: Se numeste graf neorientat o pereche ordonata de multimi(X,U), X fiind o...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Drumuri de Cost Minim și Maxim

Am ales aceasta tema in scopul de a va arata ca si in informatica exista distante (adica ”drumuri”) atat minime cat si maxime intre elementele unui...

Microsoft Excel

Dupa ce programul Excel a fost instalat, pentru a deschide programul Excel se vor efectua urmatorii pasi: - se face clic pe Start, iar pe ecran va...

Structuri de Date - Liste

3. Structuri elementare de date Inainte de a elabora un algoritm, trebuie sa ne gandim la modul in care reprezentam datele. In acest capitol vom...

Diagramele UML

Diagramele UML Diagrame structurale - Diagrame de clase - Diagrame de obiecte - Diagrame de componente - Diagrame de amplasare Diagrame...

Ai nevoie de altceva?