Cintura (teoría de grafos)
longitud del ciclo más corto contenido en un grafo / De Wikipedia, la enciclopedia encyclopedia
En teoría de grafos, la cintura[1] (en inglés girth) de un grafo no dirigido 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. Un látice cuadrado tiene cintura 4. Una malla triangular tiene cintura 3. Si un grafo tiene cintura mayor a tres, se dice que es libre de triángulos.
- 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