## Transcribed Text

Section 8.1
1) Draw a picture of the graph G = (V, E, g) where V = {t, u, v, w, z},
E = {e1, e2, e3, e4, e5}, and g(e1) = {v,w}, g(e2) = {t,u}, g(e3) = {u,v}, g(e4) = {v,w},
g(e5) = {t,v}
This problem is similar to examples 1 and 2 and problems 8.1.7 and 8.1.8.
•tuvwz ~ \
Section 8.2
1) Does the following graph have an Euler circuit, an Euler path, both, or neither? Give
reasons for your decision. This problem is similar to examples 4 and 5 and problems
8.2.1–8.2.8.
2) Does the following graph have an Euler circuit, an Euler path, both, or neither? Give
reasons for your decision. This problem is similar to examples 4 and 5 and problems
8.2.1–8.2.8.
3) Use Fleury’s algorithm to produce an Euler circuit for the following graph. Start at A
and label the edges in the order that you add them. This problem is similar to example 6
and problems 8.2.11 and 8.2.12.
1 2 3 4 5 6 7 8 9 10 11 12 13
1) Let A = {1, 2, 3, 4} and R be a relation on the set A defined by:
R = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,2), (4,4)}.
Determine whether R is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or
transitive. If the relation fails to have a property, give an example showing why it fails in
this case. (30 points).
2) Suppose an online retailer identifies each member with a 6-digit account number.
Define the hashing function h, which takes the first 3 digits of an account number as 1
number and the last 3 digits as another number, adds them, and then applies the mod-
61 function. (30 points)
a) How many linked lists does this create?
b) Compute h(158686)
c) Compute h(328981)
3) Let A = {1, 2, 3, 6, 12, 18} and R be defined by xRy if and only if x|y. (30 points)
a) Draw the digraph of R. Below are images you can use to create the diagraph.
You may copy/paste the arrow and alter the directions and length as needed.
b) Draw the Hasse diagram of R. Below are images you can use to create the
diagraph. You may copy/paste the images and alter the directions and length
as needed.
••••••12 3 s121a.~
c) Give a subset of B of A that is linearly ordered with respect to R and contains
at least three elements.
4) (30 points)
a) Construct the tree of the algebraic expression:
8n – 2(m + 1)
b) Perform a preorder search of the tree to write this expression in prefix form.
c) Evaluate the prefix expression when m = 5 and n = 3 and list each step of the
solution.
•mnx+-~
5) Use vertex A as the initial vertex and use Prim’s algorithm to find a minimal spanning
tree for the following diagram. You do not need to draw the tree, but do list the edges
(as an ordered pair) in the order in which they are chosen. (25 points)
Edges:
6) Use Fleury’s algorithm to produce an Euler circuit for the following graph. Start at A
and label the edges in the order that you add them. (25 points)
2 3 4 5 6 7 8 9 10 11 12 13

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.