*36. Suponha que para cada par de cidades em um país, há uma estrada direta conectando-as em uma direção ou na outra. Use a indução matemática para mostrar que há uma cidade que pode ser alcançada a partir de qualquer outra cidade ou diretamente ou através de outra cidade.

Passo 1

Resumindo o enunciado: temos um país com n cidades e, para cada par de cidades, há uma estrada direta ligando-as em uma direção ou na outra. Em termos de grafos, isso é um tournament em n vértices. Precisamos mostrar que existe uma cidade c tal que, para qualquer outra cidade x, existe um caminho dirigido de comprimento no máximo 2 que vai de x até c (isto é, alcança-se c direta ou passando por uma cidade intermediária). Para conseguir isso vamos usar indução matemática para provar antes um lema sobre indegrados em tournaments.

Passo 2

Lema: em qualquer tournament com n vértices existe um vértice cujo indegrado é pelo menos \lfloor(n-1)/2\rfloor.
Prova por indução em n:
  • Caso base n=1: trivial, o único vértice tem indegrado 0 e \lfloor(1-1)/2\rfloor=0.
  • Passo indutivo: suponha o lema verdadeiro para n-1. Dado um tournament T com n vértices, remova uma cidade v; pelo HI existe um vértice u no sub-tournament com
    \deg^-_{T-v}(u)\ge\lfloor(n-2)/2\rfloor.
    Ao reintroduzir v, ou v\to u (então \deg^-_T(u)=\deg^-_{T-v}(u)+1) ou u\to v (então \deg^-_T(u)=\deg^-_{T-v}(u)). Em ambos os casos
\deg^-_T(u)\;\ge\;\lfloor(n-2)/2\rfloor \quad\Longrightarrow\quad \deg^-_T(u)\;\ge\;\lfloor(n-1)/2\rfloor.
Assim o lema vale para n.

Passo 3

Escolha uma cidade c de indegrado \deg^-\text{(c)}=d\ge\lfloor(n-1)/2\rfloor. Defina
S=\{\,u\mid u\to c\},\quad T=\{\,v\neq c\mid c\to v\}.
Então |S|=d e |T|=n-1-d, e como d\ge\lfloor(n-1)/2\rfloor segue |T|\le d.
  • Para cada u\in S há o caminho direto u\to c.
  • Para cada v\in T, note que se todo vértice de S apontasse para v, então \deg^-(v)\ge|S|>d=\deg^-\text{(c)}, contradizendo a maximalidade de c. Logo existe ao menos um u\in S com v\to u, e daí
v\;\to\;u\;\to\;c
é um caminho de comprimento 2 de v até c.

Passo 4

Portanto toda cidade x\neq c alcança c ou diretamente x\in S ou por meio de uma intermediária x\in T, o que mostra que c pode ser atingida de qualquer outra em no máximo dois trechos.

Resposta

Uma cidade c cujo indegrado satisfaz
\deg^-\text{(c)}\;\ge\;\bigl\lfloor\tfrac{n-1}{2}\bigr\rfloor
é alcançável de qualquer outra cidade ou diretamente ou através de uma cidade intermediária.

Exercícios de Livros Relacionados