MAU22C00: ASSIGNMENT 4
DUE FRIDAY, MARCH 12 BEFORE MIDNIGHT
UPLOAD ON BLACKBOARD
Please attach a cover sheet with a declaration confirming that
you know and understand College rules on plagiarism. Details
can be found on http://tcd-ie.libguides.com/plagiarism/declaration.
1) (30 points) Let (V,E) be the graph with vertices a, b, c, d, e, f, g,
h, i, j, and k, and edges ab, bc, ac, cd, ch, de, eh, ef, eg, fg, hi, ij, hk,
jk, and jh.
(a) Draw this graph.
(b) Write down this graph’s incidence table and its incidence matrix.
(c) Write down this graph’s adjacency table and its adjacency matrix.
(d) Is this graph complete? Justify your answer.
(e) Is this graph bipartite? Justify your answer.
(f) Is this graph regular? Justify your answer.
(g) Does this graph have any regular subgraph? Justify your answer.
(h) Give an example of an isomorphism ϕ from the graph (V,E) to
itself satisfying that ϕ(i) = k.
(i) Is the isomorphism from part (h) unique or can you find another
isomorphism ψ that is distinct from ϕ but also satisfies that ψ(i) =
k? Justify your answer.
(j) Is this graph connected? Justify your answer.
(k) Does this graph have an Eulerian trail? Justify your answer.
(l) Does this graph have an Eulerian circuit? Justify your answer.
(m) Does this graph have a Hamiltonian circuit? Justify your answer.
(n) Is this graph a tree? Justify your answer.
2) (10 points) Prove that a connected graph (V,E) is a tree if and only
if adding an edge between any two vertices in (V,E) creates exactly
one circuit.
3) Consider the connected graph with vertices A, B, C, D, E, F , G,
H, I, J , K, and L and with edges, listed with associated costs, in the
following table:
2 MAU22C00: ASSIGNMENT 4
FJ JK CH EI DJ AB EH FK BG GJ BC AF
1 1 1 1 2 2 2 2 3 3 3 3
AC EF DF DL HI CE BD AD AE GL EK JL
3 4 4 4 5 6 6 6 6 7 7 8
(a) (2 points) Draw the graph and label each edge with its cost.
(b) (9 points) Determine the minimum spanning tree generated by
Kruskal’s Algorithm, where that algorithm is applied with the
queue specified in the table above. For each step of the algorithm,
write down the edge that is added.
(c) (9 points) Determine the minimum spanning tree generated by
Prim’s Algorithm, starting from the vertex D, where that algo-
rithm is applied with the queue specified in the table above. For
each step of the algorithm, write down the edge that is added.
4) (10 points) Let (V , E) be the directed graph with vertices A, B,
C, D, and E and edges (A,A), (C,A) (A,B), (B,C), (D,C), (C,E),
(E,E), and (E,D).
(a) Draw this graph.
(b) Write down this graph’s adjacency matrix.
(c) Give an example of an isomorphism ϕ from the graph (V , E) to
itself such that ϕ(A) = E. Note that an isomorphism of directed
graphs should also respect the direction of the edges.
5) (10 points) Let R be a relation on a set V = {a, b, c, d, e, f} given
by
R = {(a, c), (a, d), (c, c), (d, d), (b, b), (e, e), (b, e), (e, f), (f, e), (e, b), (f, f)}.
(a) Using the one-to-one correspondence between relations on finite
sets and directed graphs, draw the directed graph corresponding to
the relation R.
(b) Is R an equivalence relation? Justify your answer.
(c) If R is not an equivalence relation, which ordered pairs would have
to be added to R to make it into an equivalence relation?

欢迎咨询51作业君