Encontre o menor número de cabos que são necessários para conectar oito computadores a quatro impressoras a fim de
garantir que quatro computadores estejam ligados diretamente a quatro impressoras diferentes. Justifique sua resposta.
garantir que quatro computadores estejam ligados diretamente a quatro impressoras diferentes. Justifique sua resposta.
Passo 1
O enunciado pede o menor número de cabos (arestas) que ligam oito computadores a quatro impressoras de modo que, independentemente de como essas conexões sejam feitas, sempre exista um emparelhamento de tamanho quatro (isto é, quatro computadores ligados a quatro impressoras distintas).
Conteúdo: teoria de emparelhamento em grafos bipartidos e o Teorema de Hall.
Conteúdo: teoria de emparelhamento em grafos bipartidos e o Teorema de Hall.
Passo 2
Modelamos o problema como um grafo bipartido
onde
é o conjunto dos oito computadores (
) e
o das quatro impressoras (
), e cada cabo é uma aresta em
. Queremos o menor
tal que qualquer grafo com esse número de arestas satisfaz Hall, ou seja, admite um emparelhamento que cobre
.
Passo 3
Pelo Teorema de Hall, não existir emparelhamento que cubra todas as impressoras equivale a existir um subconjunto
com
. Se tal
tem
, então suas arestas podem atingir no máximo
computadores, gerando até
arestas. As restantes
impressoras podem se ligar a todos os
computadores, somando
arestas. Logo, qualquer grafo sem emparelhamento de tamanho
satisfaz
Passo 4
Calcular o máximo dessa expressão para
:
s
:
s :
s :
s :
s
s
s
O máximo ocorre em
, dando
arestas num grafo sem emparelhamento de tamanho
.
Passo 5
Para garantir que qualquer escolha de arestas force um emparelhamento de tamanho
, precisamos ter mais arestas do que o máximo sem esse emparelhamento. Portanto, o menor número de cabos é