Clustering: diferenças entre revisões

Ao deletarmos uma aresta de uma árvore, criamos dois componentes conexos que também são árvores, tal fato é usado fortemente neste algoritmo. Encontrar k clusters consiste em deletar arestas de um grafo até obtermos k componentes conexos. No problema que estamos tratando, desejamos, além de encontrar k componentes conexos, que estes componentes sejam o mais distantes possível entre si. Definiremos o espaçamento de um conjunto de clusters de um grafo como a menor distância entre dois nós que pertencem a componentes conexos distintos. Provaremos agora, que ao deletar as k-1 maiores arestas de uma minimum spanning tree de um grafo conexo U, obteremos k clusters e o espaçamento entre eles será máximo.

 

 

==== A otimalidade do algoritmo ====