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

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

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

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

Soft pentru Algoritmi Fundamentali de Determinare a Unui Flux de Cost Minim

“Diferența dintre școală și viață? În școală, înveți o lecție, apoi dai un test. În viață, ai de dat un test care te învață o lecție.” (Tom...

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

Algoritmi Polinomiali de Generare a Submulțimilor Discrete Finite

-Introducere- Motivul alegerii acestei lucrări este de a înţelege mai bine cum un algoritm matematic de generare poate fi implementat în cadrul...

Grafuri Celebre

1. Introducere Numeroase situatii din viata cotidiana pot fi modelate cu ajutorul teoriei grafurilor. Teoria grafurilor este o importanta...

Structuri de Date de Tip Graf în C - Caiet de Laborator

LABORATOR 1 Tema1 : Scrieţi programul C care permite crearea şi vizualizarea unui arbore binar ordonat cu vizualizare naturală. 1. Descrierea...

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

Algoritmica grafurilor

Capitolul 1 INTRODUCERE Pentru noţiunile din acest paragraf am consultat Behzad, Chartrand, Foster, Croitoru, Olaru, Tomescu. Alte completări...

Ai nevoie de altceva?