Un grafo simple admite como máximo una conexión entre cada par de vértices. Un multigrafo permite representar varias relaciones entre los mismos elementos y, según la definición utilizada, también bucles.
No todos los sistemas conectados necesitan las mismas reglas. En una red de amistad suele bastar una única arista entre dos personas. En una red de transporte, en cambio, dos ciudades pueden estar unidas por varias rutas, compañías o medios diferentes.
Los grafos simples restringen las conexiones para facilitar su análisis. Los multigrafos permiten conservar varias aristas entre el mismo par de vértices y representar más detalles del sistema.
Un grafo simple no contiene aristas paralelas ni bucles. Entre dos vértices diferentes puede existir como máximo una arista.
Esta estructura es suficiente cuando solo interesa saber si una relación existe, sin distinguir cuántas veces aparece o qué variante representa.
Un multigrafo puede contener varias aristas que conectan el mismo par de vértices. Estas conexiones reciben el nombre de aristas paralelas o múltiples.
En algunos textos, los multigrafos también admiten bucles; en otros, los grafos con aristas múltiples y bucles se denominan pseudografos. En programación conviene especificar explícitamente qué reglas permite la estructura.
| Elemento | Descripción | Ejemplo |
|---|---|---|
| Arista común | Une dos vértices diferentes | Ruta entre A y B |
| Aristas paralelas | Varias aristas unen el mismo par | Autobús y tren entre A y B |
| Bucle | Una arista conecta un vértice consigo mismo | Proceso que vuelve a su estado actual |
Un bucle tiene el mismo vértice como origen y destino. En un grafo no dirigido aporta dos incidencias al grado del vértice.
Selecciona dos vértices para agregar una conexión. En modo simple no podrás repetir una arista ni conectar un nodo consigo mismo. En modo multigrafo ambas operaciones están permitidas.
Repite varias veces la conexión A—B en modo multigrafo. Cada curva representa una arista distinta aunque sus extremos sean los mismos.
Un grafo simple es apropiado cuando la existencia de la relación es suficiente y las conexiones repetidas no agregan información útil.
Un multigrafo resulta útil cuando dos objetos pueden estar relacionados de varias maneras independientes.
La multiplicidad de un par de vértices indica cuántas aristas los conectan. En un grafo simple solo puede ser cero o uno; en un multigrafo puede ser mayor.
Cada arista paralela cuenta por separado al calcular el grado. En un grafo no dirigido, un bucle contribuye con dos al grado porque sus dos extremos inciden en el mismo vértice.
Un arreglo de aristas conserva naturalmente las repeticiones. Podemos asignar un identificador y datos propios a cada conexión.
const rutas = [
{ id: 1, origen: "A", destino: "B", medio: "tren" },
{ id: 2, origen: "A", destino: "B", medio: "autobús" },
{ id: 3, origen: "B", destino: "C", medio: "tren" }
];
const entreAyB = rutas.filter(ruta =>
(ruta.origen === "A" && ruta.destino === "B") ||
(ruta.origen === "B" && ruta.destino === "A")
);
console.log("Rutas entre A y B:", entreAyB.length);Antes de agregar una arista a un grafo simple debemos comprobar que no sea un bucle y que la conexión no exista.
const aristas = [["A", "B"], ["B", "C"]];
function puedeAgregar(a, b) {
if (a === b) return false;
return !aristas.some(([x, y]) =>
(x === a && y === b) || (x === b && y === a)
);
}
console.log(puedeAgregar("A", "C"));
console.log(puedeAgregar("B", "A"));
console.log(puedeAgregar("C", "C"));| Pregunta | Modelo recomendado | Motivo |
|---|---|---|
| ¿Solo importa si existe conexión? | Grafo simple | Evita información duplicada |
| ¿Cada conexión posee identidad propia? | Multigrafo | Conserva cada relación |
| ¿Puede un elemento relacionarse consigo mismo? | Modelo que admita bucles | Representa autorrelaciones |
| ¿Las relaciones repetidas pueden resumirse? | Grafo simple ponderado | Un peso puede guardar la cantidad |
A veces un multigrafo puede simplificarse reemplazando varias aristas por una sola con un peso. La decisión depende de si necesitamos conservar la identidad y los datos de cada conexión.
Los grafos simples ofrecen una representación compacta cuando solo importa la existencia de una relación. Los multigrafos conservan conexiones repetidas y permiten modelar sistemas donde cada vínculo tiene identidad propia.
En el próximo tema incorporaremos valores numéricos a las aristas mediante grafos ponderados.