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
computadores de um lado e
impressoras do outro, de modo que se garanta sempre a existência de
computadores conectados a
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
, a cobertura m’inima deve ter tamanho no m’aximo
. Denotemos por
uma cobertura de v’ertices com
.
Passo 3
Se
, então todas as arestas devem incidir em algum vértice de
. Sejam
computadores em
e
impressoras em
. O número de arestas máximo ocorre quando todas as possíveis arestas incidentes a
estão presentes, ou seja
Como há
computadores e
impressoras, tem-se
Basta maximizar
para
. Um cálculo rápido mostra que o máximo ocorre em
, dando
Isto corresponde ao caso em que
são
impressoras e todas as
computadores estão ligados a elas.
Passo 4
Concluímos que é possível ter até
cabos sem garantir um matching de tamanho
. Logo, com
cabos qualquer grafo bipartido com
computadores e
impressoras obrigatoriamente terá um matching de tamanho
, ou seja,
computadores acessando
impressoras distintas.