Requisito previo: conceptos básicos de teoría de grafos: conjunto 1
1. Paseo:
un paseo es una secuencia de vértices y aristas de un gráfico, es decir, si recorremos un gráfico, obtenemos un paseo.
Nota: Los vértices y los bordes se pueden repetir.
Aquí, 1->2->3->4->2->1->3 es un paseo.
Walk can be open or closed.
Paseo abierto : se dice que un paseo es un paseo abierto si los vértices inicial y final son diferentes, es decir, el vértice de origen y el vértice terminal son diferentes.
Camino cerrado : se dice que un camino es un camino cerrado si los vértices inicial y final son idénticos, es decir, si un camino comienza y termina en el mismo vértice, entonces se dice que es un camino cerrado.
En el diagrama anterior:
1->2->3->4->5->3 es un paseo abierto.
1->2->3->4->5->3->1 es un paseo cerrado.
2. Sendero –
Sendero es un paseo abierto en el que no se repite ningún borde.
El vértice se puede repetir.
Aquí 1->3->8->6->3->2 es un camino
También 1->3->8->6->3->2->1 será un camino cerrado
3. Circuito:
atravesar un gráfico de modo que no se repita un borde, pero se puede repetir el vértice y también se cierra, es decir, es un camino cerrado.
El vértice se puede repetir.
El borde no se puede repetir.
Aquí 1->2->4->3->6->8->3->1 es un circuito.
Circuit is a closed trail. These can have repeated vertices only.
4. Camino –
Es un camino en el que no se repiten vértices ni aristas, es decir, si recorremos un gráfico tal que no repetimos un vértice y tampoco repetimos una arista. Como camino es también sendero, así también es andar abierto.
Vértice no repetido
Arista no repetida
Aquí 6->8->3->1->2->4 es un Camino
5. Ciclo:
recorrer un gráfico de manera que no repitamos un vértice ni repitamos un borde, pero el vértice inicial y final debe ser el mismo, es decir, podemos repetir el vértice inicial y final solo entonces obtenemos un ciclo.
Vértice no repetido
Arista no repetida
Aquí 1->2->4->3->1 es un ciclo.
Cycle is a closed path. These can not have repeat anything (neither edges nor vertices).
Tenga en cuenta que para secuencias cerradas, los vértices inicial y final son los únicos que pueden repetirse.