Rutas y grafos Ruta Grafo

Una ruta puede verse como un recorrido por un grafo. Los principales algoritmos se basan, por lo tanto, en la teoría de grafos. Teoría de grafos

1. Definición y conceptos

Un grafo es un conjunto de nodos o vértices (que pueden representar, por ejemplo, ciudades) ligados por arcos, que serán las rutas.

He aquí un grafo que representa las estaciones y los vínculos que existen entre ellas (en tren, sin trasbordo):

images/c03f01.PNG

Las estaciones E1 a E6 son los nodos. El arco que va de E5 a E6 indica la presencia de un enlace directo entre estas dos estaciones. Se escribe (E5, E6) o (E6, E5) según el sentido deseado.

Por el contrario, para ir de E1 a E6 no existe ningún enlace directo. Será preciso pasar por E4 o por E5 si se desea realizar un único trasbordo, o por E2 y, a continuación, por E3 con dos trasbordos.

Una ruta permite alcanzar varios destinos unidos entre sí mediante arcos. De este modo, E1-E2-E3-E6 es una ruta de distancia 3 (la distancia es el número de arcos seguidos). Ruta

Hablamos de circuito cuando es posible partir de un nodo y volver a él. Aquí, el grafo contiene varios circuitos, como por ejemplo E1-E4-E5-E1 o E4-E5-E6-E4. Circuito

El orden de un grafo se corresponde con el número de destinos que contiene. Nuestro ejemplo contiene 6 estaciones, se trata por tanto de un grafo de orden 6.

Dos nodos se dice que son adyacentes (o vecinos) si existe un vínculo que permite ir de uno al otro. E5 es, por lo tanto, adyacente...

Si desea saber más, le proponemos el siguiente libro:
couv_DPT2INT.png
60-signet.svg
Versión impresa
20-ecran_lettre.svg
Versión online
41-logo_abonnement.svg
En ilimitado con la suscripción ENI
130-boutique.svg
En la tienda oficial de ENI
Anterior
Presentación del capítulo
Siguiente
Ejemplo en cartografía