15 Aula 15

Prof. Marco Antonio M. Carvalho

Lembretes
¤ Lista de discussão
¤ Endereço:
¤ [e-mail]
¤ Solicitem acesso:
¤ http://groups.google.com/group/programaacao

¤ Página com material dos treinamentos
¤ http://www.decom.ufop.br/marco/extensao/obi/

¤ Repositório online de problemas das edições passadas da OBI
¤ http://br.spoj.com/problems/obi/sort=-7

¤ Moodle
¤ http://programaacao.net.br/login/index.php
2

Avisos

3

Na aula de hoje
¤ Árvore Geradora
¤ Árvore Geradora Mínima
¤ Algoritmo de Prim
¤ Problema Selecionado
¤ Um Problema de Lógica

4

Árvore Geradora

5

Árvore Geradora
¤ Todo grafo G conexo possui uma árvore que contém todos os seus vértices;
¤ Uma árvore geradora de um grafo G é um subgrafo conexo e acíclico que possui todos os vértices originais de G e um subconjunto das arestas originais de G
¤ Em outras palavras, uma árvore geradora é um subgrafo gerador que é uma árvore.

¤ Como consequência das propriedades de uma árvore, todo grafo conexo possui pelo menos uma árvore geradora. 6

7

Árvores Geradoras
Árvore

Geradora

Grafo de exemplo, árvore geradora e uma árvore não geradora.
Grafo de exemplo, árvore geradora e árvore não geradora.

8

Árvore
Florestas

Geradora

¤ Uma floresta é um conjunto de árvores sem vértices
Definições
em comum;
Uma floresta é um conjunto de árvores sem vértices em comum.

¤ Uma floresta geradora é uma floresta que contém
Uma floresta geradora é uma floresta que contém todos os vértices de um grafo. todos os vértices de um grafo.

Grafodedeexemplo exemplo ee florestas, florestas. Aapenas primeiraa floresta geradora. Grafo primeiraé é geradora. 9

Árvore Geradora Mínima

10

Árvore Geradora Mínima
¤ A árvore geradora de custo mínimo é a árvore geradora de menor custo dentre todas as possíveis em um grafo;
¤ Analogamente, a árvore geradora de custo máximo é a árvore geradora de maior custo dentre todas as possíveis em um grafo;
¤ A determinação de ambas as