MO405 - Questão para a prova oral

Número: 124

Enunciado: Suponha que um grafo G represente uma rede de fofocas da seguinte forma.  Cada vértice é uma pessoa fofoqueira e cada aresta é uma via de comunicação bidirecional entre duas pessoas. Cada pessoa conhece um segredo que nenhuma outra sabe, e, quando duas pessoas se comunicam através de uma aresta, cada extremidade conta à outra tudo o que sabe.  Seja f(G) o número mínimo de comunicações bidirecionais necessárias para que todas as pessoas de G saibam os segredos de todas as outras.

Com relação a f(C₅), qual das afirmações a seguir é FALSA ?

a) Se excluirmos um canal de comunicação, f aumenta, ou seja,  f(C₅ − e) > f(C₅).

b) É possível diminuir f apenas reorganizando melhor os canais de comunicação: existe um grafo G com n(G) = n(C₅), e(G) = e(C₅) e f(G) < f(C₅).

c) É possível diminuir f incluindo um novo canal de comunicação:  f(C₅ + e) < f(G) para alguma aresta e.

d) Se uma nova pessoa for incluída ao grupo e possuir ao menos um canal de comunicação com as outras fofoqueiras, f aumentará: f(G) > f(C₅) para qualquer grafo conexo G de seis vértices.

e) NDA