- Cintura (teoría de grafos)
-
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.
-
El grafo de Petersen tiene cintura 5
-
El grafo de Heawood tiene cintura de 6
-
El grafo de McGee tiene cintura 7
-
El grafo de Tutte–Coxeter tiene cintura 8
Generalizaciones
La cintura par y cintura impar de un grafo son las longitudes del menor ciclo par e impar, respectivamente.
Referencias
- ↑ Reinaldo Giudici y Ángeles Bris, Introducción a la teoría de grafos, p. 60. Ediciones de la Universidad Simón Bolívar
- ↑ R. Diestel, Graph Theory, p.8. 3ra Edición, Springer-Verlag, 2005
- ↑ Girth -- Wolfram MathWorld, http://mathworld.wolfram.com/Girth.html
Categoría:- Anglicismos
-
Wikimedia foundation. 2010.
