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

Laborator SDA

LISTE SIMPLU ÎNLANTUITE 1. Continutul lucrarii În lucrare sunt prezentate operatiile importante asupra listelor simplu înlantuite si...

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Grafuri

SCURT ISTORIC AL TEORIEI GRAFURILOR Originile teoriei grafurilor se gãsesc în rezolvarea unor probleme de jocuri si amuzamente matematice,care au...

Grafuri Orientate

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

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

Te-ar putea interesa și

Structuri de Date în Limbajul Java

Motivaţia lucrării Structurile de date reprezintă modalitatea în care datele sunt dispuse în memoria calculatorului(sau păstrate pe disc)....

Implementarea Algoritumului Dijkstra pentru Calcularea Drumului Optim Folosind Java

1. Introducere 1.1 Ce este un algoritm?Tipuri de algoritmi folositi pentru calcularea drumului optim Scurt istoric: “Originile teoriei...

Proiect Algoritmi și Structuri de Date

<<INTRODUCERE>> Procesele desfăşurate într-o activitate organizată nu au loc la întam-plare, ci sunt declanşate de anumite informaţii care...

Grafuri

In informatica grafurile pot fi: neorientate si orientate.Un graf neorientat G este o pereche ordonata de multimi (X,U),unde X este o multime...

Manual Grafuri

1. Preliminarii 1.1. Algoritmi Toti algoritmii descrisi în cadrul acestei lucrari folosesc structuri de date de tip graf. Unele descrieri sînt...

Structuri de Date și Analiza Algoritmilor

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

Algoritmi și Structuri de Date

Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...

Îndrumător laborator SDTP

Lucrarea nr. 1 Structura de arbore. Arbori generalizati 1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se...

Ai nevoie de altceva?