Seja o produto cartesiano , isto é, o conjunto de todos os pares ordenados com em e em . Digamos que dois elementos e são adjacentes se
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.