O grafo do bispo
-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 bispo do jogo de xadrez pode saltar de um deles para o outro em um só movimento. Faça uma figura do grafo do bispo 4-por-4. Quantas arestas tem o grafo do bispo 8-por-8?
Passo 1
Beleza, vamos lá! O enunciado pede para a gente entender o que é o “grafo do bispo” em um tabuleiro de xadrez com
linhas e
colunas. Temos que fazer uma figura desse grafo para um tabuleiro 4x4 e descobrir quantas conexões (arestas) existem no grafo para um tabuleiro 8x8.
Aqui, o conteúdo principal envolve Grafos e o movimento do Bispo no xadrez. Para resolver isso, vamos precisar entender como representar o tabuleiro como um grafo e como determinar quando duas casas estão conectadas por uma aresta, ou seja, quando um bispo pode ir de uma casa para outra em um único movimento.
Passo 2
Primeiro, vamos lembrar como o bispo se move no xadrez. O bispo se move qualquer número de casas na diagonal, sem pular outras peças. Isso significa que, no grafo, duas casas estarão conectadas se elas estiverem na mesma diagonal.
Em um tabuleiro
, cada casa pode ser representada por um par de coordenadas
, onde
é a linha e
é a coluna.
Passo 3
Para construir o grafo do bispo 4x4, vamos listar todas as casas e conectar aquelas que estão na mesma diagonal. Vamos numerar as casas de 1 a 16 para facilitar.
Por exemplo:
- Casa 1: (1,1)
- Casa 2: (1,2)
- …
- Casa 16: (4,4)
Agora, conectamos as casas que estão na mesma diagonal. Por exemplo, Casa 1 (1,1) está na mesma diagonal que Casa 6 (2,2), Casa 11 (3,3) e Casa 16 (4,4).
Passo 4
Vamos desenhar a figura do grafo do bispo 4x4. Cada nó representa uma casa do tabuleiro, e as linhas conectando os nós representam as diagonais.
[Aqui você desenharia uma figura com 16 nós conectados pelas diagonais, mas como estamos em texto, imagine um quadrado com linhas diagonais conectando as casas conforme explicado.]
Passo 5
Agora, vamos calcular quantas arestas existem no grafo do bispo 8x8. Cada aresta representa uma conexão entre duas casas que estão na mesma diagonal.
Para um tabuleiro
, o número de diagonais principais é
. Cada uma dessas diagonais terá um número de casas que varia, e podemos calcular as conexões usando combinações.
A fórmula para o número de arestas em um grafo onde cada conjunto de
vértices está completamente conectado é:
Para o tabuleiro 8x8, vamos calcular isso.
Resposta
No grafo do bispo 8-por-8, existem 112 arestas.