Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice


Acasa » referate » informatica
GRAFURI - Notiuni introductive

GRAFURI - Notiuni introductive




GRAFURI - Notiuni introductive



Metode de reprezentare a grafurilor


Se considera multimile finite X= si multimea U, care este produsul cartezian al multimi X cu ea insasi.

Definitia 1: Se numeste graf o pereche ordonata de multimi (X,U), X fiind o multime finita si nevida de elemente numite varfuri sau noduri, iar U o multime de perechi (submultimi cu doua elemente) din X, numite muchii sau arce.




Multimea X se numeste multimea nodurilor sau varfurilor grafului, iar multimea U se numeste multimea muchiilor sau multimea arcelor.

Un graf va fi notat cu G=(X,U), iar in figura sa, varfurile (nodurile) se vor desena prin cifre sau litere, muchiile prin linii neorientate si arcele prin linii orientate.

Definitia 2: Se spune ca multimea U are proprietatea de simetrie daca si numai daca avand [Xi, Xk] Є U rezulta ca [Xk, Xi] I U.

Definitia 3: Daca multimea U are proprietatea de simetrie, se spune ca graful G=(X, U) este graf neorientat.

Pentru G=(X, U)graf neorientat, o muchie u se noteaza [Xi, Xk] si este o pereche neordonata de varfuri distincte din X (adica Xi, Xk I X si Xi ≠ Xk).

Varfurile Xi si Xk se numesc extremitatile muchiei u si se spune ca Xi si Xk sunt varfuri adiacente.

Daca un varf nu este extremitatea nici uni arc, atunci el se numeste varf izolat.

Considerand muchia u, notata [Xi, Xk], se spune ca varfurile Xi si Xk, sunt incidente cu muchia [Xi, Xk]. De asemenea, despre doua muchii care au o extremitate comuna se numesc incidente. Uneori, prin abuz de limbaj, se mai foloseste notatia [Xi,Xk] IU.

Definitia 4: Daca multimea U nu are proprietatea de simetrie, se spune ca graful G=(X,U) este graf orientat sau directionat sau digraf. Daca G=(X, U) este un graf orientat, muchiile se numesc arce; un arc u se noteaza cu [Xi, Xk] si este o pereche ordonata de varfuri distincte din X (adica Xi, Xk I X si Xi ≠ Xk).



Pentru un arc (Xi, Xk), Xi este numit baza arcului sau originea sau extremitatea initiala, iar Xk este numit varful arcului sau extremitatea finala sau terminala B.

Se spune ca Xk este adiacent lui Xi. Avand arcul (Xi, Xk), se mai spune ca acesta este incident spre exterior cu Xi si incident spre interior cu Xk. Daca un varf nu este nici extremitatea initiala, nici extremitatea finala a vrunui arc, atunci el se numeste varf izolat.

Definitia 5: Se considera graful G=(X, U). Daca U=Ř (multime vida), atunci graful G=(X, U) se numeste graf nul si reprezentarea lui in plan se reduce la figurarea unor puncte izolate.

Definitia 6: Se defineste gradul unui varf x al uni graf G=(X, U) ca fiind numarul muchiilor incidente cu x si se noteaza cu d(x).

Definitia 7: Daca un varf are gradul 0 (nu exista nici o muchie incidenta cu el), atunci el se numeste varf izolat, iar daca are gradul 1 (este incident cu o singura muchie) se numeste varf terminal.


Proprietatea 1: Fie graful G=(X, U) cu n varfuri x1, x2,…, xn si m muchii.

Atunci suma gradelor nodurilor grafurilor este 2m adica:

n

Σ d(Xk)=2m

k=1


Definitia 8: Fie graful G=(X, U) si V U



Graful Gp=(X, V) se numeste graf partial al grafului G=(X, U). se poate spune ca un graf partial se poate obtine pastrand toate nodurile, dar eliminand o parte din muchii. Daca V=U, atunci Gp coincide cu G.

Definitia 9: Fie graful G=(X, U). se numeste graf complementar al grafului G graful G’=(X, U’) cu proprietatea ca doua varfuri sunt adiacente in G’ daca ele nu sunt adiacente in G.

Definitia 10: Fie graful G=(X, U) si Y X. fie V U, unde V contine toate muchiile din U care au ambele extremitati in Y. graful H=(Y, V) se numeste subgraf al grafului G=(X, U).

Se spune ca subgraful H e indus sau generat de multimea de varfuri Y.

Definitia 11: Se considera U=X*XD. Atunci graful G=(X, U)se numeste graf complet si se noteaza Kn (n fiind numarul de varfuri ale grafului). D=

Definitia 12: Graful G=(X, U) se numeste bipartit daca exista doua multimi nevide A si B astfel incat x=A B, A B= si orice muchie u a lui are o extremitate in A si cealalta extremitate in B.

Definitia 13: Graful G=(X, U) bipartit se numeste bipartit complet daca in orice varf xi din A si orice varf xk din B exista muchia [xi, xk].


Metode de reprezentare


1. Lista de adiacente: aceasta metoda este indicata in cazul in care graful are un numar mare de noduri si un numar mic de muchii.

2. Matricea de adiacenta sau matricea asociata grafului G(X, U)

A= (aij) este definita astfel:

| 1, pentru (xi, xj) I U          

Aij=|

| 0, in caz contrar






Politica de confidentialitate







.com Copyright © 2022 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 Proiect didactic Clasa: a-IX-a, Luarea deciziilor
 PROIECT DIDACTIC 3-5 ani dezvoltarea limbajului si a comunicarii orale - „Cine face, ce face”
 PROIECT MOTOR ASINCRON - Determinarea parametrilor schemei echivalente si a caracteristicilor de functionare in regim stabilizat de la gol la sarcina
 TEMA DE PROIECTARE - arbore de masina rotativa

Lucrari de diploma

vezi toate lucrarile de diploma
 PROIECT DE DIPLOMA CHIRURGIE ORO-MAXILO-FACIALA - SUPURATIILE LOJELOR PROFUNDE DE ETIOLOGIE ODONTOGENA
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Atestat la informatica cu tema “gestionarea unui magazin de confectii”
 Proiect atestat electrician constructor - tehnologia montarii instalatiilor electrice interioare
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM

Pasii de realizare a site-ului
OPERATII CU DOSARE (FOLDER) SI FISIERE
Grafica 3D
Translatorul
Tehnologia Informatiei si a comunicatiilor – TIC
Memoria de date de tip EEPROM
Stocarea si manipularea datelor in aplicatii de calcul tabelar
DATE, INFORMATII, CUNOSTINTE, ENTROPIE INFORMATIONALA





Termeni si conditii
Contact
Creeaza si tu