matematicas discretas

Unidad 2. Grafos y árboles
2.2. Caminos y circuitos
Si se piensan a los vértices de un grafo como ciudades y las aristas como carreteras, un camino corresponde a un viaje que comienza en ciertaciudad, pasa por varias ciudades y termina en alguna ciudad.

A continuación te damos las definiciones formales de caminos y circuitos.
2.2.1. Terminología básica
Definición: Sea G = (N, A, f) undígrafo sencillo. Se dice que una sucesión de aristas es un Camino de G si y sólo si el vértice terminal, vt, de cada arista del camino es el vértice inicial, vi, de la próxima arista del camino.

Unejemplo de camino sería: {(vi1 , vi2), (vi2 , vi3), …, (vik-2 , vik-1), (vik-1 , vik)}
y se puede escribir de la siguiente forma: {(vi1 , vi2 , …, vik-1 , vik)}
• Un camino de un dígrafo conaristas distintas se llama camino sencillo.
• Un camino con vértices diferentes se denomina camino elemental.
• El número de aristas que aparecen en la sucesión de un camino se denomina longitud delcamino.
•



Definición: A un camino que comienza y acaba en un mismo vértice se le denomina circuito o ciclo. Un circuito se denomina sencillo si ninguna arista del circuito aparece más de unavez en el camino y se denomina elemental si no pasa por ningún vértice más de una vez
En un circuito el nodo inicial aparece al menos dos veces aun cuando se trate de un circuito elemental.
Algunoscircuitos presentes en el grafo de
la figura son:

Circuito 1: {1, 2, 3, 8, 1}

Circuito 2: {1, 2, 4, 5, 7, 8, 1}

Circuito 3: {1, 2, 3, 8, 1, 2, 3, 8, 1}


Un grafo sencillo que no tenganingún ciclo/circuito se denomina acíclico, naturalmente, los grafos acíclicos no pueden tener bucles.
La definición de camino requiere que las aristas que aparezcan en la sucesión tengan unvértice inicial y uno terminal bien definidos.
En el caso de un grafo sencillo no-dirigido, una arista está dada por una pareja no ordenada, y cualquiera de los vértices de esa pareja no ordenada se...