miniatura| Un grafo con arestas coloreadas para ilustrar un 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, 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