Ciclo (teoria de grafos): diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m ajustes gerais nas citações, outros ajustes usando script |
Adicionado mais conteúdo e removido informação parcialmente incorreta |
||
Linha 1:
[[Ficheiro:Ciclo em um grafo.png|miniaturadaimagem|Exemplo de um grafo contendo dois ciclos: 1-2-4-3-1 e 6-7-5-6.]]
Um '''ciclo''' em [[teoria de grafos]] é
</ref> Um ciclo é uma cadeia simples e fechada.<ref name="furtado">{{citar livro|autor=FURTADO, Antonio Luz|titulo=Teoria dos Grafos|subtitulo=Algoritmos|ano=1973|pagina=6|local=Rio de Janeiro, Guanabara|editora=LTC/Editora da USP|id=CDD 511.2076}}</ref><ref>{{citar livro|autor=BOAVENTURA NETTO, Paulo Oswaldo|titulo=Grafos|subtitulo=Teoria, Modelos Algoritmos|ano=2001|local=São Paulo|pagina=24|editora=Edgard Blücher|isbn= 85-212-0292-X}}</ref>
Em [[grafos]] não direcionados, para configurar um ciclo o caminho precisará de no mínimo três [[Aresta (teoria dos grafos)|arestas]], com o primeiro e último [[Vértice (teoria dos grafos)|vértice]] se coincidindo e todos outros distintos. Em grafos direcionados precisa-se apenas de uma aresta para configurar um ciclo.
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.<ref name=scheinerman/>▼
O comprimento de um ciclo é o número de [[Aresta (teoria dos grafos)|arestas]] que o caminho possui. Um ciclo com comprimento 1, é chamado de [[Laço (teoria dos grafos)|laço]] (loop).
▲O termo ''ciclo'' pode também ser usado para se referir ao [[grafo]] que contém os [[Vértice (teoria dos grafos)|vértices]] e [[Aresta (teoria dos grafos)|arestas]] de um ciclo na definição acima.<ref name="scheinerman" />
== Definição matemática ==
| |||