Leia com atenção as instruções abaixo.
Valor: 2,0 pontos na 1ª Nota.
Data da Entrega Limite: 29/04/2022
Formato de Entrega: envie um .pdf com a resolução, feito em meios digitais, para o chat privado do professor no Slack.
A atividade é individual.
Grafo de Bruijn. O grafo de Bruijn de \(r\) dimensões consiste de \(2^k\) nós e \(2^{k+1}\) arestas direcionadas. Cada nó corresponde a um número binário único de \(r\) bits \(u_{1}u_{2}...u_{r}\). Há uma aresta direcionada de cada nó \(u_{1}u_{2}...u_{r}\) para os nós \(u_{2}u_{3}...0\) e \(u_{2}u_{3}...1\).
Qual é o diâmetro de um grafo de Bruijn de \(r\) dimensões? Justifique sua resposta.