Hola.
1) Ustedes tienen que diseñar un protocolo pensando en un árbol de cubrimiento de costo mínimo dado. Para el momento de la implementación y prueba seguramente van a necesitar este árbol (conocer padre e hijos tal vez), para esto van a tener que crearlo antes. Dado un grafo, pueden calcularlo "offline" y crearlo agregando información en cada nodo o pueden implementar un algoritmo que lo calcula. Para lo segundo les recomiendo que utilicen el algoritmo PT_Construction del libro.
Con respecto a resolver el problema en simultaneo con la creación del árbol, puede ser. Si encontras una buena solución que haga las dos cosas juntas podes hacerlo.
2) PT(s) significa el arbol de cubrimiento de costo mínimo con raiz en s. s puede ser cualquier nodo. Ustedes tienen que diseñar el protocolo que encuentra las aristas de swap para 1 solo árbol.
3) Es solo para calcular los links de swap.
Saludos