Re: Duvida no exercicio 13 da lista

[Leo Ueda <lkueda@yahoo.com>]

Yoshiharu Kohayakawa wrote:
> 
> Fabio Kimura wrote (on 22 Mar 2000):
>  > On Tue, 21 Mar 2000, Lucas A. Meyer wrote:
>  >
>  > > Cara Lista,
>  > >
>  > >    Alguém conseguiu fazer o exercício 13? Me dá uma dica?
>  > >
>  > >    Não consegui imaginar nenhuma maneira que não dependa de olhar cada
>  > > um dos arcos.
>  >
>  >      Também não consegui imaginar nenhuma outra, mas acho que consigo
>  > provar que m<n (m=|arcos|, n=|vertices|), pois quando m>=n eu tenho um
>  > circuito, e neste caso o algoritmo deveria parar, na pior das hipóteses,
>  > com n=m, neste caso, O(2n)=O(n). Isto está correto, Yoshi?
> 
> Será que respondo...?  Pode perder a graça...  e, ademais, saber se algo
> (possivelmente) suspeito está correto ou não é também um bom exercício.
> 

Acho que isso é verdade. Como o grafo é não orientado, se tiver n ou mais
arestas, certamente há um circuito. Se fizermos uma busca em profundidade, por
exemplo (olhando para cada uma das arestas), encontraremos um circuito depois de
analisar no máximo n arestas. Apesar de olharmos para cada aresta, nunca
precisaremos olhar para mais do que n delas, então a complexidade dessa parte do
algoritmo depende de n e não de m.

Leo

> Boa sorte!  Yoshi
> 
>  > --------------------------------------------------
> [...]

__________________________________________________
Do You Yahoo!?
Talk to your friends online with Yahoo! Messenger.
http://im.yahoo.com