Seja
. Defina uma relação
em
tal que
se
. Desenhe o grafo associado a essa relação. Esse grafo deve ser orientado ou não orientado?
Passo 1
O enunciado dá o conjunto de vértices
e a relação definida por
e a relação
O objetivo é desenhar o grafo associado a
e decidir se ele deve ser orientado ou não orientado.
Passo 2
Para encontrar todos os pares
, basta resolver
com
. As soluções são:
Passo 3
Note que sempre que
temos também
porque
Isto mostra que
é simétrica.
Passo 4
Num grafo direcionado, cada par
seria representado por um arco de
para
. Mas como
e
estão sempre juntos, cada arco tem seu arco reverso. Isso sugere usar arestas não orientadas em vez de arcos duplos.
Passo 5
As arestas não orientadas correspondentes são:
Em termos de desenho:
- Uma aresta ligando o vértice
ao vértice . - Uma aresta ligando o vértice
ao vértice . - Um laço (loop) no vértice
.
Passo 6
Como não há nenhum par
sem o seu simétrico
, não há necessidade de orientação nas arestas. Logo, o grafo é não orientado.
Resposta
O grafo associado a
é não orientado, com arestas
,
e um laço em
.