A Grafice nedirecționate : Un grafic în care muchiile nu au direcție, adică muchiile nu au săgeți care indică direcția de parcurgere. Exemplu: un grafic al unei rețele sociale în care prieteniile nu sunt direcționale.

Grafice Dirijate : Un grafic în care muchiile au o direcție, adică muchiile au săgeți care indică direcția de parcurgere. Exemplu: un grafic al unei pagini web în care legăturile dintre pagini sunt direcționale.

Grafice ponderate: Un grafic în care muchiile au ponderi sau costuri asociate acestora. Exemplu: un grafic al unei rețele de drumuri în care greutățile pot reprezenta distanța dintre două orașe.

Grafic neponderat s: Un grafic în care muchiile nu au ponderi sau costuri asociate cu acestea. Exemplu: un grafic al unei rețele sociale în care marginile reprezintă prietenii.

Grafice complete: Un grafic în care fiecare vârf este conectat la fiecare alt vârf. Exemplu: un grafic de turneu în care fiecare jucător joacă împotriva fiecărui alt jucător.

Grafice bipartite: Un grafic în care vârfurile pot fi împărțite în două seturi disjunse, astfel încât fiecare muchie conectează un vârf dintr-un set de un vârf din celălalt set. Exemplu: un grafic al solicitantului de locuri de muncă în care vârfurile pot fi împărțite în candidați și locuri de muncă disponibile.

Copaci : Un grafic conectat fără cicluri. Exemplu: Un arbore genealogic în care fiecare persoană este conectată cu părinții lor.

Cicluri : Un grafic cu cel puțin un ciclu. Exemplu: un grafic de partajare a bicicletelor în care bicicletele reprezintă traseele pe care le parcurg bicicletele.

Grafice rare: Un grafic cu margini relativ puține în comparație cu numărul de vârfuri. Exemplu: Un grafic de reacție chimică în care fiecare vârf reprezintă un compus chimic și fiecare muchie reprezintă o reacție între doi compuși.

Graficul dens s: Un grafic cu multe muchii în comparație cu numărul de vârfuri. Exemplu: un grafic al unei rețele sociale în care fiecare vârf reprezintă o persoană și fiecare margine reprezintă o prietenie.

Tipuri de grafice:

1. Grafice finite

Se spune că un grafic este finit dacă are un număr finit de vârfuri și un număr finit de muchii. Un graf finit este un graf cu un număr finit de vârfuri și muchii. Cu alte cuvinte, atât numărul de vârfuri, cât și numărul de muchii dintr-un graf finit sunt limitate și pot fi numărate. Graficele finite sunt adesea folosite pentru a modela situații din lumea reală, în care există un număr limitat de obiecte și relații între

2. Grafic infinit:

Se spune că un grafic este infinit dacă are un număr infinit de vârfuri, precum și un număr infinit de muchii.

3. Grafic trivial:

Se spune că un graf este trivial dacă un graf finit conține un singur vârf și nicio muchie. Un grafic trivial este un grafic cu un singur vârf și fără muchii. Este cunoscut și sub numele de graf singleton sau graf cu un singur vârf. Un grafic trivial este cel mai simplu tip de grafic și este adesea folosit ca punct de plecare pentru construirea de grafice mai complexe. În teoria graficelor, graficele triviale sunt considerate a fi un caz degenerat și nu sunt de obicei studiate în detaliu

shreya ghoshal

4. Grafic simplu:

Un grafic simplu este un grafic care nu conține mai mult de o muchie între perechea de vârfuri. O cale ferată simplă care conectează diferite orașe este un exemplu de grafic simplu.

5. Grafic multiplu:

Orice grafic care conține niște muchii paralele, dar nu conține nicio buclă automată se numește multigraf. De exemplu, o hartă rutieră.

• Margini paralele: Dacă două vârfuri sunt conectate cu mai mult de o muchie, atunci astfel de muchii sunt numite muchii paralele care sunt mai multe rute, dar o destinație.
• Buclă: O muchie a unui grafic care începe de la un vârf și se termină la același vârf se numește buclă sau auto-buclă.

6. Grafic nul:

Un grafic de ordinul n și dimensiunea zero este un grafic în care există doar vârfuri izolate fără muchii care să conecteze vreo pereche de vârfuri. Un grafic nul este un grafic fără muchii. Cu alte cuvinte, este un grafic cu doar vârfuri și fără conexiuni între ele. Un graf nul poate fi denumit și graf fără margini, graf izolat sau graf discret

7. Graficul complet:

Un grafic simplu cu n vârfuri se numește grafic complet dacă gradul fiecărui vârf este n-1, adică un vârf este atașat cu n-1 muchii sau restul vârfurilor din grafic. Un grafic complet se mai numește și Grafic complet.

8. Pseudografic:

Un grafic G cu o buclă automată și câteva muchii multiple se numește pseudograf. Un pseudograf este un tip de graf care permite existența auto-buclelor (muchii care leagă un vârf de el însuși) și a mai multor muchii (mai mult de o muchie care leagă două vârfuri). În schimb, un grafic simplu este un grafic care nu permite bucle sau margini multiple.

