El grado mide cuántas aristas inciden en un vértice. En grafos dirigidos se divide en grado de entrada y grado de salida, revelando cómo se distribuyen las conexiones.
No todos los vértices participan de la misma manera en una red. Algunos no tienen conexiones, otros funcionan como extremos y algunos concentran gran cantidad de relaciones.
El grado permite expresar esa cantidad mediante un número. Es una propiedad local del vértice, pero la distribución de grados también aporta información sobre la estructura completa del grafo.
En un grafo no dirigido, el grado de un vértice v es la cantidad de aristas incidentes en él. Se representa como grado(v), deg(v) o d(v).
Si A está conectado con B, C y D, entonces grado(A) = 3.
En un grafo simple no dirigido, el grado coincide con la cantidad de vecinos distintos.
En multigrafos esta igualdad puede dejar de cumplirse, porque varias aristas paralelas conectan el mismo par de vértices y cuentan por separado.
| Grado | Nombre habitual | Descripción |
|---|---|---|
| 0 | Aislado | No tiene aristas incidentes |
| 1 | Hoja o extremo | Posee una única conexión |
| 2 | Intermedio en muchos caminos | Posee dos conexiones |
| Alto respecto del resto | Centro o hub | Concentra numerosas conexiones |
Selecciona dos vértices para agregar o quitar una conexión. Pulsa un nodo para resaltarlo y observa cómo cambian sus grados. En modo dirigido, el orden define origen y destino.
Grados por vértice
Crea o elimina aristas y comprueba que la suma de grados siempre es dos veces la cantidad de aristas. También observa que la cantidad de vértices de grado impar siempre resulta par.
Cada arista no dirigida contribuye una incidencia a cada uno de sus dos extremos. Por eso, al sumar todos los grados, cada arista se cuenta dos veces.
Esta igualdad se conoce como lema del apretón de manos: si varias personas se saludan por pares, la suma de los saludos individuales duplica la cantidad de saludos realizados.
Como la suma de todos los grados es par, la cantidad de vértices con grado impar también debe ser par.
Esta propiedad fue fundamental en el problema de los puentes de Königsberg y permite descartar ciertos recorridos eulerianos.
En un grafo no dirigido, un bucle aporta 2 al grado de su vértice porque sus dos extremos inciden en el mismo nodo. Cada arista paralela también cuenta por separado.
| Conexión | Aporte al grado |
|---|---|
| Arista común A—B | +1 para A y +1 para B |
| Dos aristas paralelas A—B | +2 para A y +2 para B |
| Bucle A—A | +2 para A |
En un grafo dirigido distinguimos los arcos que llegan de los que salen.
La suma de todos los grados de entrada y la suma de todos los grados de salida coinciden con la cantidad de arcos.
const vertices = ["A", "B", "C", "D"];
const aristas = [["A", "B"], ["A", "C"], ["B", "D"]];
const grados = Object.fromEntries(vertices.map(v => [v, 0]));
for (const [a, b] of aristas) {
grados[a]++;
grados[b]++;
}
console.log(grados);const arcos = [["A", "B"], ["A", "C"], ["C", "B"]];
const entrada = { A: 0, B: 0, C: 0 };
const salida = { A: 0, B: 0, C: 0 };
for (const [origen, destino] of arcos) {
salida[origen]++;
entrada[destino]++;
}
console.log("Entrada:", entrada);
console.log("Salida:", salida);El grado resume la participación de cada vértice dentro del grafo. Además de identificar nodos aislados, extremos y centros, permite deducir propiedades globales mediante la suma de grados.
En el próximo tema estudiaremos caminos, trayectorias y recorridos, construidos como secuencias de vértices y aristas.