代做Mathematics编程、代写Java，Python，CS程序设计

日期：2021-03-25 11:11

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).