Solução por Rogério Júnior
A solução por força bruta seria simplesmente testar todos os vértices como possíveis $$A$$, $$B$$, $$C$$ e $$D$$. Entretanto, note que para dados $$B$$ e $$C$$ fixos, não faz sentido escolher $$A_1$$ mais próximo de $$B$$ que $$A_2$$ se $$A_2$$ não aparecer como nenhum dos outros vértices escolhidos. Deste modo, temos apenas $$3$$ possibilidades para $$A$$: os $$3$$ vértices mais distantes de $$B$$ (partindo deles), visto que não faz sentido escolher um outro pois dentre eles sempre há pelo menos um que não é $$C$$ ou $$D$$. De modo semelhante, há apenas três possibilidades para $$D$$.
Seja $$\alpha(v) = {u_1, u_2, u_3}$$ de modo que a distância de $$u_i$$ para $$v$$ não é inferior à de nenhum vértice não contido em $$\alpha(v)$$ ($$\alpha(v)={u_1,u_2,u_3}, \forall 1\leq i \leq 3, j, d(u_i,v)\geq d(j,v)$$), ou seja $$\alpha(v)$$ são três vértices $$u_i$$ cujos valores $$d(u_i,v)$$ são máximos. De maneira semelhante, Seja $$\beta(v) = {u_1, u_2, u_3}$$ de modo que a distância de $$v$$ para $$u_i$$ não é inferior à de nenhum vértice não contido em $$\beta(v)$$
Como vimos, basta agora testarmos todos os valores possíveis para $$A$$, $$B$$, $$C$$ e $$D$$ da seguinte maneira: vamos testar, por força bruta, todos os possíveis valores de $$B$$ e $$C$$, então testaremos os três valores possíveis de $$A$$ ($$\alpha(B)$$) e os tr~\e possíveis valores de $$D$$ ($$\beta(D)$$). A complexidade é $$O(n^2)$$.
Segue o código para melhor entendimento:
https://gist.github.com/rogerioagjr/3e255d2ca40e4920edda9b2cb37b34e3
Deixe um comentário