Conceptes Fonamentals i Tipus de Grafs en Teoria de Grafs
Tipus Fonamentals de Grafs
Grafs Bàsics
Graf Nul d'ordre n, Nn
És un graf d’ordre $n$ i mida $0$.
Graf Trivial
És el graf $N_1$ (ordre 1).
Graf Complet d'ordre n, Kn
És un graf d’ordre $n$ amb totes les arestes possibles.
- Mida de $K_n = \frac{n(n-1)}{2}$
Graf Trajecte d'ordre n, Tn = (V, A)
És un graf d’ordre $n$ i mida $n - 1$ amb conjunt d’arestes $A = \{x_1x_2, x_2x_3, \dots, x_{n-1}x_n\}$.
- Grau mínim $\delta(T_n) = 1$ i grau màxim $\Delta(T_n) = 2$.
Graf Cicle d'ordre n, n >= 3, Cn = (V, A)
És un graf d’ordre $n$ i mida $n$ amb conjunt d’arestes $A = \{x_1x_2, x_2x_3, \dots, x_{n-1}x_n, x_nx_1\}$.
- Grau mínim i màxim: $\delta(C_n) = \Delta(C_n) = 2$.
Graf Roda d'ordre n, n >= 4, Wn = (V, A)
És un graf d’ordre $n$ i mida $2n