Math 310
Spring 2011
Homework answer for assigned even problems
For the material on Test 3 or later:
2.1: 6) a) no, b) no, c) yes, d) yes, e) yes, f) no
16) Answers vary. One example would be: A={1} and B={1,{1}}
24) It would be the set of all ordered pairs, where the first element is a MSUM math course and the second element is a MSUM math professor.
26) If AxB is the empty set, then at least one of A or B must also be the empty set (it does not have to be both).
2.2) 48) a) The union is Z+. The intersection is the empty set.
b) The union is N. The intersection is {0}.
c) The union is (0,\infty). The intersection is (0,1).
d) The union is (1,\infty). The intersection is the empty set.
8.1) 16) a, b, c, e, f are not asymmetric. d is asymmetric.
18) none are asymmetric
8.3) 36) For the union, add every edge that appears in either of the individual graphs.
For the intersection, add every edge that appears in both of the individual graphs.
For the symmetric difference, add every edge that appears in exactly one of the individual graphs.
For the difference, add every edge that is in the first graph but not the second graph.
For the composition, if there is an edge from i to j in the first graph and from j to k in the second graph, then draw an edge from i to k in the composition graph.
8.5) 2) a) is an equivalence relation
b) is an equivalence relation
c) is not an equivalence relation (not transitive)
d) is not an equivalence relation (not transitive)
e) is not an equivalence relation (not transitive)
26) a) {0), {1}, {2}, {3}
c) {0}, {1, 2}, {3}
9.2) 12) The degree of a vertex v is the number of people known by the person represented by v.
An isolated vertex would represent someone who knows no one at all.
A pendant vertex would represent someone who knows only one other person.
If the average degree is 1000, then the average person knows 1000 other people.
28) a) Sorry, but graphs are too hard to type....
b) There are multiple answers. One answer is: (Anna, Jason), (Barbara, Kevin), (Carol, Nick), Diane, Oscar), (Elizabeth, Matt). If you want to be nicer to Larry than I was, you would have a different answer.
9.4) 32) 29) none
30) edge {c,d}
31) edges {a,b}, {b,c}, {c,d}, {c,e}, {e,i}, and {i,h}
9.5) 10) yes
16) The idea is similar to that of the related theorem regarding Euler circuits for undirected graphs, you just have to count the in-degrees and out-degrees separately.
38) yes - a,b,c,d,e
40) no - it has three pendant vertices. Any one of them can be where the path starts or stops, but when you have three or more pendant vertices, there will not be a Hamilton path.
42) yes - a,b,d,c,e (but it does not have a Hamilton circuit)
9.6) 2) 7
4) 16
6) (see the solution for #7)
14) Assign a weight of 1 to every edge.
10.3) 4) a) Level 5
b) 3.4.5.2
c) At least 3 siblings
d) At least 19 vertices.
e) 0, 1, 2, 3, 3.1, 3.2, 3.3, 3.4, 3.4.1, 3.4.2, 3.4.3, 3.4.4, 3.4.5, 3.4.5.1, 3.4.5.2, 3.4.5.2.1, 3.4.5.2.2, 3.4.5.2.3
12) k, e, l, m, b, f, r, n, s, g, a, c, o, h, d, i, p, j, q
18) a) Sorry, graphs are too hard to type.
b) Hopefully, the translation from the words below to the appropriate symbols will be clear.
First expression: iff not and p q or not p not q; Second expression: or and not p iff q not p not q.
c) First expression: p q and not p not q not or iff; Second expression: p not q p not iff and q not or
d) First expression: p and q not iff p not or q not; Second expression: p not and q iff p not or q not
24) a) 32
b) 40
c) 32
28) Both trees give the result a b c d e f g h
10.4) 12) a) 1
b) 2
c) 3
16) 13) edges included are {a,b}, {a,c}, {c,d}, {d,e}{d,f}, {e,h}, {f,g}, {h,i}, {g,j}
14) edges included are {a,b}{a,g}{b,c}{g,h}{g,l}{h,i}{h,m}{i,d}{i,e}{i,j}{i,n}{e,f}{j,k}
15) edges included are {a,b}{a,e}{b,c}{b,f}{e,j}{c,d}{j,g}{j,h}{j,i}{j,k}{j,p}{k,o}{k,n}{k,m}{k,l}{p,q}{p,r}{p,t}{q,s}
24) If and only if it is a cut edge.
10.5) 12) Just replace the words/concepts of "minimum" with "maximum" in Kruskal's algorithm.
14) edges included are {d,h}{d,e}{b,f}{d,g}{a,b}{b,e}{b,c}{f,i}
11.1) 12) In order to have a sum of 1, then at least one of the products must be 1. In order for one of the products to be one, each of the values in the product must be 1. But, given that each combination of two of the three variables is used in a product, this means that there must be at least two variables with the value 1.
11.2) 12) Hopefully, you will be able to figure out the notation used below.
a) \overline{ \overline{x} \overline{y} \overline{z} }
b) \OVERLINE{ \overline{x} \OVERline{ \overline{y} \Overline{x \overline{z}} } }
c) \overline{x} y
d) \overline{x} \OVERLINE{ \overline{x} y z }
11.4) 2) a) xy + \overline{x}y+\overline{x}\overline{y}
b) xy + x\overline{y}
c) xy + x\overline{y} + \overline{x}y+ \overline{x}\overline{y}
4) a) \overline{x}
b) x
c) 1
6) For #6, you should draw the circuit as well.
a) yz
b) \overline{z}
c) 0
12) a) \overline{x}z
b) y
c) \overline{z}z + x\overline{z} + x\overline{y} or \overline{x}z + x\overline{z} + \overline{y}z
d) yz + \overline{x}\overline{z} + x\overline{y} or xz + \overline{x}y + \overline{y}\overline{z}
22) See Example 3 for a solution (you'll get the same solution, through a different method).
24) See Example 4 for a solution (you'll get the same solution, through a different method).