MO405 - Solução dos Exercícios
propostos em 2002-11-13
resolvidos em 2002-11-18

8.2.1 Mostre que os conjuntos independentes de um grafo não são, necessariamente, os conjuntos independentes de um matróide.

         - Os conjuntos independentes formam um sistema hereditário.

         - Os conjuntos independentes satisfazem a propriedade "Uniformidade"?

            Dado o grafo C5:

8.2.2 Caracterize os grafos nos quais os conjuntos independentes formam a família de conjuntos independentes de um matróide no conjunto de vértices.

São os grafos que não têm P3 induzido, pois no caso abaixo, considerando a>2, o algoritmo guloso pegaria a e não poderia pegar os vértices da ponta (a-1).

Portanto são os grafos onde toda componente conexa é completa.