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.

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.

Passo 2

Modelamos o problema como um grafo bipartido G=(U,V,E) onde U é o conjunto dos oito computadores ( \lvert U\rvert=8) e V o das quatro impressoras ( \lvert V\rvert=4), e cada cabo é uma aresta em E. Queremos o menor \lvert E\rvert tal que qualquer grafo com esse número de arestas satisfaz Hall, ou seja, admite um emparelhamento que cobre V.

Passo 3

Pelo Teorema de Hall, não existir emparelhamento que cubra todas as impressoras equivale a existir um subconjunto X\subseteq V com \lvert N(X)\rvert<\lvert X\rvert. Se tal X tem \lvert X\rvert=s, então suas arestas podem atingir no máximo \lvert N(X)\rvert\le s-1 computadores, gerando até s\,(s-1) arestas. As restantes (4-s) impressoras podem se ligar a todos os 8 computadores, somando (4-s)\times8 arestas. Logo, qualquer grafo sem emparelhamento de tamanho 4 satisfaz
\lvert E\rvert\le s(s-1)+(4-s)\,8.

Passo 4

Calcular o máximo dessa expressão para s=1,2,3,4:
s =1: 1\cdot0 + 3\cdot8 = 0 +24 = 24
s =2: 2\cdot1 + 2\cdot8 = 2 +16 = 18
s =3: 3\cdot2 + 1\cdot8 = 6 + 8 = 14
s =4: 4\cdot3 + 0\cdot8 = 12 + 0 = 12
O máximo ocorre em s=1, dando \lvert E\rvert_{\max}=24 arestas num grafo sem emparelhamento de tamanho 4.

Passo 5

Para garantir que qualquer escolha de arestas force um emparelhamento de tamanho 4, precisamos ter mais arestas do que o máximo sem esse emparelhamento. Portanto, o menor número de cabos é
24 + 1 = 25.

Resposta

25

Exercícios relacionados