# Proprietăți: conex, complet, hamiltonian, eulerian

> Pagina: https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate/graf-proprietati
> Markdown: https://bacalaurescu.ro/informatica/lectii/grafuri-neorientate/graf-proprietati.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

Componente conexe, graf complet, cicluri hamiltoniene și euleriene.

## Graf conex

Un graf e **conex** dacă între oricare două noduri există un lanț.

O **componentă conexă** e un subgraf conex maximal: nu mai poți adăuga niciun nod fără să pierzi conexitatea. Un graf neconex are cel puțin două componente.

## Graf complet

Un graf complet $K_n$ are muchie între **oricare două** noduri distincte.

$$m = \frac{n(n-1)}{2}$$

Fiecare nod are gradul $n - 1$.

## Graf hamiltonian

Are un **ciclu hamiltonian**: un ciclu elementar care trece prin **toate nodurile**, fiecare exact o dată.

**Condiție suficientă (Dirac)**: dacă $n \geq 3$ și fiecare nod are $d(x) \geq n/2$, graful e hamiltonian. Atenție: e suficientă, nu necesară.

## Graf eulerian

Are un **ciclu eulerian**: un ciclu care parcurge **toate muchiile**, fiecare exact o dată.

**Teoremă (condiție necesară și suficientă)**: un graf conex e eulerian **dacă și numai dacă toate nodurile au grad par**.

Dacă exact **două** noduri au grad impar, graful nu e eulerian, dar admite un **lanț eulerian** între acele două noduri.

> [!RETINE]
> Confuzia clasică: **hamiltonian trece prin toate NODURILE**, **eulerian trece prin toate MUCHIILE**. Criteriul eulerian e simplu și se verifică imediat (toate gradele pare); cel hamiltonian nu are criteriu simplu.

## Greșeli frecvente

1. Se inversează hamiltonian cu eulerian.
2. Se aplică teorema lui Euler pe un graf neconex. Condiția cere graful **conex**.
3. Se crede că teorema lui Dirac e și necesară. Un graf poate fi hamiltonian fără s-o respecte.