Camino (teoría de grafos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
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

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.

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

Véase también[editar]