Grados y representación matricial
Aquí conectamos el dibujo del grafo con herramientas “de cálculo”: grados y matrices.
Grado en grafos no dirigidos
El grado de un vértice \(v\) (en grafo no dirigido) es el número de aristas incidentes:
Lema del saludo (teorema fundamental)
En cualquier grafo no dirigido:
Consecuencia típica
El número de vértices de grado impar siempre es par.
Ejemplo 1 — Contar aristas con el lema del saludo
Supón que un grafo tiene grados (ordenados) \(\{3,3,2,2,2\}\).
Entonces
Grados en dígrafos
En un dígrafo distinguimos:
- Grado de salida: \(\delta^+(v)\) = número de arcos que salen de \(v\).
- Grado de entrada: \(\delta^-(v)\) = número de arcos que entran en \(v\).
Definiciones útiles:
- Fuente: \(\delta^-(v)=0\).
- Sumidero: \(\delta^+(v)=0\).
Ejemplo 2 — Fuente y sumidero
Sea \(E=\{a\to b,\ a\to c,\ a\to d,\ b\to c,\ d\to c,\ e\to a,\ e\to d\}\).
- Salidas: \(\delta^+(a)=3,\ \delta^+(b)=1,\ \delta^+(c)=0,\ \delta^+(d)=1,\ \delta^+(e)=2\).
- Entradas: \(\delta^-(a)=1,\ \delta^-(b)=1,\ \delta^-(c)=3,\ \delta^-(d)=2,\ \delta^-(e)=0\).
Conclusión: \(e\) es fuente y \(c\) es sumidero.
Matriz de adyacencia
Si numeramos los vértices \(V=\{v_1,\dots,v_n\}\), la matriz de adyacencia es:
- En grafos no dirigidos simples, \(A\) es simétrica.
- La suma de la fila \(i\) (o columna \(i\)) coincide con \(\delta(v_i)\).
Ejemplo 3 — Matriz de adyacencia y grados
Sea \(V=\{1,2,3,4\}\) y \(E=\{12,13,24,34\}\).
Entonces
Sumas por filas: \((2,2,2,2)\), por tanto todos los vértices tienen grado 2.
Matriz de costes (red ponderada)
Una red es un grafo ponderado donde cada arista tiene un peso (coste, distancia, tiempo…).
La matriz de costes \(C=(c_{ij})\) suele definirse como:
- \(c_{ij}=\) coste de ir de \(v_i\) a \(v_j\) si hay conexión.
- \(c_{ij}=\infty\) si no hay arista.
- \(c_{ii}=0\).
Ojo
Para Dijkstra, los pesos deben ser no negativos.
Ejercicio resuelto
Ejercicio. En un grafo no dirigido, los grados son \(\{1,1,2,2,4\}\). ¿Cuántas aristas tiene?
Solución
Por el lema del saludo: