Encontre o menor número de cabos que são necessários para conectar 100 computadores a 20 impressoras para garantir que 20 computadores possam acessar diretamente 20 impressoras diferentes. (Aqui, as hipóteses sobre os cabos e computadores são as mesmas que as do Exemplo 9.) Justifique sua resposta.

Passo 1

O enunciado pede o menor número de cabos (arestas) num grafo bipartido com 100 computadores de um lado e 20 impressoras do outro, de modo que se garanta sempre a existência de 20 computadores conectados a 20 impressoras distintas. O conteúdo usado será teoria de emparelhamento (matching) em grafos bipartidos, em particular o Teorema de K"onig que relaciona tamanho máximo de matching e tamanho mínimo de cobertura de v’ertices.

Passo 2

Pelo Teorema de K"onig, num grafo bipartido o tamanho de um emparelhamento m’aximo é igual ao tamanho de uma cobertura m’inima de v’ertices. Para n~ao existir um matching de tamanho 20, a cobertura m’inima deve ter tamanho no m’aximo 19. Denotemos por S uma cobertura de v’ertices com \lvert S\rvert =19.

Passo 3

Se \lvert S\rvert=19, então todas as arestas devem incidir em algum vértice de S. Sejam x computadores em S e 19-x impressoras em S. O número de arestas máximo ocorre quando todas as possíveis arestas incidentes a S estão presentes, ou seja
E(x) = (\text{computadores fora de }S)\times(\text{impressoras em }S) +(\text{impressoras fora de }S)\times(\text{computadores em }S).
Como há 100 computadores e 20 impressoras, tem-se
E(x) = (100 - x)\,(19 - x)\;+\;x\,(1 + x).
Basta maximizar E(x) para x=0,1,\dots,19. Um cálculo rápido mostra que o máximo ocorre em x=0, dando
E_{\max} = 100\cdot19 + 0 = 1900.
Isto corresponde ao caso em que S são 19 impressoras e todas as 100 computadores estão ligados a elas.

Passo 4

Concluímos que é possível ter até 1900 cabos sem garantir um matching de tamanho 20. Logo, com 1901 cabos qualquer grafo bipartido com 100 computadores e 20 impressoras obrigatoriamente terá um matching de tamanho 20, ou seja, 20 computadores acessando 20 impressoras distintas.

Resposta

1901 cabos.

Exercícios relacionados