Cadeias e ciclos eulerianos
No primeiro exemplo a seguir, as arestas do grafo dado aparecem
decompostas em três cadeias simples:
- uma cadeia aberta
a=(a1,a2,a3,a4,
a5,a6,a7)
- e dois ciclos
b=(b1,b2,b3,b4,
b5,b6,b7,b8)
e c=
(c1,c2,c3)
Observe que os vértices extremidades da cadeia aberta a (a roxo)
são os únicos que têm grau ímpar.
Estas três cadeias podem ser "ligadas" numa
única cadeia euleriana m , e.g.
m=(a1,
b1,b2,b3,b4,
b5,b6,b7,
c1,c2,c3,
b8,
a2,a3,a4,
a5,a6,a7)
O segundo exemplo, em baixo, tem uma aresta a mais.
As arestas deste grafo dado aparecem
decompostas em três ciclos:
a=(a1,a2,a3,a4,
a5,a6,a7,a8) ,
b=(b1,b2,b3,b4,
b5,b6,b7,b8)
e c=
(c1,c2,c3) .
Novamente estes três ciclos podem ser "ligados" num
único ciclo euleriano q , e.g.
q=(a1,
b1,b2,b3,b4,
b5,b6,b7,
c1,c2,c3,
b8,
a2,a3,a4,
a5,a6,a7,a8)
Dizemos que o grau de um vértice relativo a uma cadeia é
o número de arestas dessa cadeia incidentes no vértice.
Se houver lacetes incidentes no vértice eles são contados
duas vezes tal como na definição de
grau.
Repare que se as arestas de um grafo G se decompõem na união disjunta
dum certo número de ciclos, então o grau de cada vértice
é igual à soma dos seus graus relativos a cada um dos
ciclos em que G se decompõem.
Verifique, nos exemplos acima, que
são pares os graus de todos os vértices relativos a cada um dos
ciclos mencionados. Porquê?
Verifique também, no primeiro exemplo, que relativamente
à cadeia euleriana m
são ímpares apenas os graus das extremidades
dessa cadeia. Porquê?