Pour être clair dés le départ, je présente la source pour ceux qui connaissent un peu de recherche opérationnelle et de la théorie des graphes, puis pour ceux qui n'en connaissent rien du tout:
PCQCUP: Il s'agit de trouver l'arbre de poids minimal dans un graphe dont les sommets sont des points du plan. Chaque sommet est relié avec tout autre sommet par une arrête qui a un coût égal à la distance entre ces 2 point. L'algorithme utilisé est celui de Kruskal.
PCQNCRDT: On a n points dans le plan, il faut les relier avec (n-1) segments (chaque segment relie 2 points), de sorte qu'on ait un réseau, c'est à dire que chaque point doit communiquer avec tout autre. Le probléme est de minimiser la somme des longueurs des segments (Imaginez qu'on doit connecter des postes avec du cablage, il faudrait minimiser le cout des cables donc utiliser le minimum possible)