-
Acredito que o erro esteja em o vértice representar pares (u,v) quando, na verdade, cada vértice deveria ser um computador, ou seja, apenas v. Pares (u,v) não fazem sentido.
-
"caminho mínimo, que contenha todos os vértices de G, a partir de um dado vértice v." O Caminho mínimo não deve conter todos os vértices do grafo, do contrário não seria mínimo e sim máximo hehehe.
-
Um grafo é representado como um conjunto de pontos (vértices) ligados por retas (arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas". Os grafos são muito úteis na representação de problemas da vida real. Os grafos podem possuir pesos (custos), quer nas arestas, quer nos vértices. um vértice ou nodo é a unidade fundamental da qual os grafos são formados. As arestas são as uniões entre os vértices. Portanto, quem representaria os pares (u,v) de computadores seríam as arestas e não os vértices. Estes representaríam os próprios computadores.
-
Yuri, a questão utilizou com pares (u,v), apenas uma maneria de poder fazer referentes depois a dois computadores u e v. Isso não é o erro da questão.
A solução para o problema não tem nada haver com caminho mínimo e sim COBERTURA MINIMA.
-
O Yuri está correto,
Alguém já leu em alguma bibliografia que um vértice é representado ou pode ser representado por um par de nós?
É exatamente isso que está na questão: "grafo G cujos vértices representem os possíveis pares (u, v) de computadores".
Os vértices são os computadores. As arestas representam os pares de computadores.
-
O erro está nesta parte "grafo G cujos vértices representem os possíveis pares (u, v) de computadores".
São as arestas que representam cada par (u, v) de computadores.
-
Para modelar a rede que conecta todos os computadores em uma sala de escritório com a menor metragem possível de cabos, é adequado utilizar um grafo G PONDERADO, cujos vértices u representem os computadores, cujas ARESTAS representem os possíveis pares (u, v) de computadores e cujos PESOS representem o comprimento dos cabos necessários para ligar os computadores u e v, determinando-se o caminho mínimo, que contenha todos os vértices de G, a partir de um dado vértice v.
-
Acho que o erro da questão está em afirmar que se trata de um problema de caminho mínimo, como o Wagner Salazar disse. O adequado para resolver o problema, na verdade, seria uma árvore geradora mínima.
"Um exemplo de uso de uma árvore de extensão mínima seria a instalação de fibras óticas num campus de uma faculdade. Cada trecho de fibra ótica entre os prédios possui um custo associado (isto é, o custo da fibra, somado ao custo da instalação da fibra, mão de obra, etc). Com esses dados em mãos (os prédios e os custos de cada trecho de fibra ótica entre todos os prédios), podemos construir uma árvore de extensão que nos diria um jeito de conectarmos todos os prédios sem redundância. Uma árvore geradora mínima desse grafo nos daria uma árvore com o menor custo para fazer essa ligação."
Fonte: https://pt.wikipedia.org/wiki/%C3%81rvore_de_extens%C3%A3o_m%C3%ADnima
-
A questão possui diversos erros, mas parei de ler quando ele afirma: "[...] grafo G cujos vértices representem os possíveis pares (u, v) de computadores [...]".
Um vértice, por definição, não pode ser um par. Oras pois.
-
Força Guerreiro!!!!!!