next up previous contents
Next: Determinação do Consenso (Montagem) Up: ... ao Computador O Previous: Comparação Rápida   Contents

Refinamento

A fase anterior nos deu um grafo G com uma série de arestas que não deveriam existir, pois não possuem uma similaridade mínima requerida. Estes falso-positivos devem ser removidos com uma comparação mais rigorosa dada por Sim(X, Y). O algoritmo da Figura 7 nos devolve um novo grafo G que é o refinamento do grafo de entrada. Note que w(u, v) denota o peso associado à aresta (u, v).

Figure 7: Algoritmo para Refinamento de Grafos
\begin{figure} \centering\textsf{ \begin{tabbing} \large Refina(G, w) \\ \\ ... ...$E[G] \leftarrow E[G]-\{(u, v)\}$\ \\ retorne $G$ \end{tabbing}} \end{figure}

Queremos trabalhar com um conjunto minimal de arestas, ou seja, o menor conjunto de arestas que conectam todos os vértices do grafo G. Isso torna mais fácil a montagem na próxima fase. Para obtermos uma qualidade maior, escolheremos um conjunto minimal Em de arestas tal que maximize:

\begin{displaymath}\sum_{(u, v) \in E_{m}} Sim(s[u], s[v])\end{displaymath}

.

O grafo A=(V, Em) é uma árvore que pode ser obtida com um algoritmo para árvores de espalhamento máximas, como o algoritmo de Kruskal (Figura 8). A cada passo do loop de AEMax-Kruskal(G, w), conectam-se dois conjuntos de vértice através da maior aresta possível. Ao final, a árvore A=(V, EA) representa um único conjunto conexo de vértices, com peso total máximo.

Figure: Algoritmo para encontar a Árvore de Espalhamento Máxima
\begin{figure} \centering\textsf{ \begin{tabbing} \large AEMax-Kruskal(G, w) \... ... \\ \> \> \> \> Union($u, v$) \\ retorne $E_{A}$ \end{tabbing}} \end{figure}

next up previous contents
Next: Determinação do Consenso (Montagem) Up: ... ao Computador O Previous: Comparação Rápida   Contents
Thiago Teixeira Santos
1999-07-19