9. Graficul obișnuit:

Se spune că un grafic simplu este regulat dacă toate vârfurile graficului G sunt de grad egal. Toate graficele complete sunt regulate, dar invers nu este posibil. Un graf obișnuit este un tip de graf nedirecționat în care fiecare vârf are același număr de muchii sau vecini. Cu alte cuvinte, dacă un grafic este regulat, atunci fiecare vârf are același grad.

10. Grafic bipartit:

Un graf G = (V, E) se spune a fi un graf bipartit dacă setul său de vârfuri V(G) poate fi împărțit în două submulțimi disjunse nevide. V1(G) și V2(G) în așa fel încât fiecare muchie e a lui E(G) să aibă un capăt în V1(G) și un alt capăt în V2(G). Partiția V1 U V2 = V se numește Bipartită a lui G. Aici, în figură: V1(G)={V5, V4, V3} și V2(G)={V1, V2}

11. Grafic etichetat:

Dacă vârfurile și marginile unui grafic sunt etichetate cu nume, dată sau greutate, atunci se numește grafic etichetat. Se mai numește și grafic ponderat.

12. Graficul digraf:

Un grafic G = (V, E) cu o mapare f astfel încât fiecare muchie se mapează pe o pereche ordonată de vârfuri (Vi, Vj) se numește Digraf. Se mai numeste Graficul Dirijat . Perechea ordonată (Vi, Vj) înseamnă o margine între Vi și Vj cu o săgeată îndreptată de la Vi la Vj. Aici în figură: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Subgraf:

Un grafic G1 = (V1, E1) se numește subgraf al unui grafic G(V, E) dacă V1(G) este o submulțime a lui V(G) și E1(G) este o submulțime a lui E(G) astfel încât fiecare muchie a lui G1 are aceleași vârfuri ca și în G.

14. Grafic conectat sau deconectat:

Se spune că graficul G este conectat dacă orice pereche de vârfuri (Vi, Vj) ale unui grafic G este accesibilă unul de la celălalt. Sau se spune că un grafic este conectat dacă există cel puțin o cale între fiecare pereche de vârfuri din graficul G, în caz contrar, este deconectat. Un graf nul cu n vârfuri este un graf deconectat format din n componente. Fiecare componentă constă dintr-un vârf și nicio muchie.

15. Graficul ciclic:

Un grafic G format din n vârfuri și n> = 3 adică V1, V2, V3- – – – Vn și muchii (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1) se numesc grafic ciclic.

lung de înşirat

16. Tipuri de subgrafe:

• Subgraful disjunct al vârfurilor: Orice două grafice G1 = (V1, E1) și G2 = (V2, E2) se spune că sunt disjuncte de vârfuri ale unui grafic G = (V, E) dacă intersecția V1(G1) V2(G2) = nulă. În figură, nu există un vârf comun între G1 și G2.
• Subgraf disjunct de margine: Un subgraf se spune a fi disjunct cu muchia dacă intersecția E1(G1) E2(G2) = nulă. În figură, nu există o margine comună între G1 și G2.

Notă: Subgraful disjun de margine poate avea vârfuri în comun, dar un graf disjun de vârf nu poate avea o muchie comună, astfel încât subgraful disjun de vârf va fi întotdeauna un subgraf disjun de margine.

17. Subgraf de acoperire

Luați în considerare graficul G(V,E) așa cum se arată mai jos. Un subgraf care se întinde este un subgraf care conține toate vârfurile grafului original G care este G'(V’,E’) se întinde dacă V’=V și E’ este o submulțime a lui E.

Deci, unul dintre subgrafele de întindere poate fi așa cum se arată mai jos G’(V’,E’). Are toate vârfurile graficului original G și unele dintre muchiile lui G.

Acesta este doar unul dintre numeroasele subgrafe de acoperire ale graficului G. Putem crea diverse alte subgrafe de acoperire prin diferite combinații de muchii. Rețineți că dacă luăm în considerare un grafic G’(V’,E’) unde V’=V și E’=E, atunci graficul G’ este un subgraf care se întinde pe graficul G(V,E).

Avantajele graficelor:

1. Graficele pot fi folosite pentru a modela și analiza sisteme și relații complexe.
2. Sunt utile pentru vizualizarea și înțelegerea datelor.
3. Algoritmii grafici sunt utilizați pe scară largă în informatică și în alte domenii, cum ar fi analiza rețelelor sociale, logistica și transportul.
4. Graficele pot fi folosite pentru a reprezenta o gamă largă de tipuri de date, inclusiv rețele sociale, rețele de drumuri și internet.

Dezavantajele graficelor:

1. Graficele mari pot fi dificil de vizualizat și analizat.
2. Algoritmii grafici pot fi costisitori din punct de vedere computațional, în special pentru graficele mari.
3. Interpretarea rezultatelor graficului poate fi subiectivă și poate necesita cunoștințe specifice domeniului.
4. Graficele pot fi susceptibile la zgomot și valori aberante, ceea ce poate afecta acuratețea rezultatelor analizei.

Articol înrudit: Aplicații, avantaje și dezavantaje ale graficului