Cintura (teoría de grafos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En teoría de grafos, la cintura[1] (en inglés girth) de un grafo es la longitud del ciclo más corto contenido en dicho grafo.[2] Si el grafo no posee ciclos (es decir, es un grafo acíclico), su cintura se define como infinita.[3]

Por ejemplo, un ciclo de cuatro vértices (cuadrado) tiene cintura 4.

Generalizaciones[editar]

La cintura par y cintura impar de un grafo son las longitudes del menor ciclo par e impar, respectivamente.

Referencias[editar]

  1. Reinaldo Giudici y Ángeles Bris, Introducción a la teoría de grafos, p. 60. Ediciones de la Universidad Simón Bolívar
  2. R. Diestel, Graph Theory, p.8. 3.ª Edición, Springer-Verlag, 2005
  3. Girth -- Wolfram MathWorld, http://mathworld.wolfram.com/Girth.html