Un camino es una sucesión de vértices tal que cada uno de sus vértices existe una arista hacia el vértice sucesor.
Dos caminos son independientes si no tienen ningún vértice en común excepto el primero y el último.
Un camino en un multígrafo consta de una sucesión alternada de nodos y segmentos de la forma
v0, e1,v1,e2,v2…………………………………………………en-1,vn-1,en,Vn
En donde cada segmento si es incidente en vi-1 y vi. El número n de segmentos se llama la longitud del camino. Cuando no hay ambigüedad denotamos un camino por una sucesión de segmentos (s1,s2, ……sn) o por sucesión de nodos (v1,v2,….. vn).
Un camino P={v0,v1,v2,….vn) es simple si todos los nodos que forman el camino son distintos pudiendo ser iguales v0 y vn (los extremos del camino).
La longitud de un camino es el número de enlaces que tiene el camino. Por ejemplo (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.
No hay comentarios:
Publicar un comentario