MO640 - Exercícios - Para 2004-10-11

Considere a instância do problema de uns consecutivos apresentada na Figura 1 do artigo de Meidanis, Porto e Telles, 1998. Construa a árvore PQR correspondente a esta instância. Determine as coleções C barra, C ortogonal e a interseção de ambas.
Para cada inteiro n >= 1, achar uma árvore PQR T_n e um conjunto S_n tais que |S_n| = 2 e a adição de S_n a T_n produza uma árvore com pelo menos n nós a mais ou a menos que T_n.
Tome U=abcdefghijk, e C={def, efghijk, gh, ijk, ghi}, que dão origem à árvore da Figura 3 do artigo de Booth e Leuker, 1976. Usando S=ghijk, faça a decomposição da instância original do problema, conforme descrito na Seção 4.2 do artigo de Meidanis, Porto e Telles, 1998.