Questao Gomes 21/06/2012

[Joao Meidanis]

Caro Rafael,

Questao muito interessante. A ideia e' boa, mas esta' mal desenvolvida.
Por exemplo, voce nao deixa claro se na contracao deve-se manter arestas
multiplas ou nao. E nao deixa claro o que acontece se acabarem as arestas
antes na (n-2)-esima contracao.

Sobre as arestas multiplas, ao dizer que o algoritmo retorna "as arestas
que ligam estes dois vertices", voce implicitamente parece admitir que
possa haver arestas multiplas ao final. Isto e' mau estilo: deveria
esclarecer logo de cara, ao inves de esperar que o leitor "deduza" sua
intencao ao ler mais adiante. Em todo caso, se admitirmos que ficam
arestas multiplas, ao contrair uma delas podemos formar um loop. Sao
permitidos loops? Outra coisa que nao ficou clara. E o que resulta da
contracao de um loop? Neste caso, nao perdemos um vertice, invalidando
sua suposicao de que sobram exatamente dois vertices ao final.

Em suma, nao pensou direito em todas as consequencias do cenario que voce
mesmo montou. Descarto.

--
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

[Rafael Lopes]

bom, verdd q soh disse q o grafo eh conexo, era p ter dito q eh simples conexo, ate por isso ele tem no mínimo n-1 arestas, entao elas n acabam antes de m-2 iterações. E as contrações n retiram as arestas multiplas, ate pq senao n faria sentido, visto que sempre teria somente uma aresta para retornar.

2012/6/23 Joao Meidanis <meid...@ic.unicamp.br>

--
Rafael Lopes Gomes:
 - Msc. Candidate in Computer Science at University of Campinas (UNICAMP)
 - Member of LRC/UNICAMP and GERCOM/UFPA

 - http://www.lrc.ic.unicamp.br/~rafaellgom

[Joao Meidanis]

Ah, sim. Obrigado por esclarecer, colega Rafael. Mas, mesmo o grafo
comecando como simples, ao longo do processo ele pode se tornar
nao-simples? Ate' mesmo com loops?

--Joao

On Sun, 24 Jun 2012, Rafael Lopes wrote:

> bom, verdd q soh disse q o grafo eh conexo, era p ter dito q eh simples

> conexo, ate por isso ele tem no m�nimo n-1 arestas, entao elas n acabam
> antes de m-2 itera��es. E as contra��es n retiram as arestas multiplas, ate

[Rafael Lopes]

Bom, o objetivo eh esse, loops nao influenciam pq o retorno sao as arestas que ligam os dois vertices, e os multiplos caminhos que surgem representam o corte que vai ser retornado.

2012/6/26 Joao Meidanis <meid...@ic.unicamp.br>

Ah, sim.  Obrigado por esclarecer, colega Rafael.  Mas, mesmo o grafo comecando como simples, ao longo do processo ele pode se tornar nao-simples?  Ate' mesmo com loops?

--Joao

On Sun, 24 Jun 2012, Rafael Lopes wrote:

bom, verdd q soh disse q o grafo eh conexo, era p ter dito q eh simples

conexo, ate por isso ele tem no mínimo n-1 arestas, entao elas n acabam
antes de m-2 iterações. E as contrações n retiram as arestas multiplas, ate