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