Considere o seguinte grafo planar topológico
G de ordem 16.
Este grafo tem três tipos de arestas, paralelas aos
vectores v, h e
d, a que chamaremos respectivamente:
arestas verticais, arestas horizontais e
arestas diagonais.
Chamaremos caminho a uma cadeia de G onde
as arestas sejam percorridas na mesma direcção e sentido dos
vectores acima. Conhecida a extremidade inicial,
cada caminho fica univocamente descrito por uma palavra
no alfabeto {V,H,D},
isto é por uma sequência de letras neste conjunto.
- Dados três números inteiros p,
q e r,
quantas palavras, neste alfabeto de três letras, se
podem escrever usando p vezes a letra
V, q vezes a letra
H e r vezes a letra
D?
- Para que valores de p,
q e r as palavras
da alínea anterior descrevem caminhos ligando os
vértices A e C?
- Quantos caminhos existem com extremidade inicial no vértice
A e extremidade final em
C?
- Quantos caminhos de comprimento 3 existem?