Re: Dúvida grafos e árvore

[Leonidas O Brandao <leo@ime.usp.br>]

Olá

On Mon, 24 Mar 2003, Reginaldo do Prado wrote:

> Oi pessoal.
> 
> Encontrei na rede uma pág bem legal sobre Huffman
> tem até o código (em Delphi) para a criação da
> árvore... vale a pena dar uma olhada.
> 
> http://www.howtodothings.com/showarticle.asp?article=313#frequency

Legal! Olhei a página e parece que a explicação didática está boa. Por
isso incorporei o "link" na seção "Apontadores" da disciplina e também no
item "Código de Huffman" do meu "semário de classe" (seção "Cronograma").

Vale lembrar, que incorporei na apostila uma "tentativa" de demonstração
da otimalidade do cód. de Huffman (pgs 4 e 5 da atual versão apostila - de
24/03/2003).

Se alguém notar alguma deficiência na página e quiser "des-recomendá-la",
avise-me do problema que notou (eu não tenho Windows p/ testar o
código e nem mesmo o Kalix no Linux). Do mesmo modo, se notarem problemas
na minha demonstração avisem-me para eu poder revisá-la.

> A minha dúvida é sobre a pág 2 da apostila Grafos
> e Árvores, no trecho:
> 
> "Componente conexa ... se existem dois caminhos disjuntos,
>  um de u para v e outro de v para u.  Como p.e., em G2,
>  G': VG'={2,3,4}..."
> 
> Ocorre que em G'(subgrafo de G2), formado pelos vértices
> {2,3,4} não se pode estabelecer um par(u,v) tal que possi-
> bilite a existência de (v,u).
> Por acaso onde se lê G2 não seria G1?

Opa, na verdade a definição que eu havia colocado é mais usalmente aceita
para "componentes fortemente conexas". Agora eu corrigi isto na apostila.

> Sobre o teorema enunciado na pág 2.
> Posso concluir que cada vértice é uma componente conexa
> por definição?

Precisamente!! Até incorporei está observação na apostila.

> Até mais,
> 
> Reginaldo.

[]s
Leônidas

 --------------------------------------------------------------------------
 Leônidas de Oliveira Brandão  -  Computer Science Dep. of IME-USP (Brazil)
 leo@ime.usp.br - http://www.ime.usp.br/~leo - +55 (011) 3091 [6298 | 6135] 
 Interessado em Matemática?  Visite o "iMatica":   http://www.matematica.br