Seja X=0,1,2,3,4. Defina uma relação R em X tal que x R y se x+y=4. 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
,X = 0,1,2,3,4
e a relação Rsubseteq Xtimes X definida por
xRy se, e somente se, x + y = 4
O objetivo é desenhar o grafo associado a R e decidir se ele deve ser orientado ou não orientado.

Passo 2

Para encontrar todos os pares (x,y)in R, basta resolver x+y=4 com x,yin X. As soluções são:
(0,4),,(1,3),,(2,2),,(3,1),,(4,0)

Passo 3

Note que sempre que (x,y)in R temos também (y,x)in R porque
x+y=4implies y+x=4
Isto mostra que R é simétrica.

Passo 4

Num grafo direcionado, cada par (x,y) seria representado por um arco de x para y. Mas como (x,y) e (y,x) 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:
0,4, 1,3, 2,2
Em termos de desenho:
  • Uma aresta ligando o vértice 0 ao vértice 4.
  • Uma aresta ligando o vértice 1 ao vértice 3.
  • Um laço (loop) no vértice 2.

Passo 6

Como não há nenhum par (x,y) sem o seu simétrico (y,x), não há necessidade de orientação nas arestas. Logo, o grafo é não orientado.

Resposta

O grafo associado a R é não orientado, com arestas 0,4, 1,3 e um laço em 2.

Exercícios de Livros Relacionados