1) For graphs 1-5 below determine whether each graph has an Euler Circuit. If such a circuit exists list the points in the Euler circuit. 1 doesnt have an Euler circuit; vertex A has a degree 3. 2 has an Euler circuit, ABCAHGIEGFEDCIA 3 doesnt have an Euler circuit; vertex A has a degree 3. 4 doesnt have an Euler circuit, vertex E has a degree 3. 1) 5 has an Euler circuit, I J H E I D E G C D B C F B G F D H G I . 2) For graphs 6-9 below determine whether the given graph has a Hamilton circuit. If it does, find the circuit. If it does not, give an argument to show why no such circuit exists. (Please draw it if it has one.) 6 doesnt have Hamilton circuit. After you cross B to C one cannot come back to A without going through C and B for the second time. Graph 7 has a Hamilton circuit
8 doesnt have a Hamilton circuit. After you go from E to F you can’t come back with out going through E for the second time. 9 Does not have a Hamilton Circuit. 3) For graphs 10-12 below use Kruskal’s algorithm to find and draw a minimum spanning tree for the weighted graphs.
4) a) This would be correct if a line went from 2 to 6.
b)
c)
d)
5) Draw the Hasse diagram for inclusion (subset) on the set P(S) where S = {a, b, c, d}
{a,b,c,d} {a,b,c} {a,b}
{a,c} {a}
{a,b,d} {a,d}
{a,c,d} {b,c}
{b,d} {c}
{b}
{b,c,d} {c,d} {d}
{Ø} 6) For graph 13 below, answer the following questions: a. Find the maximal elements: i,m. b. Find the minimal elements: a,b,c. c. Find the minimum, if it exists. DNE d. Find the maximum, if it exists. DNE e. Find all upper bounds of {a, b, c}: k,i,m f. Find the least upper bound of {a, b, c} if it exists:k g. Find all lower bounds of {f, g, h}:DNE Find the greatest lower bound of {f, g, h} if it exists. DNE 7) Answer the following questions concerning the poset ({3, 5, 9, 15, 24, 45}, | ) (the divisibility relation on the set) a. Find the maximal elements 24, 45 b. Find the minimal elements.3,5 c. Find the minimum, if it exists.DNE d. Find the maximum, if it exists.DNE e. Find all upper bounds of {3,5}: 15, 45 f. Find the least upper bound of {3,5} if it exists. 15 g. Find all lower bounds of {15,45} 15, 5, 3 Find the greatest lower bound of {15,45} if it exists. 15
8) Design an Finite State machine for each of the following, and include a state table or brief explanation of why your FSM works. a. a* b*
b. (a + b) b*a
c. b+(a b) *
