Ruta (teoría de grafos)

Un camino en un gráfico es una secuencia de vértices en la que cada vértice está conectado al siguiente borde.

Definiciones

Sea G un grafo no dirigido . Un camino en G es una secuencia finita o infinita de aristas y vértices [1] ,

que cada dos aristas adyacentes y tienen un vértice común .

Así, se puede escribir

Tenga en cuenta que el mismo borde puede ocurrir varias veces en una ruta. Si no hay aristas que preceden a , entonces se llama vértice inicial de S, y si no hay aristas que siguen a , entonces se llama vértice final de S. Cualquier vértice que pertenece a dos aristas adyacentes se llama interior . Como las aristas y los vértices se pueden repetir en un camino, un vértice interior puede ser el vértice inicial o final.

Si los vértices inicial y final son iguales, el camino se llama cíclico . Un camino se llama cadena , y un camino cíclico se llama ciclo , si cada uno de sus bordes ocurre como máximo una vez (los vértices se pueden repetir). Un camino no cíclico se llama camino simple si no se repite ningún vértice en él. Un ciclo con un final se llama ciclo simple si no es un vértice intermedio en él y no se repiten otros vértices.

Desafortunadamente, esta terminología no está bien establecida. Wilson [2] escribió:

Lo que hemos llamado ruta también se llama camino, secuencia de aristas.

La cadena se llama camino, camino semisimple; una cadena simple: una cadena, un camino, un arco, un camino simple, una cadena elemental; un circuito cerrado - un circuito cíclico, un circuito; ciclo - un contorno, un circuito de contorno, un ciclo simple, un ciclo elemental.

— [3] [4] [5]

Caminos, cadenas y ciclos son conceptos fundamentales en la teoría de grafos y se definen en la parte introductoria de la mayoría de los libros de teoría de grafos. Véase, por ejemplo, Bondi y Marty [6] , Gibbons [7] o Distel [8] .

Diferentes tipos de caminos

Un camino para el cual ningún borde del gráfico conecta dos vértices del camino se llama camino inducido .

Un camino simple que contiene todos los vértices de un gráfico sin repeticiones se conoce como camino hamiltoniano .

Un ciclo simple que contiene todos los vértices de un gráfico sin repeticiones se conoce como ciclo hamiltoniano .

El ciclo obtenido al agregar un borde del gráfico al árbol de expansión del gráfico original se conoce como Ciclo Fundamental.

Propiedades de ruta

Dos caminos son independientes de vértice si no comparten vértices interiores. De manera similar, dos caminos son independientes de los bordes si no comparten bordes interiores.

La longitud de la ruta es el número de aristas utilizadas en la ruta, y las aristas reutilizables se cuentan la cantidad de veces correspondiente. La longitud puede ser cero si el camino consta de un solo vértice.

Un gráfico ponderado asocia cada arista con algún valor ( peso de la arista ). El peso de un camino en un gráfico ponderado es la suma de los pesos de los bordes del camino. A veces, en lugar de la palabra peso , se usa precio o longitud .

Notas

  1. ↑ Ore, 2008 , 2.1 Rutas, circuitos y circuitos simples, p. 34-38.
  2. ↑ Wilson, 1977 , Nuevas definiciones, p. 37.
  3. ↑ Harari, 2003 , Rutas y Conectividad, p. 232.
  4. ↑ Harari, 2003 , Digraphs and Connectivity, p. 232.
  5. ↑ Christofides, 1978 , Capítulo 1. Introducción 2. Caminos y Rutas, p. 13
  6. ↑ Bondy, Murty, 1976 .
  7. ↑ Gibbons, 1985 .
  8. ↑ Distel, 2002 .

Véase también

Literatura

Enlaces