Grafuri neorientate: terminologie (nod/vârf, muchie, adiacență, incidență, grad)
În domeniul teoriei grafurilor, grafurile neorientate reprezintă o componentă esențială în analiza și rezolvarea problemelor complexe. În această lecție, vom explora terminologia de bază asociată cu grafurile neorientate și vom prezenta exemple de algoritmi nerezolvati în limbajul de programare C++.
1. Nod/Vârf
Un nod sau vârf reprezintă o entitate distinctă într-un graf neorientat. Fiecare nod poate fi identificat printr-un nume sau o etichetă unică. De exemplu, într-un graf reprezentând o rețea de socializare, fiecare utilizator poate fi considerat un nod.
2. Muchie
O muchie este o legătură între două noduri într-un graf neorientat. Ea poate fi considerată ca o conexiune sau o relație între cele două noduri. În continuarea exemplului cu rețeaua de socializare, o muchie poate reprezenta o prietenie între doi utilizatori.
3. Adiacență
Adiacența se referă la relația dintre două noduri care sunt conectate printr-o muchie. Dacă două noduri sunt adiacente, înseamnă că există o muchie care le leagă. Această relație poate fi reprezentată printr-o matrice de adiacență sau o listă de adiacență.
4. Incidență
Incidența este o măsură a numărului de muchii care sunt conectate la un anumit nod. Un nod poate avea mai multe muchii incidente sau poate fi izolat, fără nicio muchie incidentă. Gradul unui nod reprezintă numărul de muchii incidente la acel nod.
În concluzie, în această lecție am explorat terminologia de bază asociată cu grafurile neorientate, inclusiv noduri, muchii, adiacență, incidență și grad.