O grafo do cavalo t-por-t é definido assim: os vértices do grafo são as casas de um tabuleiro de xadrez com t linhas e t colunas; dois vértices são adjacentes se um cavalo do jogo de xadrez pode saltar de um deles para o outro em um só movimento. Faça uma figura do grafo do cavalo 3-por-3. Quantas arestas tem o grafo do cavalo 8-por-8?

Passo 1

Beleza, vamos resolver esse exercício juntos! O enunciado fala sobre o grafo do cavalo em um tabuleiro de xadrez com t linhas e t colunas. Basicamente, cada casa do tabuleiro é um vértice no grafo, e dois vértices estão conectados se um cavalo pode pular de uma casa para a outra em um único movimento. Para resolver isso, vamos precisar entender como o cavalo se move no xadrez e como representar essas conexões no grafo. Vamos primeiro fazer uma figura do grafo para um tabuleiro 3-por- 3 e depois calcular quantas arestas existem no grafo para um tabuleiro 8-por- 8.

Passo 2

Primeiro, vamos visualizar como o cavalo se move no tabuleiro. O cavalo move em “L”, ou seja, duas casas em uma direção e depois uma casa perpendicularmente. Em um tabuleiro 3-por- 3, temos 9 casas, então nosso grafo terá 9 vértices.
Vamos numerar as casas assim:
1 2 3
4 5 6
7 8 9
Agora, vamos ver de quais casas o cavalo pode pular para quais:
  • Casa 1: Pode ir para a casa 6 e 8.
  • Casa 2: Pode ir para a casa 7 e 9.
  • Casa 3: Pode ir para a casa 4 e 8.
  • Casa 4: Pode ir para a casa 3 e 9.
  • Casa 5: O cavalo na casa 5 não pode se mover para nenhuma outra casa porque todas as posições estão fora do tabuleiro.
  • Casa 6: Pode ir para a casa 1 e 7.
  • Casa 7: Pode ir para a casa 2 e 6.
  • Casa 8: Pode ir para a casa 1 e 3.
  • Casa 9: Pode ir para a casa 2 e 4.

Passo 3

Com essas conexões, podemos desenhar o grafo do cavalo 3-por- 3. Cada casa é um vértice, e cada movimento possível do cavalo é uma aresta conectando dois vértices.
Aqui está uma representação simplificada:
  • Vértice 1 conectado a 6 e 8
  • Vértice 2 conectado a 7 e 9
  • Vértice 3 conectado a 4 e 8
  • Vértice 4 conectado a 3 e 9
  • Vértice 5 sem conexões
  • Vértice 6 conectado a 1 e 7
  • Vértice 7 conectado a 2 e 6
  • Vértice 8 conectado a 1 e 3
  • Vértice 9 conectado a 2 e 4
Isso forma o grafo do cavalo para um tabuleiro 3-por- 3.

Passo 4

Agora, vamos calcular quantas arestas existem no grafo do cavalo para um tabuleiro 8-por- 8. Cada aresta representa um movimento possível do cavalo entre duas casas.
Primeiro, sabemos que cada cavalo tem até 8 movimentos possíveis em um tabuleiro grande, mas nas bordas e cantos do tabuleiro, o número de movimentos diminui.
Para um tabuleiro 8-por- 8, há 64 casas. Vamos contar todas as possíveis conexões sem contar duplicadas (já que uma aresta entre A e B é a mesma que entre B e A).
Uma forma eficiente é calcular para cada posição quantos movimentos o cavalo pode fazer e somar todos, depois dividir por 2 para não contar duas vezes a mesma aresta.
Após calcular, descobrimos que o grafo do cavalo 8-por- 8 tem 168 arestas.

Resposta

O grafo do cavalo 8-por- 8 tem 168 arestas.

Exercícios relacionados