Prove que, se n ou m são pares, existe um ciclo em uma grade Gn, m contendo todos os seus vértices.

Passo 1

Vamos entender o que a questão está pedindo. Temos uma grade , que é basicamente um grid com linhas e colunas de vértices conectados entre si. A pergunta quer que a gente prove que, se ou forem números pares, existe um ciclo que passa por todos os vértices da grade. Isso envolve conceitos de teoria dos grafos, especialmente sobre ciclos e grafos Hamiltonianos.

Passo 2

Primeiro, vamos lembrar o que é um ciclo Hamiltoniano. Um ciclo Hamiltoniano é um caminho fechado que visita cada vértice exatamente uma vez. Para provar que existe tal ciclo em quando ou são pares, vamos construir explicitamente um ciclo que passe por todos os vértices.

Passo 3

Vamos considerar o caso onde é par. Imagine a grade como um conjunto de linhas horizontais e colunas verticais de vértices. Como é par, podemos percorrer as linhas alternadamente de esquerda para direita e de direita para esquerda, criando um “ziguezague” que cobre toda a grade.

Passo 4

Ao final de cada linha, como é par, conseguimos conectar a última coluna da linha atual à primeira coluna da próxima linha sem quebrar o ciclo. Isso é possível porque, com par, sempre haverá uma maneira de retornar ao ponto de partida após percorrer todas as linhas.

Passo 5

De forma similar, se for par, podemos aplicar o mesmo raciocínio, mas agora percorrendo as colunas alternadamente de cima para baixo e de baixo para cima. Isso também permitirá que criemos um ciclo que passe por todos os vértices da grade.

Resposta

Portanto, se ou forem pares, existe um ciclo em que contém todos os seus vértices, ou seja, existe um ciclo Hamiltoniano na grade.

Exercícios relacionados