Ciclo (teoria de grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Um ciclo em teoria de grafos é "um passeio de comprimento mínimo três, em que o primeiro e o último vértice coincidem, mas nenhum outro vértice é repetido" [1] . Um ciclo é uma cadeia simples e fechada[2] [3] . Um ciclo é uma cadeia fechada[2] .

O termo ciclo pode também ser usado para se referir ao grafo que contém os vértices e arestas de um ciclo na definição acima[1] .

Definição matemática[editar | editar código-fonte]

Matematicamente: Seja G um grafo. Um ciclo em G é um caminho

{v1, v2, . . ., vk, vk+1}

sendo

v1 = vk+1, 3 ≤ k[4]

Referências

  1. a b SCHEINERMAN, Edward (2011). Matemática Discreta. Uma Introdução 2ª ed. (São Paulo: Cengage Learning). p. 473. 
  2. a b FURTADO, Antonio Luz (1973). Teoria dos Grafos. Algoritmos (Rio de Janeiro, Guanabara: LTC/Editora da USP). p. 6. CDD 511.2076. 
  3. BOAVENTURA NETTO, Paulo Oswaldo (2001). Grafos. Teoria, Modelos Algoritmos (São Paulo: Edgard Blücher). p. 24. ISBN 85-212-0292-X. 
  4. SZWARCFITER, Jayme Luiz (1988). Grafos e algoritmos computacionais (Rio de Janeiro: Campus). ISBN 85-7001-341-8.