Grafurile Orientate și Neorientate

Curs
8.8/10 (5 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 20 în total
Cuvinte : 2748
Mărime: 86.67KB (arhivat)
Cost: Gratis
Tot ce trebuie sa stii despre grafurile orientate si cele neorientate cu figuri si probleme rezolvate

Extras din document

Grafurile

Graf orientat

Un graf orientat reprezinta o pereche ordonata de multimi G=(X,U), unde X este o multime finita si nevida, numita multimea nodurilor, si U este o multime formata din perechi ordonate de elemente ale lui X, numita multimea arcelor.

Exemplu

In graful din fig. 1 multimea nodurilor este X={1, 2, 3, 4, 5, 6, 7} si multimea arcelor este U={u1, u2, u3, u4, u5, u6, u7, u8, u9, u10}={(1,2), (2,3), (3,4), (4,1), (3,5), (5,3), (5,6), (6,7), (7,6), (7,5)}.

Conexitate in grafuri orientate

Un graf G este conex, daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga.

Un lant intr-un graf orientat este un sir de arce {u1, u 2, u3 , &, un} cu proprietatea ca oricare doua arce consecutive au o extremitate comuna. Altfel spus, un lant este un traseu care uneste prin arce doua noduri numite extremitatile lantului, fara a tine cont de orientarea arcelor componente.

Exemplu

Graful este conex pentru ca oricum am lua doua noduri putem ajunge de la unul la celalalt pe un traseu de tip lant. De exemplu, de la nodul 4 la nodul 2 putem ajunge pe traseul de noduri (4,3,2) stabilind astfel lantul {u5, u3}, dar si pe traseul de noduri (4,1,2) stabilind lantul {u6, u2}

Acest graf nu este conex.

Luand submultimea de noduri {1,2,3}, putem spune ca intre oricare doua noduri din aceasta submultime exista cel putin un lant., de exemplu lantul {u1, u2} sau {u3, u1}. La fel stau lucrurile cu submultimea de noduri {4,5,6}. Dar nu ptuem gasi un lant intre un nod din prima submultime si un nod din a doua submultime.

Plecand dintr-un nod al primei submultimi si deplasandu-ne pe arce, nu avem cum sa trecem in a doua submultime pentru ca nu exista nici un arc direct care sa lege cele doua submultimi. De exemplu plecand din nodul 1 putem ajunge in nodul 2 pe traseul {u3, u2}, dar de aici nu putem ajunge mai departe in nodul 4, deci nu exista lant de la 2 la 4.

Preview document

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

Conținut arhivă zip

  • Grafurile Orientate si Neorientate.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...

Sisteme de Prelucrare Grafică

Curs nr. 1 Evolutia graficii: Se pot distinge mai multe etape: - grafica simpla care sa fie printata; - modele sau obiecte care trebuiau...

Curs Practic HTML

Culoarea de fond O culoare poate fi precizata in doua moduri: Printr-un nume de culoare.Sunt disponibile cel putin 16 nume de culori: aqua,...

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?