Ciclo (teoría de grafos)

[miniatura| Un grafo con arestas coloreadas para ilustrar un [Camiño (teoría de grafos)|camiño pechado, H–A–B–A–H, en verde; un circuíto que é un paseo pechado no que todas as arestas son distintas, B–D–E–F–D–C–B, en azul; e un ciclo que é un camiño pechado no que todos os vértices son distintos, H–D–G–H, en vermello.]]
Na teoría de grafos, un **ciclo** nun grafo é un camiño non baleiro no que só o primeiro e o último vértice son iguais. Un **ciclo orientado** nun grafo orientado é un camiño orientado non baleiro no que só o primeiro e o último vértice son iguais.

Un grafo sen ciclos chámase ***grafo acíclico***. Un grafo orientado sen ciclos orientados chámase  *grafo acíclico orientado*. Un grafo conexo sen ciclos chámase *árbore*.

## Definicións 
### Circuíto e ciclo 
* Un **circuíto** é un camiño non baleiro no que o primeiro e o último vértice son iguais (*percorrido pechado*).

: Sexa  un grafo. Un circuíto é un camiño non baleiro  cunha secuencia de vértices  .

* Un **ciclo** ou **circuíto simple** é un circuíto no que só o primeiro e o último vértice son iguais.
* *O número de vértices n* chámase **lonxitude do circuíto** ou **duración do ciclo**.

Os mesmos conceptos aplican para os **grafos orientados**.

## Ciclo sen cordas 
dereita|miniatura| Neste grafo o ciclo verde A–B–C–D–E–F–A non ten cordas mentres que o ciclo vermello G–H–I–J–K–L–G ten corda. Isto débese a que a aresta {K, I} é unha corda.
Un ciclo sen cordas nun grafo, tamén chamado burato ou ciclo inducido, é un ciclo tal que non hai dous vértices do ciclo ligados por unha aresta que non pertence ao ciclo.

Os ciclos sen cordas pódense utilizar para caracterizar grafos perfectos: polo teorema do grafo perfecto forte, un grafo é perfecto se e só se ningún dos seus buratos ou antiburatos ten un número impar de vértices superior a tres.

## Detección de ciclos 
A existencia dun ciclo en grafos orientados e non orientados pódese determinar se unha busca en profundidade (DFS) atopa unha aresta que apunte a un antepasado do vértice actual (é dicir, contén unha aresta anterior). Todas as arestas anteriores sobre os que salta DFS forman parte dos ciclos. Nun grafo non orientado, a aresta do pai dun nó non debe contarse como unha aresta anterior, pero atopar calquera outro vértice xa visitado indicará unha aresta anterior. 

## Cobertura de grafos por ciclos 
No seu artigo de 1736 sobre as Sete Pontes de Königsberg, amplamente considerado como o nacemento da teoría dos grafos,Leonhard Euler demostrou que, para que un grafo finito non orientado teña un camiño pechado que visite cada aresta exactamente unha vez (o que o converte nun camiño pechado), é condición necesaria e suficiente que todos os vértices estean ligados e teñan grao par en cada vértice. 

A caracterización correspondente para a existencia dun camiño pechado que visita cada aresta exactamente unha vez nun grafo orientado é que o grafo sexafortemente conexo e teña o mesmo número de arestas entrantes e saíntes en cada vértice. En calquera dos casos, o camiño pechado resultante coñécese como camiño euleriano. 

Se un grafo finito non orientado ten grao par en cada un dos seus vértices, independentemente de que estea conectado, entón é posíbel atopar un conxunto de ciclos simples que cobren en conxunto cada aresta exactamente unha vez: este é o teorema de Veblen. 

Cando un grafo conexo non cumpre as condicións do teorema de Euler, pódese atopar un camiño pechado de lonxitude mínima que cobre cada aresta polo menos unha vez en tempo polinómico resolvendo o problema de inspección de rutas.

## Clases de grafos definidos por ciclo 
Varias clases importantes de grafos pódense definir ou caracterizar polos seus ciclos. Estes inclúen:

* Grafo bipartito, un grafo sen ciclos impares (ciclos cun número impar de vértices)
* Grafo de cacto, un grafo no que cada compoñente biconectado non trivial é un ciclo
* Grafo de ciclo, un grafo que consta dun único ciclo
* Grafo de cordas, un grafo no que cada ciclo inducido é un triángulo
* Grafo acíclico orientado, un grafo orientado sen ciclos orientados
* Bosque, un grafo sen ciclos
* Grafo de liña perfecta, un  grafo no que cada ciclo impar é un triángulo
* Grafo perfecto, un grafo sen ciclos inducidos ou os seus complementos de lonxitude impar superior a tres
* Pseudobosque, un grafo no que cada compoñente conexo ten como máximo un ciclo
* Grafo estrangulado, un grafo no que cada ciclo periférico é un triángulo
* Grafo fortemente conexo, un grafo orientado no que cada aresta forma parte dun ciclo
* Grafo sen triángulos, un grafo sen ciclos de tres vértices
* Grafo sen ciclos pares, un grafo sen ciclos pares
* Grafo sen buratos pares, un grafo sen ciclos pares de lonxitude maior ou igual a 6

## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 

### Outros artigos 
* Detección de ciclos
* Ciclo con peso medio mínimo