Elementary constraint graph

Theorem 9.3.1 For a well-posed, ordered, elementary constraint graph, the sum of the cardinality of the prime anchor sets for all vertices is equal to V — 1. 

By Theorem 9.2.2 the algorithm is guaranteed to make a constraint graph taut. In addition, the algorithm also guarantees for elementary constraint graphs, the control offset cost is always reduced, or in the worst case remains the same. In order to determine the effect of these steps on the control cost, we state the following lemma and theorem. 

Theorem 9.3.2 Given a well-posed, elementary constraint graph G(V,E), G can be made taut without increasing the maximal offset values of the anchors ofG. 

The set of anchor clusters is denoted by Ao, Ai,..., A, who-e Ao is the cluster containing the source vertex. A constraint graph is called elementary if all anchor clusters contain a single anchor, i.e. A, = 1, Vt. 

Since we can make a graph taut, the theorem above implies that it is possible to achieve the lower bound in synchronization costs for elementary graphs. We note that imposing a cluster ordering in a graph will not affect the property of well-posedness. The reason is that, by definition, anchor clusters are not connected by any cycle in the constraint graph. Therefore, no cycles can be formed by serializing between anchors in different clusters. 

---