Ce este un graf neorientat?

O mulțime de vârfuri și o mulțime de muchii, fiecare muchie legând două vârfuri. Suma gradelor este dublul numărului de muchii.

Un graf neorientat este o mulțime de vârfuri (noduri) și o mulțime de muchii, fiecare muchie legând două vârfuri. Modelează orice relație simetrică: orașe unite prin șosele, oameni care se cunosc.

Termenii din enunțuri: două vârfuri unite printr-o muchie sunt adiacente. Gradul unui vârf este numărul de muchii care pleacă din el. Un lanț este o succesiune de vârfuri adiacente două câte două, iar un ciclu este un lanț care se întoarce de unde a plecat. Un graf este conex dacă din orice vârf se ajunge în oricare altul.

Aproape toate întrebările de la Subiectul I ies din această teoremă: suma gradelor este dublul numărului de muchii, pentru că fiecare muchie are două capete. De aici: suma gradelor e mereu pară, numărul de vârfuri de grad impar e par, iar un graf complet cu n vârfuri are n(n−1)/2 muchii.

În program, graful se ține de obicei într-o matrice de adiacență: a[i][j] = 1 dacă există muchia [i, j], și a[j][i] = 1 de asemenea.

Lecțiile din capitolul Grafuri și arbori pornesc de la aceste definiții.

Lecția care merge mai departe: Grafuri neorientate: noțiuni