Extras din curs
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
Conținut arhivă zip
- Grafurile Orientate si Neorientate.doc
Alții au mai descărcat și
INTRODUCERE IN TEORIA GRAFURILOR Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin...
’’ 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...
LISTE SIMPLU ÎNLANTUITE 1. Continutul lucrarii În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si...
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...
Te-ar putea interesa și
Motivaţia lucrării Structurile de date reprezintă modalitatea în care datele sunt dispuse în memoria calculatorului(sau păstrate pe disc)....
1. Introducere 1.1 Ce este un algoritm?Tipuri de algoritmi folositi pentru calcularea drumului optim Scurt istoric: “Originile teoriei...
<<INTRODUCERE>> Procesele desfăşurate într-o activitate organizată nu au loc la întam-plare, ci sunt declanşate de anumite informaţii care...
1. Preliminarii 1.1. Algoritmi Toti algoritmii descrisi în cadrul acestei lucrari folosesc structuri de date de tip graf. Unele descrieri sînt...
8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...
Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...
Lucrarea nr. 1 Structura de arbore. Arbori generalizati 1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se...