(1) Find (using weighted adjacency matrices) the minimum cost of paths between any pair of vertices in the following graph.

(2) In class we defined the transitive closure of a relation R on a set S as the smallest relation R\  with the property that R ⊆ R\ . This means that if R\\  is any other transitive relation on S such that R ⊆ R\\ , then R\  ⊆ R\\ . Fill in the details of the proof of the following statement: any relation R on a set S has a unique transitive closure.

•  Suppose that T1 and T2 are both transitive closures of a relation R on a set S .

•  · · ·   Fill this in  · · ·

•  Therefore T1 = T2 .

(3) For each property listed, find an example of a partial order that has that property, with brief justifi- cations. Draw its Hasse diagram.

(a) A partial order that is also an equivalence relation.

(b) A poset with at least two elements, in which every element is maximal.

(4) Let (P, ⪯) be a poset and let A be any subset of P . An element u ∈ P is said to be an upper bound for A if for each a ∈ A, we have a ⪯ u. An element l ∈ P is said to be a lower bound for A if for each a ∈ A, we have l ⪯ a. Further, an element u ∈ P is said to be a least upper bound (lub) for A if:

•  u is an upper bound for A, and

•  if v ∈ P is any upper bound for A, then u ⪯ v .

Similarly, an element l ∈ P is said to be a greatest lower bound (glb) for A if:

•  l is a lower bound for A, and

•  if m ∈ P is any lower bound for A, then m ⪯ l .

With this background, answer the following.

(a) Draw a Hasse diagram of a poset (P, ⪯) and write down a subset A that has an upper bound, but no least upper bound. Justify briefly.

(b) Draw a Hasse diagram of a poset (P, ⪯) and write down a subset A that has a greatest lower bound. Justify briefly.

(c) Complete the following partial proof of the following statement:“If (P, ⪯) is a poset and A ⊆ P has a least upper bound, then the least upper bound is unique.”Write out the third step with full justifications.

(i) Suppose that A ⊆ P has a least upper bound u ∈ P .  (ii) Suppose that v ∈ P is also a least upper bound of A. (iii)  · · ·   Fill this in  · · ·

(iv) Therefore, u = v .