Laboratório 3- Dúvidas

[Farris]

Caros Professor Meidanis, Priscila e colegas,

ao estudar o algoritmo recomendado pelo professor encontrei dois principais problemas para a implementação do algoritmo.

1) Determinar as faces de um sugrafo G' de G

2) Determinar os fragmentos do subgrafo

Alguém tem alguma dica, ou direção para me ajudar a solucionar esses problemas ?

Obrigado desde já,

Atenciosamente

Lucas

[renato lochetti]

Boa pergunta Lucas!

Realmente esses são os pontos mais pesados do algoritmo. Se tivessemos algo do lemon que ajude, ou mesmo alguma dica pra resolver seria bem legal.

abs!

--
Recebeu esta mensagem porque está inscrito no grupo "mc558_2012s2" dos Grupos do Google.
 
Para publicar uma mensagem neste grupo, envie um e-mail para mc558_...@googlegroups.com.
Para anular a inscrição neste grupo, envie um e-mail para mc558_2012s2...@googlegroups.com.
Para ver este debate na Web, visite https://groups.google.com/d/msg/mc558_2012s2/-/Q_Fqqyzd0EUJ.
Para mais opções, consulte https://groups.google.com/groups/opt_out.
 
 

--
Renato Tadeu Lochetti

Graduando em Ciência da Computação - UNICAMP

(11) 7609-6689

(19) 8821-3510

[Joao Meidanis]

Gente,

Deixa eu dar uns palpites. Ainda nao fiz o meu programinha, entao pode
ser que na pratica as coisas sejam um pouco mais complicadas do que penso
aqui, mas espero que ajude de qualquer forma.

Para as faces, acho que basta guardar cada face como uma lista circular de
vertices. Uma das faces ficara' rotulada ainda como a face externa.

No inicio, o desenho e' apenas um ciclo. Temos entao duas faces com a
mesma lista de vertices. Uma delas e' a externa.

Quando adicionamos um caminho no meio de uma face, ela se tranforma em
duas. Cada uma delas tera' todo o caminho adicionado, e uma parte da face
original. Creio que isto basta para implementar as faces. Para saber se
os vertices de um fragmento estao numa face, basta ver se cada um pertence
'a lista de vertices da face.

Para determinar os fragmentos, lembre que ha' dois tipos de fragmentos. O
primeiro tipo e' so' uma aresta que nao esta' no subgrafo mas cujos
extremos estao no subgrafo. Entendo que este tipo de fragmento e' facil
determinar. Para o segundo tipo, basta pegar os vertices que NAO estao
no subgrafo e as arestas entre eles, e calcular as componentes conexas.
Tem coisa pronta no Lemon para componentes conexas. Ai' tem tambem que
determinar as arestas entre o fragmento e o subgrafo, o que nao e'
conceitualmente dificil.

Abracos,

Joao Meidanis IC-UNICAMP
Institute of Computing Av. Albert Einstein, 1251
University of Campinas, Brazil 13083-852, Campinas, Sao Paulo
http://www.ic.unicamp.br/~meidanis Brazil

On Wed, 26 Sep 2012, renato lochetti wrote:

> Boa pergunta Lucas!

> Realmente esses s�o os pontos mais pesados do algoritmo. Se tivessemos algo

> do lemon que ajude, ou mesmo alguma dica pra resolver seria bem legal.
>
> abs!
>
> Em 25 de setembro de 2012 22:18, Farris <luksf...@gmail.com> escreveu:
> Caros Professor Meidanis, Priscila e colegas,
> ao estudar o algoritmo recomendado pelo professor encontrei dois

> principais problemas para a implementa��o do algoritmo.

>
> 1) Determinar as faces de um sugrafo G' de G
>
> 2) Determinar os fragmentos do subgrafo
>

> Algu�m tem alguma dica, ou dire��o para me ajudar a solucionar esses
> problemas ?
> Obrigado desde j�,
> Atenciosamente
> Lucas
>
> --
> Recebeu esta mensagem porque est� inscrito no grupo "mc558_2012s2" dos

> Grupos do Google.
> �
> Para publicar uma mensagem neste grupo, envie um e-mail para
> mc558_...@googlegroups.com.

> Para anular a inscri��o neste grupo, envie um e-mail para

> mc558_2012s2...@googlegroups.com.
> Para ver este debate na Web, visite
> https://groups.google.com/d/msg/mc558_2012s2/-/Q_Fqqyzd0EUJ.

> Para mais op��es, consulte https://groups.google.com/groups/opt_out.
> �
> �
>
>
>
>
> --
> Renato Tadeu LochettiGraduando em Ci�ncia da Computa��o - UNICAMP
> (11) 7609-6689
> (19) 8821-3510
>
> --
> Recebeu esta mensagem porque est� inscrito no grupo "mc558_2012s2" dos

> Grupos do Google.
> �
> Para publicar uma mensagem neste grupo, envie um e-mail para
> mc558_...@googlegroups.com.

> Para anular a inscri��o neste grupo, envie um e-mail para
> mc558_2012s2...@googlegroups.com.
> Para mais op��es, consulte https://groups.google.com/groups/opt_out.
> �
> �
>
>