6

Preciso argumentar que a solução encontrada após a execução do Algoritmo Guloso de Prim é ótima. Mas não sei como, alguém poderia ajudar?

1 Resposta 1

2

O algoritmo de Prim serve para encontrar a árvore geradora mínima de um grafo, ou seja, uma árvore com o menor peso possível de suas arestas. Fonte: Wikipedia

Ele começa com qualquer nó arbitrário do grafo e coloca na árvore A. Em cada passo seguinte insere a aresta de menor peso que possui exatamente um vértice dentro da árvore A e outro fora de A, repetindo até todos nós serem adicionados.

A forma mais fácil de provar é por contradição. Mas para isso você tem que usar a propriedade do ciclo: "Para qualquer ciclo C do grafo, se o peso de uma aresta [e] do ciclo for maior do que de todas as outras arestas do ciclo, então [e] não pertence à árvore geradora mínima".

  1. Assuma que aresta [e] pertence à árvore geradora mínima T;
  2. Mostre que existe outra árvore geradora T' com custo menor que não utiliza [e];
  3. Conclua que aresta [e] não pode pertencer à árvore geradora mínima T (contradição).

Outra forma de provar é por indução. A hipótese é que a cada iteração do algoritmo, a árvore A é um sub-grafo da árvore geradora mínima T.

  1. Isso é trivial no primeiro passo, pois a árvore A possui apenas um nó e nenhuma aresta, e obviamente este nó precisa estar em T.
  2. Agora suponha que em algum passo nós temos A (subgrafo de T) e o algoritmo de Prim diz para incluir a aresta [e]. Precisamos provar que A U [e] também é uma subárvore de alguma T. Se [e] pertence a T então isso é verdadeiro, pois por indução A é uma subárvore de T e [e] pertence a T, logo A U [e] é uma subárvore de T.
  3. Agora suponha que [e] não pertence a T. Considere o que acontece quando adicionamos [e] à T. Isso cria um ciclo. Como [e] tem um vértice em A e um vértice fora de A (pois o algoritmo adicionou), tem que existir um aresta [e'] neste ciclo que possui exatamente um vértice em A. O algoritmo podia ter adicionado [e'], mas resolveu inserir [e], o que significa que o peso(e) <= peso (e'). Então se adicionamos [e] na árvore T e removemos [e'] nós acabamos com uma nova árvore T' cujo peso é <= ao peso de T e que contém [e]. Isso mantém a indução, e prova o teorema.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .