# Grafuri neorientate: terminologie

> Pagina: https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate/graf-terminologie
> Markdown: https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate/graf-terminologie.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Grafuri neorientate](https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate)
Actualizat: 2026-09-22

Nod, muchie, adiacență, incidență, grad, lanț, ciclu, subgraf și graf parțial.

## Ce este un graf neorientat

Un graf neorientat $G = (V, E)$ are o mulțime de **noduri** (vârfuri) $V$ și o mulțime de **muchii** $E$. O muchie leagă două noduri și **nu are sens**: $[x, y]$ și $[y, x]$ sunt aceeași muchie.

## Terminologia cerută de programă

- **Nod (vârf)**: element al mulțimii $V$.
- **Muchie**: pereche neordonată de noduri distincte.
- **Adiacență**: două noduri sunt adiacente dacă între ele există muchie.
- **Incidență**: o muchie este incidentă cu nodurile pe care le unește.
- **Grad** ($d(x)$): numărul de muchii incidente cu nodul $x$. Un nod cu gradul 0 se numește **izolat**, cu gradul 1 **terminal**.
- **Lanț**: succesiune de noduri în care oricare două consecutive sunt adiacente.
- **Lanț elementar**: lanț în care **niciun nod nu se repetă**.
- **Ciclu**: lanț în care primul nod coincide cu ultimul, cu cel puțin 3 muchii distincte.
- **Ciclu elementar**: ciclu în care nu se repetă niciun nod, în afară de primul și ultimul.
- **Lungime**: numărul de **muchii** din lanț sau ciclu, nu numărul de noduri.
- **Subgraf**: se obține eliminând noduri **și toate muchiile incidente cu ele**.
- **Graf parțial**: se obține eliminând **doar muchii**; nodurile rămân toate.

## Teorema gradelor

$$\sum_{x \in V} d(x) = 2 \cdot m$$

Suma gradelor tuturor nodurilor este dublul numărului de muchii, pentru că fiecare muchie contribuie cu 1 la gradul fiecăruia dintre cele două capete.

**Consecință**: suma gradelor e întotdeauna **pară**, iar numărul nodurilor de grad impar e **par**.

> [!RETINE]
> Diferența subgraf / graf parțial se cere aproape la fiecare examen. **Subgraf: scoți noduri.** **Graf parțial: scoți doar muchii.**

## Greșeli frecvente

1. Se numără lungimea în noduri. Se numără în **muchii**: un lanț cu 4 noduri are lungimea 3.
2. Se confundă subgraful cu graful parțial.
3. Se uită că într-un graf neorientat muchia nu are sens, deci matricea de adiacență e **simetrică**.