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
[editar | editar a fonte]Circuíto e ciclo
[editar | editar a fonte]- Un circuíto é un camiño non baleiro no que o primeiro e o último vértice son iguais (percorrido pechado).[1]
- Sexa G = (V, E, Φ) un grafo. Un circuíto é un camiño non baleiro (e1, e2, ..., en) cunha secuencia de vértices (v1, v2, ..., vn, v1) .
- Un ciclo ou circuíto simple é un circuíto no que só o primeiro e o último vértice son iguais.[1]
- 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
[editar | editar a fonte]
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
[editar | editar a fonte]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).[2] 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
[editar | editar a fonte]No seu artigo de 1736 sobre as Sete Pontes de Königsberg,[3] amplamente considerado como o nacemento da teoría dos grafos,[4]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.[3]
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
[editar | editar a fonte]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
[editar | editar a fonte]- 1 2 Bender & Williamson 2010, p. 164.
- ↑ Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings". Applied Combinatorics (5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
- 1 2 Euler, Leonhard (1741). "Solutio problematis ad geometriam situs pertinentis". Commentarii Academiae Scientiarum Petropolitanae (en Latin) 8: 128–140 + Plate VIII. en inglés como Solution of a problem in the geometry of position, Michael Behrend.
- ↑ Räz, Tim (2018). "Euler's Königsberg: The explanatory power of mathematics" (PDF). European Journal for Philosophy of Science 8 (3): 331–346. doi:10.1007/s13194-017-0189-x.
Véxase tamén
[editar | editar a fonte] |
Wikimedia Commons ten máis contidos multimedia na categoría: Ciclo |
Bibliografía
[editar | editar a fonte]- Balakrishnan, V. K. (2005). Schaum's outline of theory and problems of graph theory ([Nachdr.] ed.). McGraw–Hill. ISBN 978-0070054899.
- Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.
