Clustering: diferenças entre revisões

Dado que <math>p_{i}</math> e <math>p_{j}</math> pertencem a um mesmo cluster, nenhuma das arestas do caminho <math>P</math> entre eles foi deletado pelo algoritmo. Ou seja, cada aresta pertencente a <math>P</math> tem comprimento menor ou igual a <math>d^*</math>. Por outro lado, sabemos que pi pertence a <math>C_{s}'</math>, mas <math>p_{j}</math> não; logo, tomemos <math>p'</math> como o primeiro nó em <math>P</math> que não pertence a <math>C_{s}'</math> e <math>p</math> o nó que vem logo antes de <math>p'</math> no caminho <math>P</math>. Sabemos que <math>d(p,p') \leq d^*</math> em <math>C'</math> e isso completa a prova, pois o <math>d \leq d(p,p')</math>, sendo <math>d</math> o espaçamento de <math>C'</math>.

 

 

==== Implementação e Análise da Complexidade ====