Se um gráfico GGG estiver conectado e não tiver um caminho com um comprimento maior que kkk , prove que todos os dois caminhos em GGG de comprimento kkk têm pelo menos um vértice em comum. Eu acho que esse vértice comum deve estar no meio dos dois caminhos. Porque se esse não for o caso, podemos...
Acredito que isso seja verdade, mas também não consegui uma prova formal. Mas é verdade que qualquer árvore de abrangência mínima é alcançável aplicando o algoritmo de Kruskal? Da mesma forma, isso é verdade para o algoritmo de Prim? EDIT: Para ser mais preciso, quero saber se é fornecido um MST...
Eu estou procurando o algoritmo O (V + E) para encontrar a redução transitiva dado um DAG. Isso remove o maior número possível de arestas, para que, se você puder alcançar v de u, para v e u arbitrários, ainda possa alcançá-lo após a remoção das arestas. Se este for um problema padrão, indique-me...
Dado um labirinto bidimensional onde você pode dar 4 comandos "mover para cima / baixo / direita / esquerda". Conhecendo o labirinto, mas não onde está a pessoa, como encontrar a sequência mínima de comandos que garante a saída do labirinto? Estou procurando uma única sequência de comandos que...
Sou iniciante (novato em teoria da complexidade computacional) e tenho uma pergunta. Digamos que tenhamos 'Problema do Vendedor Viajante', a seguinte aplicação dos Algoritmos de Dijkstra o resolverá? A partir de um ponto inicial, calculamos a menor distância entre dois pontos. Nós vamos direto ao...
Eu implementei uma classificação topológica com base no artigo da Wikipedia que estou usando para resolução de dependências, mas ele retorna uma lista linear. Que tipo de algoritmo posso usar para encontrar os caminhos
Atualmente, estou lendo a introdução aos algoritmos e vim pelo algoritmo de Johnson, que depende de garantir que todos os caminhos sejam positivos. o algo depende de encontrar uma nova função de peso (w ') que seja positiva para todas as arestas e mantenha a correção das relações de caminhos mais...
Dada uma distribuição de graus, com que rapidez podemos construir um gráfico que segue a distribuição de graus dada? Um esboço de link ou algoritmo seria bom. O algoritmo deve relatar um "não" caso nenhum gráfico possa ser construído e qualquer exemplo, se vários gráficos puderem ser...
Diz- se que um gráfico direcionado é unipático se, para quaisquer dois vértices uuu e no gráfico , houver no máximo um caminho simples de para .vvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Suponha que eu receba um gráfico unipático modo que cada aresta tenha um peso positivo ou negativo, mas não contenha ciclos...
Eu tenho uma pergunta muito genérica a fazer. Está relacionado à pesquisa. Estou interessado na teoria dos grafos. Eu fiz um curso nele. Fiz alguns tópicos relacionados à teoria dos grafos como ponto de vista de fazê-lo como estudante de matemática e também estudei alguns algoritmos de grafos. Vou...
Existe uma maneira de calcular o tamanho de uma correspondência máxima em um gráfico bipartido não ponderado com mais eficiência (por exemplo, mais rápido) do que calcular uma correspondência máxima? É um tiro no escuro, mas geralmente é um problema interessante para evitar cálculos...
Isso pode estar relacionado à ciência cognitiva computacional, mas estou curioso para saber como o processo seguido por algoritmos comuns de busca de caminhos (como A * ) se compara ao processo que os humanos usam em diferentes situações de busca de caminhos (com as mesmas informações). Esses...
Dado o fato de que enumeração - path é um problema # P-complete, poderia haver métodos eficientes que computem (ou pelo menos se aproximem) o comprimento médio do caminho - sem enumerá-los? E se os caminhos tiverem permissão para revisitar vértices?ssstttsssttt Resultados relevantes em gráficos...
Em uma primeira árvore de profundidade, existem as arestas que definem a árvore (ou seja, as arestas que foram usadas no percurso). Existem algumas arestas restantes conectando alguns dos outros nós. Qual é a diferença entre uma aresta cruzada e uma aresta dianteira? Da wikipedia: Com base...
No problema do posto de gasolina, temos nnn cidades {0,…,n−1}{0,…,n−1}\{ 0, \ldots, n-1 \} e estradas entre elas. Cada estrada tem extensão e cada cidade define o preço do combustível. Uma unidade de estrada custa uma unidade de combustível. Nosso objetivo é ir de uma fonte a um destino da maneira...
Eu fiz essa pergunta no StackOverflow. Me pediram para morar aqui. Então aqui está: Preciso de alguns esclarecimentos e informações sobre o algoritmo de Dijkstra versus a primeira pesquisa de largura em gráficos direcionados, se estiverem corretos. O algoritmo de Dijkstra encontra o caminho mais...
No trabalho, fui encarregado de deduzir algumas informações de tipo sobre uma linguagem dinâmica. Reescrevo seqüências de instruções em letexpressões aninhadas , da seguinte maneira: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
Para alguns gráficos, os algoritmos de pesquisa DFS e BFS processam os nós na mesma ordem exata, desde que ambos iniciem no mesmo nó. Dois exemplos são gráficos com caminhos e gráficos em forma de estrela (árvores de profundidade com um número arbitrário de filhos). Existe alguma maneira de...
Eu tenho um problema e acho difícil de NP, mas não posso provar. Aqui está um gráfico de camadas, em que a camada 0 é a camada mais alta e a camada L, a mais baixa. há alguma aresta direcionada entre as camadas, onde uma aresta (A, B) indica que o nó A pode [cobrir] o nó B. E quando A pode cobrir...
Considere um gráfico direcionado GGG no qual é possível adicionar dinamicamente arestas e fazer algumas consultas específicas. Exemplo: floresta com conjunto separado Considere o seguinte conjunto de consultas: arrow(u, v) equiv(u, v) find(u) o primeiro adiciona uma seta u→vvocê→vu→v para o...