Camino (teoría de grafos)

secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente

En Teoría de Grafos, se llama camino a una secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados. Dos vértices pueden estar conectados por varios caminos. El número de aristas dentro de un camino es su longitud. Así, los vértices adyacentes están conectados por un camino de longitud 1, y los segundos vecinos por un camino de longitud 2.

Grafo camino Pn o Pn
Path-graph.svg
P 6 : Grafo camino de orden 6
Vértices n
Aristas n - 1
Radio ⌊ n / 2 ⌋
Diámetro n - 1
Automorfismos 2
Número cromático 2
Índice cromático 2
Propiedades

Si un camino empieza y termina en el mismo vértice se le llama ciclo.

Véase tambiénEditar