Não-amigos independentes

Uma rede social permite que duas pessoas se declarem amigas. Vamos representar cada pessoa por um círculo e a relação de amizade entre duas pessoas como uma linha ligando os dois círculos que representam as pessoas. Um conjunto independente de membros da rede social é formado por pessoas que não têm relação de amizade. A figura abaixo à esquerda mostra os membros de uma rede social. A figura abaixo ao centro mostra, com círculos pintados de preto, um possível conjunto independente, com dois membros. A figura abaixo à direita mostra um outro possível conjunto independente para a mesma rede, com três membros.

Questão 1. Na rede social da figura abaixo, qual o maior número de pessoas num conjunto independente?

1
3
4
6
7

Questão 2. Na rede social da figura abaixo, qual o maior número de pessoas num conjunto independente?

4
5
6
7
8

Submete