Seja V o produto cartesiano 1,2, ldots, p times1,2, ldots, q, isto é, o conjunto de todos os pares ordenados (i, j) com i em 1,2, ldots, p e j em 1,2, ldots, q. Digamos que dois elementos (i, j) e (i^prime, j^prime) são adjacentes se
i=i^prime e|j-j^prime|=1
ou
j=j^prime e|i-i^prime|=1
Essa relação de adjacência define um grafo sobre o conjunto V de vértices conhecido como grade p-por-q. Faça uma figura da grade 3-por-4. Quantas arestas tem essa grade? Quantas arestas tem a grade p-por- q ?

Passo 1

Beleza, vamos lá! A gente tem um conjunto de pares ordenados (i, j) onde i vai de 1 a p e j de 1 a q. Isso forma uma grade chamada p-por- q. A questão é sobre como desenhar essa grade (vou falar mais sobre isso depois) e contar quantas conexões, ou arestas, existem nela. Para resolver isso, vamos precisar entender o conceito de adjacência em grafos e aplicar um pouquinho de matemática para contar direitinho as arestas.

Passo 2

Primeiro, vamos visualizar a grade 3-por- 4. Imagina uma tabela com 3 linhas e 4 colunas. Cada célula dessa tabela representa um vértice (i, j). Assim, teremos os vértices:
(1,1), (1,2), (1,3), (1,4)
(2,1), (2,2), (2,3), (2,4)
(3,1), (3,2), (3,3), (3,4)
Esses vértices estão conectados por arestas se estiverem na mesma linha e colunas adjacentes, ou na mesma coluna e linhas adjacentes.

Passo 3

Agora, vamos contar as arestas dessa grade 3-por- 4. Para isso, a gente pode dividir o trabalho em duas partes: contar as arestas horizontais e as verticais.
Arestas Horizontais:
Cada linha tem 4 vértices, o que dá 3 conexões entre eles (entre (1,1)-(1,2), (1,2)-(1,3), e (1,3)-(1,4), por exemplo). Como temos 3 linhas, totalizamos:
3 linhas times 3 arestas por linha = 9 arestas horizontais
Arestas Verticais:
Cada coluna tem 3 vértices, gerando 2 conexões entre eles (como entre (1,1)-(2,1) e (2,1)-(3,1)). Com 4 colunas, temos:
4 colunas times 2 arestas por coluna = 8 arestas verticais

Passo 4

Somando as arestas horizontais e verticais, a gente tem:
9 arestas horizontais + 8 arestas verticais = 17 arestas no total

Passo 5

Agora, para generalizar e encontrar o número de arestas em uma grade p-por- q, vamos usar a mesma lógica.
Arestas Horizontais:
Cada linha tem q vértices, formando (q - 1) arestas. Com p linhas, temos:
p times (q - 1) arestas horizontais
Arestas Verticais:
Cada coluna tem p vértices, formando (p - 1) arestas. Com q colunas, temos:
q times (p - 1) arestas verticais
Total de Arestas:
Somando as duas partes:
p(q - 1) + q(p - 1) = 2pq - p - q

Resposta

A grade 3-por- 4 tem 17 arestas. De forma geral, uma grade p-por- q possui 2pq - p - q arestas.

Exercícios relacionados