¿Cuál es la diferencia entre ciclo, camino y circuito en la Teoría de Grafos?

Question

Actualmente estoy estudiando Teoría de Grafos y quiero saber la diferencia entre Camino, Ciclo y Circuito.

Conozco la diferencia entre Sendero y el ciclo pero ¿Qué significa realmente el Circuito?

Answer 1

En general, un camino es lo mismo que una caminata, que no es más que una secuencia de vértices de tal manera que los vértices adyacentes están conectados por aristas. Piensa en ello como un simple viaje alrededor de un gráfico a lo largo de las aristas sin restricciones.

Algunos libros, sin embargo, se refieren a un camino como un camino "simple". En ese caso, cuando decimos un camino nos referimos a que ningún vértice se repite . No viajamos al mismo vértice dos veces (o más).

Un ciclo es un camino cerrado. Es decir, empezamos y terminamos en el mismo vértice. En el medio, no viajamos a ningún vértice dos veces.

Será conveniente definir las pistas antes de pasar a los circuitos. Los circuitos se refieren a un paseo en el que ninguna arista se repite . (Obsérvese la diferencia entre un sendero y un simple camino)

Circuitos consulte el cerrado que significa que empezamos y terminamos en el mismo vértice.

Answer 2

Diferentes libros tienen diferente terminología, en algunos libros un camino simple significa que ninguna de las aristas se repite y un circuito es un camino que comienza y termina en el mismo vértice, y circuito y ciclo son la misma cosa en estos libros.

Los libros que utilizan el término paseo tienen diferentes definiciones de camino y circuito, aquí, el paseo se define como una secuencia alternada de vértices y aristas de un grafo, un sendero se utiliza para denotar un paseo que no tiene ninguna arista repetida aquí un camino es un sendero sin vértices repetidos, paseo cerrado es un paseo que comienza y termina con el mismo vértice y un circuito es un sendero cerrado.

Answer 3

Creo que estoy un poco en desacuerdo con Kelvin Soh, en el sentido de que parece permitir que un camino repita el mismo vértice, y creo que no es una definición común. Yo diría:

Ruta de acceso: Vértices distintos $v_1,\dots,v_k$ con bordes entre $v_i$ y $v_{i+1}$ , $1 \le i \le k-1$ .

Camino: Una secuencia de vértices no necesariamente distintos $v_1,\dots,v_k$ y una secuencia de aristas $e_1,\dots,e_{k-1}$ tal que $e_i$ conecta $v_i$ y $v_{i+1}$ , $1 \le i \le k-1$ y todos los $e_i$ son distintos.

Ciclo: Vértices distintos $v_1,\dots, v_k$ con bordes entre $v_i$ y $v_{i+1}$ , $1 \le i \le k-1$ y el borde $\{v_1,v_k\}$ .

Circuito: Un recorrido con el mismo primer y último vértice.

Nota: En algunos textos antiguos la palabra circuito se utiliza a veces para significar ciclo.

Answer 4

En un circuito podemos tener vértices repetidos, pero no en un ciclo.

Answer 5

es un camino cerrado sin vértices repetidos.