Matemáticas | Paseos, Senderos, Senderos, Ciclos y Circuitos en Gráfica

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. 

Publicación traducida automáticamente

Artículo escrito por him0000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *