Preciso da fórmula e maneira (algoritmo) de encontrar todas as possibilidades para navegar em um grafo, com as seguintes características:
- O grafo terá um número n de nodos;
- O grafo é direcionado (setas);
- O grafo não é cíclico, ou seja, as arestas tendem sempre para próximos nodos;
- Existem m tipos de arestas, onde m >= 1;
- Uma aresta 1 consegue atingir o próximo nodo, uma aresta 2 consegue atingir o segundo nodo subsequente (salta o próximo), e assim por diante;
- É importante ressaltar que o último nodo só receberá nodos, e os últimos terão restrição na quantidade de arestas devido a não existirem mais nodos distantes;
Fiz uma figura (meio feia eu sei) pra ajudar no entendimento. Ela tem n=12 nodos, m=3 arestas sendo preta=1, vermelha=2 e azul=3.
Preciso saber todas as formas de navegar no grafo, por exemplo, para a sequencia de arestas haveriam essas possibilidades (e muitas outras é claro):
11111111111
1111111112
1211111111
121111121
2113211
33212
Nota-se que a soma das arestas sempre dará n - 1 (não sei se isso ajuda
)Preciso de uma explicação formal, é para minha dissertação de mestrado.
Desde já agradeço!
![{(0,05)}^{-\frac{1}{2}}=\frac{10}{\sqrt[5]}](/latexrender/pictures/19807748a214d3361336324f3e43ea9a.png "{(0,05)}^{-\frac{1}{2}}=\frac{10}{\sqrt[5]}")
![{(0,05)}^{-\frac{1}{2}}=\frac{10}{\sqrt[2]{5}}](/latexrender/pictures/3d7908e5b4e397bf635b6546063d9130.png "{(0,05)}^{-\frac{1}{2}}=\frac{10}{\sqrt[2]{5}}")
, ou seja, 1 dividido por 20 é igual a 0.05 . Sendo assim, a função final é igual a vinte elevado à meio. ![{0,05}^{-\frac{1}{2}} = {\frac{1}{20}}^{-\frac{1}{2}} = {\frac{20}{1}}^{\frac{1}{2}} = \sqrt[2]{20}](/latexrender/pictures/c0100c6f4d8bdbb7d54165e6be7aff04.png "{0,05}^{-\frac{1}{2}} = {\frac{1}{20}}^{-\frac{1}{2}} = {\frac{20}{1}}^{\frac{1}{2}} = \sqrt[2]{20}")
da seguinte forma:
.
da seguinte forma:
.