Para quais valores de
estes grafos têm um ciclo euleriano?
Passo 1
O enunciado pede para quais inteiros
o grafo roda
possui um ciclo euleriano.
O conteúdo teórico que vamos usar é o seguinte critério: um grafo conexo admite ciclo euleriano se, e somente se, todos os seus vértices têm grau par.
O conteúdo teórico que vamos usar é o seguinte critério: um grafo conexo admite ciclo euleriano se, e somente se, todos os seus vértices têm grau par.
Passo 2
Descrevendo os graus em
:
– Os vértices do “anel” (os vértices que formam o ciclo) têm, cada um, duas arestas do ciclo mais uma aresta que vai ao centro. Logo, cada vértice do anel tem grau
– Os vértices do “anel” (os
que é ímpar.
Passo 3
O vértice central (o “hub”) está ligado a todos os
vértices do anel, então seu grau é
Esse valor pode ser par ou ímpar dependendo de
, mas não adianta tornar
par se já há vértices de grau ímpar no anel.
Passo 4
Como o grafo roda
é sempre conexo e já identificamos que os vértices do anel têm grau ímpar para todo
, falha a condição de todos os graus serem pares. Portanto não existe valor de
que torne
euleriano.
Resposta
Não há valor de
para o qual
tenha ciclo euleriano.