Algoritmos e Estruturas de Dados/Estruturas para classes de equivalência

Estruturas para classes de equivalência

Introdução

Diversos problemas podem ser modelados através do cálculo de classes de equivalência (uma definição formal desse conceito é apresentada logo em seguida). Um exemplo famoso é aquele de determinar os componentes conexos de um grafo. Um grafo é um conjunto de vértices que podem ser conectados dois a dois por arestas. Como determinar se, dado o conjunto das arestas, existe um caminho entre dois vértices? Se considerarmos dois vértices como equivalentes quando existe um caminho entre os dois, então uma solução desse problema consiste em determinar se dois vértices fazem parte da mesma classe de equivalência.

Definições

Uma relação binária $\equiv$ sobre um domínio ${\mathcal {D}}$ é uma relação de equivalência se satisfaz as seguintes propriedades

1. $\forall a,b\in {\mathcal {D}}\bullet a\equiv b\Leftrightarrow b\equiv a$ ($\equiv$ é simétrica);
2. $\forall a\in {\mathcal {D}}\bullet a\equiv a$ ($\equiv$ é reflexiva);
3. $\forall a,b,c\in {\mathcal {D}}\bullet a\equiv b\land b\equiv c\Rightarrow a\equiv c$ ($\equiv$ é transitiva).

Seja $a\in {\mathcal {D}}$ um elemento do domínio, a classe de equivalência de $a$ é o conjunto $\{x\in {\mathcal {D}}\mid x\equiv a\}$ dos elementos relacionados com $a$.

Objetivo

O cliente do tipo abstrato de dados manipula valores de um determinado domínio que nomeamos D. O objetivo é definir um tipo abstrato de dados que permita representar e manipular eficientemente classes de equivalência que evoluem dinamicamente. Inicialmente cada classe de equivalência é constituída por um único elemento do domínio D, d. O nome de cada classe é d. Queremos operações para unir classes, e determinar o nome da classe de equivalência de um elemento.

O tipo abstrato de dados possuirá três operações: 1)construtor: cria as classes. 2)Find: determina o nome da classe de equivalência de um elemento qualquer de D. 3)Uniao: une duas classes de nomes conhecidos.

O construtor cria uma classe de equivalência para cada elemento d distinto de D. Pós-Condição - Cada classe tem apenas um elemento, d. O nome da classe de d é d.

Find

dado d de D, retorna o nome da classe de d.

Uniao

Dadas duas classes de nomes d1 e d2, realiza a união das duas classes de equivalência, adotando d1 ou d2 como nome da nova classe. As classes unidas deixam de existir.

Apresentação das soluções

Os algoritmos e estruturas de dados que provêm implementação eficientes desse tipo abstrato de dados são conhecidos como algoritmos Union-Find (União-Busca), pelo tipo de operações que são providas. Outros nomes encontrados são disjoint sets (conjuntos disjuntos) e dynamic equivalence relations (relações de equivalência dinâmicas).

Existe basicamente duas estruturas de dados para implementar o tipo abstrato União-Busca: a baseada em listas, e a baseada em árvores. A estrutura de dados linear, baseada em listas encadeadas, é mais apropriada para aplicações onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a estrutura de dados ramificada, baseada em árvores, é mais eficiente quando o número de união é proporcionalmente mais elevado que o número de buscas. A estrutura de dados baseada em árvores é fácil de implementar como um vetor, sendo adotada por muitos autores. Além disso permite realizar as operações prasticamente em tempo constante.