Graful complet

Exemplu de graf neorientat complet:

Proprietățile grafului complet neorientat

• are un număr maxim de muchii $m$, formula pentru $n$ noduri fiind $m = n*(n-1)/2$;
• este un graf conex și hamiltonian;
• nodurile au grade maxime, egale cu $n-1$ (pentru un graf complet cu $n$ noduri).

Exemplu de graf orientat complet:

Proprietățile grafului complet orientat

• numărul de muchii $m$ este maxim. Pentru un graf orientat cu $n$ noduri, formula este $m = n*(n-1)$;
• este un graf conex;
• gradele interioare și exterioare sunt maxime, egale (fiecare) cu numărul de noduri $n$ din graf minus $1$.