Cadeias
Dado um grafo G chama-se
cadeia de G a uma sequência
m=(a1,a2, ... , ak )
de arestas de G
tal que para cada i=2,3,...,k-1,
a aresta ai
tenha com ai+1
uma extremidade em comum, e com
ai-1 a outra extremidade em comum.
O número de arestas k diz-se o
comprimento da cadeia m.
Das duas extremidades de a1
a única que não é comum com a2
diz-se a extremidade inicial da cadeia m.
Analogamente, a única extremidade
de ak que não
é comum com ak-1
diz-se a extremidade final da cadeia m.
Algums tipos de cadeia
Cadeias fechadas
Uma cadeia diz-se fechada se
as suas extermidades inicial e final coincidirem.
Cadeias abertas
Uma cadeia diz-se aberta se
as extermidades inicial e final forem
distintas.
Cadeias simples
Uma cadeia diz-se simples se
não repetir arestas.
Ciclos
Uma cadeia diz-se um ciclo
se fôr uma cadeia simples fechada.
Cadeias elementares
Uma cadeia diz-se
elementar se
não repetir vértices, excepção feita das extremidades
inicial e final que podem coincidir. É claro
que uma cadeia elementar é sempre uma cadeia simples.
Ciclos elementares
Uma cadeia diz-se um ciclo elementar se fôr simultâneamente
um ciclo e uma cadeia elementar.
Inversa de uma cadeia
Dada uma cadeia m chama-se
inversa de m
à cadeia m -1 que se obtem
invertendo a sequência de arestas de m.
O percurso ao longo da cadeia inversa m -1
consiste em percorrer as mesmas arestas de m
mas pela ordem inversa.
Justaposição de cadeias
Dadas duas cadeias m e q, tais que a
extremidade final de m coincide com a
extremidade inicial de q, chama-se
justaposição da cadeia m
com a cadeia q à cadeia m * q que se obtem
juntando a sequência de arestas de q
a seguir à sequência de arestas de m.
O percurso ao longo da cadeia justaposta m * q
consiste em percorrer primeiro as arestas de m
seguindo depois as arestas de q.