1. (15%) Consider the set $S = \{a,b,c,d,e\},$ and a logical matrix $M$ corresponding to a relation $R$ on the set $S$ is shown in the following.

$$M = \begin{bmatrix} 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 \end{bmatrix}$$

(a) In order to check if there exists a partial ordering, which properties should you check?
(b) Draw the Hasse diagram of this order.
(c) Determine all pairs of incomparable elements.

(a) 1. Reflexive 2. Anti-symmetric 3. Transitive
(b)

(c) (a, b), (a, e), (b, c).

2. (15%) Solve the following recurrence equations for $A(n),$ and $B(n).$

$$\begin{cases} A(n) = 3A(n-1) + 2B(n-1)\\ B(n) = A(n-1) + B(n-1)\\ n \geq 1, A(0) = \sqrt{3}, B(0) = 0 \end{cases}$$

3. (20%) Given the following figures (a) and (b). Assume the source node is a and the sink node is f. The label along the edge (or node) means the maximum capacity of the edge (or node).

(a) Find the maximum flow from the source to the sink. And what is the corresponding minimum cut in Fig. (a).
(b) Find the maximum flow from the source to the sink. And what is the corresponding minimum cut in Fig. (b).

(a) Max flow: 8, $\{\{a,b,c,d,e\},\{f,g,h,i,j\}\} \in \text{min-cut}.$
(b) Max flow: 15