Graf complet
Fie G=(X,U) un graf, fie orientat, fie neorientat.
Un graf care are toate muchiile posibile (card(U)=max) se numește graf complet.
Proprietățile și formulele pentru graful complet diferă în funcție de tipul de graf:
Graf complet neorientat
Exemplu de graf complet neorientat:
Proprietățile grafului complet neorientat
- Are un număr maxim de muchii, formula pentru n noduri fiind n*(n-1)/2;
- Este un graf conexÎntr-un graf conex orice 2 noduri sunt unite între ele printr-un lanț., eulerianGraful eulerian conține un ciclu ce parcurge toate muchiile grafului. și hamiltonianGraful hamiltonian conține un ciclu ce trece prin toate nodurile grafului.;
- Nodurile au grade maxime, egale cu n-1 pentru un graf cu n noduri.
Graf complet orientat
Exemplu de graf complet orientat:
Proprietățile grafului complet orientat
- Are un număr maxim de muchii, formula pentru n noduri fiind n*(n-1);
- Este un graf conexÎntr-un graf conex orice 2 noduri sunt unite între ele printr-un lanț.;
- Gradele interioare și exterioare sunt maxime, egale (fiecare) cu numărul de noduri din graf minus 1.