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
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
então
— não faz sentido usar um grafo com arestas orientadas. Em vez disso escolhemos um grafo não orientado, onde uma aresta
indica que
está relacionado com
, sem direção.
Passo 3
Definimos o grafo
assim:
, ou seja, cada elemento de
vira um vértice.
.
A reflexividade ( ) 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.
A reflexividade (
Passo 4
A transitividade garante que, sempre que existe aresta entre
e
e também entre
e
, então deve haver aresta entre
e
. 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
corresponde exatamente a uma componente conexa do grafo
. 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.