MO640 - Solução dos Exercícios - Sobre a aula de 2006-06-21

Redigido por Bruno Dilly.

1. Considere uma árvore PQR que consiste em 5 folhas a, b, c, d, e e um único nó interno do tipo P, pai de todas estas folhas, nesta ordem. Seja C uma coleção de conjuntos que dá origem a esta árvore. Calcule C barra (completion de C). Sua resposta depende do C de partida? Se houvesse n folhas, qual seria o tamanho de C barra?

   C barra é igual à coleção de subconjuntos triviais de U, que no caso são: o conjunto vazio, o próprio conjunto U, e os conjuntos unitários. Para cada elemento de U, temos um unitário que possue este elemento de U como seu único elemento.

   C barra não depende do C de partida, apenas da árvore.

   O tamanho de C barra para n folhas é n+2, sendo assim, uma função linear.

2. Considere uma árvore PQR que consiste em 5 folhas a, b, c, d, e e um único nó interno do tipo Q, pai de todas estas folhas, nesta ordem. Seja C uma coleção de conjuntos que dá origem a esta árvore. Calcule C barra (completion de C). Sua resposta depende do C de partida? Se houvesse n folhas, qual seria o tamanho de C barra?

   O colega que resolveu a questão informou que o Teorema 27, enunciado no texto J. Meidanis et al, On the consecutive ones property , possui a resposta relacionada ao cálculo de C barra para as 3 questões. E no caso desta questão, C barra é igual à coleção de conjuntos de consecutivos para permutações no conjunto universo U = {a, b, c, d, e}

   Abaixo seguem os conjuntos "não triviais" de elementos consecutivos de U. Na verdade, na última linha temos {a,b,c,d,e}, que é um dos subconjuntos triviais de U

   ab	bc	cd	de
   abc	bcd	cde
   abcd	bcde
   abcde

   C barra seria, então, a união entre estes conjuntos e os conjuntos triviais

   A resposta também não depende do C de partida

   Por fim, calculou-se o tamanho de C barra para n folhas, que é: (n^2 + n)/2 + 1. Logo, é uma função quadrática.
   Para chegar a este valor, somamos n(n-1)/2, que seria o tamanho da coleção dos consecutivos com dois ou mais alamentos, e n+2, que seria o tamanho da coleção de subconjuntos triviais. Disto, subtraiu 1, pois o subconjunto {a,b,c,d,e} estava presente tanto no primeiro grupo como na coleção de triviais.

3. Considere uma árvore PQR que consiste em 5 folhas a, b, c, d, e e um único nó interno do tipo R, pai de todas estas folhas, nesta ordem. Seja C uma coleção de conjuntos que dá origem a esta árvore. Calcule C barra (completion de C). Sua resposta depende do C de partida? Se houvesse n folhas, qual seria o tamanho de C barra?

   C barra é igual à coleção de todos os subconjuntos de U.

   Assim como nas duas outras questões, a resposta não depende do C de partida.

   O tamanho de C barra caso houvesse n folhas é 2^n. É uma função exponencial.

MO640 Home

© 2006 João Meidanis