MO640 - Exercícios - Para 2004-12-15

Considere o conjunto de rótulos L = {a,b,c,d,e,f,g} e o sistema de cortes que contém todos os cortes triviais e mais os seguintes: {{a,b,c},{d,e,f,g}}, {{a,b,c,d,e},{f,g}}, {{a,b},{c,d,e,f,g}}. Desenhe a árvore correspondente a este sistema de cortes.
Diga qual é a distância entre os seguintes dois sistemas de cortes sobre L = {a,b,c,d,e,f}: S1 = triviais mais {{{a,b},{c,d,e,f}}, {{a,b,c},{d,e,f}}, {a,b,c,d}, {e,f}}} e S2 = triviais mais {{{a,c},{b,d,e,f}}, {{a,b,c},{d,e,f}}, {a,b,c,f}, {d,e}}}. A seguir, mostre um caminho mínimo de um para o outro, e desenhe as árvores correspondentes.