O grafo do cavalo
-por-t é definido assim: os vértices do grafo são as casas de um tabuleiro de xadrez com
linhas e
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
linhas e
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
-por-
e depois calcular quantas arestas existem no grafo para um tabuleiro
-por-
.
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
-por-
, temos
casas, então nosso grafo terá
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
-por-
. 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
-por-
.
Passo 4
Agora, vamos calcular quantas arestas existem no grafo do cavalo para um tabuleiro
-por-
. Cada aresta representa um movimento possível do cavalo entre duas casas.
Primeiro, sabemos que cada cavalo tem até
movimentos possíveis em um tabuleiro grande, mas nas bordas e cantos do tabuleiro, o número de movimentos diminui.
Para um tabuleiro
-por-
, há
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
para não contar duas vezes a mesma aresta.
Após calcular, descobrimos que o grafo do cavalo
-por-
tem 168 arestas.
Resposta
O grafo do cavalo
-por-
tem 168 arestas.