Description
Question 1: Find a Nonisomorphic Graph
Take a look at the following simple graph G:
a) Draw another graph H that has the same number of vertices and edges and the same
degrees as G but is not isomorphic to G.
b) Is there another invariant we discussed besides the number of vertices and edges and
the degrees, such as the length of circuits and paths, that could be used to show that G
and H are nonisomorphic? If so, please state how this invariant differs between the
two graphs.
Question 2: … And More about Graphs
a) In class we showed that the cycle C6 is bipartite. Which of the cycles C3, C4, C5, and
C7 are bipartite as well?
b) Bonus: Based on (a) there seems to be a rule that tells us for which numbers n the
cycle Cn is bipartite. What is that rule? Give an argument for this rule to be correct for
all integers n > 2.
c) How many nonisomorphic subgraphs does C4 have? Draw them.
d) Develop an equation for computing the number of edges |En| for any wheel Wn.
Explain your reasoning and test your equation by computing |E3|.
Question 3: Dijkstra in Action
Use Dijkstra’s algorithm to compute the shortest path from A to I, where edge labels
indicate the distance (or cost) between vertices. For each iteration, write down the
shortest path (i.e., its length and the vertices in it) from A to each vertex that has been
found so far, and also indicate which vertices are currently in the set S.
Question 4: Trees
a) How many vertices does a full 4-ary tree with 100 internal vertices have?
b) How many vertices and how many leaves does a complete m-ary tree of height h
have?
c) Build a binary search tree for the words the, final, exam, will, contain, at, least, one,
question, about, and trees using alphabetical order and adding words in the same
order as listed here.
d) Represent the expressions (x + x⋅y) + (x/y) and x + ((x⋅y + x)/y) using two binary trees.
e) How many non-isomorphic trees with four vertices are there? Draw them.
f) Bonus: Show that a full m-ary tree with l leaves has (l – 1)/(m – 1) internal vertices.
A
B
C
D
E
F
G
H
I
1
3
7
1
2
1
2
1
6
4
9 8
