3. Conceptos fundamentales: vértices y aristas

3.1 Introducción

Un grafo permite describir elementos conectados sin depender de su forma o posición física. Sus dos componentes fundamentales son los vértices y las aristas.

Si representamos una red social, las personas pueden ser vértices y sus amistades, aristas. En un mapa, las ciudades pueden ser vértices y las carreteras, aristas. Elegir correctamente qué representa cada componente es el primer paso para resolver un problema con grafos.

3.2 ¿Qué es un vértice?

Un vértice es una unidad individual del grafo. También suele llamarse nodo. Matemáticamente, todos los vértices forman un conjunto denominado V.

Los nombres A, B, C y D son identificadores. Cada vértice puede guardar además información: una persona puede tener nombre y edad; una ciudad, coordenadas; un servidor, dirección IP y estado.

3.3 ¿Qué es una arista?

Una arista conecta dos vértices y representa una relación entre ellos. El conjunto de todas las aristas se denomina E. Se utiliza la letra E porque proviene del término inglés edges (aristas).

La arista {A, B} indica que A y B están conectados. En este ejemplo usamos relaciones sin dirección: conectar A con B equivale a conectar B con A. Los grafos dirigidos se estudiarán en el próximo tema.

3.4 Grafo, vértices y aristas

Un grafo G queda definido por su conjunto de vértices y su conjunto de aristas.

En un dibujo, la ubicación de los nodos puede cambiar sin alterar el grafo. Lo importante es cuáles vértices existen y cuáles pares están conectados.

3.5 Simulación interactiva: construye un grafo

Utiliza la simulación para experimentar. En Agregar vértice, pulsa sobre un espacio vacío. En Conectar, pulsa dos vértices. También puedes arrastrar los nodos y seleccionarlos para consultar sus conexiones.

Observa que mover un vértice cambia el dibujo, pero no cambia el grafo: las aristas siguen conectando los mismos pares. En cambio, agregar una arista sí modifica su estructura.

3.6 Incidencia y adyacencia

Una arista es incidente en los vértices que conecta. Si existe la arista {A, B}, esa arista incide en A y en B. A su vez, A y B son vértices adyacentes.

3.7 El grado de un vértice

El grado de un vértice indica cuántas aristas inciden en él. En la simulación, selecciona un vértice para ver su grado y la lista de vecinos.

El grado permite detectar nodos muy conectados, extremos de una red o vértices aislados. Este concepto se desarrollará con más detalle en el tema 13.

3.8 Vértices aislados y hojas

Un vértice con grado cero se denomina aislado: pertenece al grafo, pero no está conectado con ningún otro. Un vértice con grado uno suele llamarse hoja, especialmente cuando trabajamos con árboles.

• Grado 0: vértice aislado.
• Grado 1: hoja o extremo.
• Grado 2 o más: participa en varias conexiones.

Agrega un vértice en la simulación y déjalo sin conectar para crear un vértice aislado.

3.9 Representación inicial en JavaScript

Una forma sencilla de almacenar un grafo consiste en usar un arreglo para los vértices y otro para las aristas.

const vertices = ["A", "B", "C", "D"];
const aristas = [
  ["A", "B"],
  ["A", "C"],
  ["B", "D"]
];

function vecinosDe(vertice) {
  return aristas
    .filter(([a, b]) => a === vertice || b === vertice)
    .map(([a, b]) => a === vertice ? b : a);
}

console.log("Vecinos de A:", vecinosDe("A"));
console.log("Grado de A:", vecinosDe("A").length);

Esta representación es fácil de comprender. Más adelante veremos listas y matrices de adyacencia, que ofrecen distintas ventajas según las operaciones necesarias.

3.10 Datos asociados a los vértices y aristas

En programas reales, un vértice suele ser un objeto con propiedades. Las aristas también pueden almacenar información, como una distancia, un costo o el tipo de relación.

const ciudades = [
  { id: "COR", nombre: "Córdoba", habitantes: 1565000 },
  { id: "ROS", nombre: "Rosario", habitantes: 1342000 }
];

const ruta = {
  origen: "COR",
  destino: "ROS",
  distanciaKm: 400
};

console.log(`${ruta.origen} → ${ruta.destino}: ${ruta.distanciaKm} km`);

La estructura matemática sigue siendo un grafo, pero sus datos permiten responder preguntas específicas de la aplicación.

3.11 Cómo elegir vértices y aristas

La elección depende de la pregunta que debe responder el programa. Un mismo sistema puede dar origen a grafos distintos.

No existe una única representación correcta: existe una representación adecuada para la pregunta que queremos resolver.

3.12 Errores comunes

• Confundir la posición visual de un vértice con información propia del grafo.
• Crear un vértice distinto cada vez que aparece el mismo objeto.
• Representar como arista una relación que no es relevante para el problema.
• Suponer que toda relación funciona igual en ambos sentidos.
• Olvidar que un vértice puede existir aunque no tenga aristas.
• Mezclar el identificador de un vértice con sus datos descriptivos.

3.13 Qué debes recordar de este tema

• Los vértices representan los objetos de un grafo.
• Las aristas representan relaciones entre pares de vértices.
• Los conjuntos de vértices y aristas se escriben como V y E.
• Dos vértices unidos por una arista son adyacentes.
• El grado cuenta cuántas aristas inciden en un vértice.
• Mover los nodos en un dibujo no altera las conexiones del grafo.
• La forma de modelar depende del problema que queremos resolver.

3.14 Conclusión

Vértices y aristas forman el vocabulario básico de la teoría de grafos. Con ellos podemos convertir personas, ciudades, archivos o dispositivos en una estructura común y procesable.

En el próximo tema distinguiremos grafos dirigidos y no dirigidos, según si sus relaciones tienen o no un sentido definido.