A strict partial order on a finite set of elements S, is a binary relation that is irreflexive, anti- symmetric, and transitive. (These properties of relations are assumed to be background knowledge. If you need to look them up, please feel free to do so.) A strict partial order relation R on a set S can naturally be represented by a directed graph with vertex set S, where the edge (u,v) means that (u,v) R.

(a) Prove that if G is a directed graph representing a strict partial order, then G is acyclic.

(b) We know that strict partial orders are transitive. So, if our graph has edges (u,v) and (v,w), the edge (u,w) is implied and we dont have to explicitly have this edge. We could remove implied edges from the given graph one by one using just the rule above: If we find edges (u,v),(v,w) and (u,w), then we can remove (u,w). If there are no more implied edges, the partial order representation is said to be reduced . Prove that any strict partial order has a unique reduced representation. In other words, no matter in what order we remove the implied edges, we will arrive at the same reduced representation.

(c) Design and analyze an efficient algorithm for finding this reduced representation.