Combinações para navegar em um grafo direcionado não ciclico
04 set 2013, 05:50
Olá,
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!
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!
- Anexos
-
Re: Combinações para navegar em um grafo direcionado não ciclico
05 set 2013, 14:24
Já pensou em adaptar o raciocíonio do cálculo de arranjos sem repetição ao problema?
O grafo está determinado ou aquele que fornece é só um exemplo possível entre outros?
O grafo está determinado ou aquele que fornece é só um exemplo possível entre outros?
Re: Combinações para navegar em um grafo direcionado não ciclico
06 set 2013, 18:41
Não conheço e nem sei se existe (não quero dizer que não exista!) nenhum algoritmo que trate este problema para n vértices (nós) e m tipos de aresta (comprimentos). O problema que apresentas em exemplo é de acessível resolução (bastam realmente alguns minutos para se obter resolução), e a julgar pelo tipo de problema (Problemas de Empacotamento), outros casos com n e m baixos também o serão.
No entanto, um algoritmo generalizador como o que pedes é um problema "respeitável" de matemática discreta ou computacional, que foge ao âmbito dos problemas que podem ser colocados e respondidos no Fórum de Matemática. Provavelmente é trabalho para alguns dias ou talvez semanas. Daí julgo que ninguém se vai ocupar desse trabalho todo apenas por espírito de ajuda.
No entanto, um algoritmo generalizador como o que pedes é um problema "respeitável" de matemática discreta ou computacional, que foge ao âmbito dos problemas que podem ser colocados e respondidos no Fórum de Matemática. Provavelmente é trabalho para alguns dias ou talvez semanas. Daí julgo que ninguém se vai ocupar desse trabalho todo apenas por espírito de ajuda.