Faculty of Mathematics of the University of Duisburg-Essen, Campus Duisburg
Exam: Discrete Mathematics, WS 19/20
You are permitted to bring one DIN A4 page of personally handwritten crib notes (both sides) and a
simple non-programmable calculator to use during the exam. This exam contains 5 problems.
Justify your answers.
Time: 120 minutes.
Problem 1 (20 points)
Solve the following recursion by the generating function method (i.e., give an explicit formula for the n-th
element an):
a0 = 0, a1 = 1, an − 3an−1 + 2an−2 = 0
Problem 2 (20 points)
(a) For what values of m does exist a not closed euler line and/or a closed euler line for the m-regular
graph Km?
(b) For what values of m and n does exist a not closed euler line and/or a closed euler line for the complete
bipartite graph Km,n?
(c) Does there exist a not closed euler line and/or a closed euler line for the following graph G(V, E)?
V = {a, b, c, d, e}, E = {{a, b}, {a, c}, {a, d}, {b, d}, {b, e}, {c, d}, {d, e}}
If yes, give this line as a walk.
(d) Draw all trees with at most 5 vertices. Do not draw isomorphic graphs.
Problem 3 (20 points)
Given is the following graph:
(a) Does there exist a complete matching? Answer this question without using the algorithm to find a
maximum matching.
(b) Start with the matching M = {{2, a}, {3, c}} to find a maximum matching by using the alternating
path method.
(c) How many complete matchings do exist in the bipartite graph Kn,n?
Problem 4 (20 points)
Consider the following Petri nets:
(a) Describe the Petri nets by giving the reachability graphs. What are the main differences between both
Petri nets?
(b) Are the Petri nets live, weak live, bounded, reversible, persistent?
(c) Is a Petri net in general a bipartite graph? If so, give the partition of the nodes and explain why it is
bipartite.
Problem 5 (20 points)
Given is a linear code C ⊆ Z
(a) Determine a Generatormatrix G for the same code.
(b) Give all codewords of the linear code. What is the dimension of the code?
(c) What can be said about error correction and error detection?
(d) Encode the information m1 = (1, 0) and m2 = (1, 2).