Suponha que você quisesse modelar uma relação de equivalência com um grafo. Você usaria um grafo orientado ou não orientado? Como seriam as classes de equivalência? Explique.

Passo 1

O enunciado quer que a gente represente uma relação de equivalência sobre um conjunto S usando um grafo. Para isso, vamos lembrar que uma relação de equivalência é reflexiva, simétrica e transitiva, e ver como cada propriedade se traduz em termos de grafos.

Passo 2

Como a relação é simétrica — ou seja, se asim b então bsim a — não faz sentido usar um grafo com arestas orientadas. Em vez disso escolhemos um grafo não orientado, onde uma aresta a,b indica que a está relacionado com b, sem direção.

Passo 3

Definimos o grafo G=(V,E) assim:
V = S, ou seja, cada elemento de S vira um vértice.
E = lu,vmid u,vin S e usim v,;uneq vr.
A reflexividade ( ;asim a;) pode ser ignorada em termos de desenho de grafo padrão ou indicada por loops em cada vértice, mas o essencial são as arestas entre pares distintos.

Passo 4

A transitividade garante que, sempre que existe aresta entre u e v e também entre v e w, então deve haver aresta entre u e w. Isso faz com que todos os vértices de uma mesma classe de equivalência formem uma sub-grafo completo (uma clique).

Passo 5

Cada classe de equivalência
[x] = ,yin S mid ysim x
corresponde exatamente a uma componente conexa do grafo G. Dentro dessa componente todos os vértices estão ligados entre si (é uma clique), e não há arestas ligando vértices de classes diferentes.

Resposta

Usa-se um grafo não orientado. As classes de equivalência aparecem como componentes conexas (cliques) desse grafo.

Exercícios de Livros Relacionados