MAN 240 : Diskret matematik

Tentamen 240802

Lösningar

F.1 See Theorem 8.5 in the book. Here is a proof for the sake of completeness.

⇐ Suppose G is connected, with n nodes and n − 1 edges. We prove by induction on n that G has no cycles. If n = 2, then G is a single edge, and hence obviously has no cycles. Suppose G has k edges and k + 1 nodes. Since

∑_{v∈V (G)} deg(v) = 2|E(G)| = 2k < 2(k + 1),

it follows that G has a vertex v of degree 1. Let G^{∗} be the graph obtained by removing from G the vertex v and its’ single adjacent edge. Then G^{∗} must still be connected. But G^{∗} has k nodes and k − 1 edges. By the induction hypothesis, G^{∗} has no cycles. But then neither does G.

⇒ Suppose G is connected with n nodes and no cycles. We prove by induction on n that G has n − 1 edges. Evidently, this is the case if n = 2. So suppose G is connected, has k + 1 nodes and no cycles. We must show G has k edges.

Let v be any vertex in G. Let G^{∗} be the graph obtained by deleting from G the vertex v and all its’ adjacent edges. Let C_{1}, ..., C_{t} denote the connected components of G^{∗}. Then

(i) since G has no cycles, neither has any C_{i}, hence by the induction hypothesis

|V (C_{i})| = |E(C_{i}| + 1, i = 1, ..., t.  (1)

(ii) since G is connected, there is at least one edge in G from v to each C_{i}. But since G has no cycles, there is therefore exactly one edge from v to each C_{i}, that is, deg(v) = t. Hence, the total number of edges in G is

t + ∑_{i=1}^{t} |E(C_{i})|

= t + ∑_{i=1}^{t} (|V (C_{i}| − 1) , by (1)

= ∑_{i=1}^{t} |V (C_{i}|

= |V (G)| − 1,

as required.

F.2 I label the nodes of the graph as follows : a to the left, z to the right as in the diagram ; reading downwards on the left b, c, d, e ; reading downwards on the right f, g, h, i.

(i) G has perfect matchings. An example of such a matching is that consisting of the 5 edges

{a, b}, {c, d}, {e, i}, {f, z}, {g, h}.

(ii) Use DFS, starting, say, from the vertex a, to build up the follwowing sequence of edges in a MST :

{a, b}, {a, e}, {e, d}, {d, h}, {h, c}, {c, f}, {f, g}, {g, z}, {h, i}.

The total weight of this tree is 1 + 3 + 2 + 3 + 1 + 1 + 2 + 2 + 3 = 18.

(iii) The following is an example of a maximal flow

Edge Flow Edge Flow
{a, b} 1 {d, h} 3
{a, c} 6 {e, h} 0
{a, d} 4 {e, i} 3
{a, e} 3 {g, f} 0
{c, b}  4 {h, g} 0
{d, c} 1 {i, h} 0
{e, d} 0 {f, z} 5
{b, f} 5 {g, z} 2
{c, f} 0 {h, z} 4
{c, g} 2 {i, z} 3
{c, h} 1

This flow has strength 14. The corresponding minimal cut (S, T) is

S = {a, b, c, d, f, g}, T = {e, h, i, z}.

Observe that

c(S, T) = c(a, e) + c(c, h) + c(d, h) + c(f, z) + c(g, z) = 3 + 1 + 3 + 5 + 2 = 14.

F.3 (i) Φ(G) is the minimal number of colors needed to color the edges of G, if edges with a vertex in common must receive different colors.

(ii) Theorem 10.2 in the book.

F.4 Let S have n elements, say S = {1, ..., n}. Let E denote the collection of subsets of S having an even number of elements, and O the collection of subsets having an odd number of elements. We must describe a bijection f : E → O. We do so explicitly as follows : Let X ∈ E, that is X is a subset of S having an even number of elements. There are two cases :

(i) if n ∈ X, set f(X) = X\{n}. (ii) if n ∉ X, set f(X) = X ∪ {n}.

It’s easy to check that f is a bijection (if you’re not convinced, write it out in full for n = 4, say).

F.5 Let

E(x) = ∑_{n=0}^{∞} u_{n} \frac{x^{n}}{n!}

denote the exponential generating function of the sequence (u_{n}). Noting that

∑_{n=0}^{∞} n\frac{x^{n}}{n!} = xe^{x},

we conclude that E(x) satisfies the differential equation

2E′′ − 7E′ + 3E = xe^{x}.  (2)

We find the general solution to (2) in the usual way. First, the general solution of the homogeneous equation is

E_{h}(x) = C_{1}e^{3x} + C_{2}e^{\frac{1}{2} x}.

A particular solution to the inhomogeneous equation will have the form

E_{p}(x) = (Ax + B)e^{x}.

Substituting into the lhs of (2) we may solve for A, B as A = −\frac{1}{2}, B = \frac{3}{4}. Hence the general solution to (2) is

E(x) = C_{1}e^{3x} + C_{2}e^{\frac{1}{2} x} + (−\frac{1}{2}x + \frac{3}{4}) e^{x}.

To solve for C_{1} and C_{2} we use the initial conditions

u_{0} = E(0) = 1, u_{1} = E′(0) = 2.

After the required computation, we find that

C_{1} = \frac{13}{20}, C_{2} = −\frac{2}{5}.

We thus finally obtain the desired formula for u_{n}, namely

u_{n} = \frac{13}{20} · 3^{n} − \frac{2}{5} (\frac{1}{2})^{n} − \frac{n}{2} + \frac{3}{4}.

F.6 f(n − 2, k − 1) is the number of sets satisfying the condition which contain the number n, and f(n − 1, k) is the number of sets satisfying the condition which do not contain n.

F.7 Let K = {x^{2} mod 23 : x ∈ F_{23}^{∗}}.

The blocks of the design are the 23 translates of K modulo 23 - see Theorem 16.8. Explicitly,

1^{2} ≡ 1, 2^{2} ≡ 4, 3^{2} ≡ 9, 4^{2} ≡ 16, 5^{2} ≡ 2, 6^{2} ≡ 13,
7^{2} ≡ 3, 8^{2} ≡ 18, 9^{2} ≡ 12, 10^{2} ≡ 8, 11^{2} ≡ 6,

so that

K = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}.