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.
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. 3.ª Edición, Springer-Verlag, 2005
Girth -- Wolfram MathWorld.
Datos:Q959831
Agosto 16, 2021
cintura, teoría, grafos, teoría, grafos, cintura, inglés, girth, grafo, longitud, ciclo, más, corto, contenido, dicho, grafo, grafo, posee, ciclos, decir, grafo, acíclico, cintura, define, como, infinita, ejemplo, ciclo, cuatro, vértices, cuadrado, tiene, cint. En teoria de grafos la cintura 1 en ingles girth de un grafo es la longitud del ciclo mas corto contenido en dicho grafo 2 Si el grafo no posee ciclos es decir es un grafo aciclico su cintura se define como infinita 3 Por ejemplo un ciclo de cuatro vertices 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 8Generalizaciones EditarLa cintura par y cintura impar de un grafo son las longitudes del menor ciclo par e impar respectivamente Referencias Editar Reinaldo Giudici y Angeles Bris Introduccion a la teoria de grafos p 60 Ediciones de la Universidad Simon Bolivar R Diestel Graph Theory p 8 3 ª Edicion Springer Verlag 2005 Girth Wolfram MathWorld Datos Q959831Obtenido de https es wikipedia org w index php title Cintura teoria de grafos amp oldid 118018919, wikipedia, wiki, leyendo, leer, libro, biblioteca,
