Ciclo (teoría de grafos)

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, en inglés como Solution of a problem in the geometry of position, Michael Behrend. 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

Categoría:Teoría de grafos