MAN 240 : Diskret matematik Tentamen 040602 Lösningar

F.1 Sats 10.4. F.2 (i) Använd den giriga algoritmen för att konstruera ett minimalt spanning träd. Om vi börjar med kanten {j, g}, t.ex., då kunde vi bygga t.ex. följande träd

kant vikt
{j, g} 2
{j, k} 4
{f, g} 6
{g, c} 6
{c, b} 6
{c, h} 7
{h, i} 6
{i, n} 2
{n, m} 2
{c, d} 8
{l, m} 8
{j, a} 9
{d, e} 10
{i, z} 10

Den totala vikten av trädet är 86. Notera att vi har olika val i flera steg och att detta inte är det unika trädet av vikt 86. (ii) Använd BFS för att bygga upp ett träd med följande sekvens av kanter :

{a, j}, {a, b}, {a, f}, {j, g}, {j, k}, {b, c}, {c, h} eller {g, h}. Då ser vi att den kortaste vägen från a till h har total längd 23, och det finns två möjligheter för denna väg, nämligen a−b−c−h eller a−j −g −h. F.3 G är 3-regulär om och endast om varje sammanhängande komponent av G är det. WLOG, får vi därför antaga att G är sammanhängande. Låt G ha n noder. Eftersom varje nod har grad 3 då har g totalt 3n/2 kanter. Eftersom G är sammanhängande, den har ett spanning träd T. T har n − 1 kanter. För alla n > 1 har vi att 3n/2 ≥ (n − 1) + 2 så det finns minst två kanter av G utanför trädet T. Välj två sådana kanter, säg e och f. Delgrafen till G som består av T ∪ {e} måste då innehålla en cykel C_{1} och denna cykel måste deeutom inkludera kanten e. PSS, måste delgrafen bestående av T ∪{f} innehålla en cykel C_{2} som inkluderar kanten f. Därför är C_{1} och C_{2} två olika cykler i G, v.s.v.

F.4 Det är inte så svårt att se att det går att hitta ett flöd genom grafen där alla tre kanter utifrån a är mättade. Ett sådant flöd måste alltså vara maximalt och S = {a} är en minimal cut-set. Här är ett explicit exempel av ett sådant flöd f :

f(a, b) = 10 f(a, f) = 11 f(a, j) = 9,
f(b, c) = 6 f(f, b) = 8 f(j, f) = 3,
f(j, k) = 4 f(j, g) = 2 f(f, g) = 6,
f(b, g) = 12 f(g, k) = 7 f(g, c) = 6,
f(c, d) = 5 f(d, h) = 5 f(c, h) = 7,
f(g, h) = 7 f(k, h) = 11 f(k, l) = 0,
f(l, h) = 0.

F.5 Sats 18.3 i Biggs.

F.6 Låt S vara en mängd med n element, säg S = {1, 2, ..., n}. Både leden räknar antalet par (A, B) där

(i) A är en delmängd till S och B en delmängd till A, (ii) A har k element och B har i element.

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

E′′ − 5E′ + 6E = xe^{x}.  (1)

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

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

A particular solution to the inhomogeneous equation will have the form

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

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

E(x) = C_{1}e^{2x} + C_{2}e^{3x} + (\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) = 3, u_{1} = E′(0) = 4.

After the required computation, we find that

C_{1} = 4, C_{2} = −\frac{7}{4}.

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

u_{n} = 4 · 2^{n} − \frac{7}{4} · 3^{n} + \frac{n}{2} + \frac{3}{4}.

F.8 Here’s an explicit description of the projective plane over F_{2} and of the associated 2 − (7, 3, 1) design : this being a 2 − (q^{2} + q + 1, q + 1, 1) design with q = 2.

F_{2} is the finite field of order 2. We have F_{2} = Z/2Z = {0, 1} with addition and multiplication rules

0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0,
0 · 0 = 0, 0 · 1 = 0, 1 · 1 = 1.

We have

V = F_{2}^{3} = {(x, y, z) : x, y, z ∈ F_{2}},

where addition and scalar multiplication are componentwise.

The points of the design are the lines through the origin (0, 0, 0) in V, that is, all 1-dimensional subspaces of V. There are 2^{3} − 1 = 7 non-zero elements v of V, and any such v determines a 1-dimensional subspace. We write these seven lines as

1 = (1, 0, 0)
2 = (0, 1, 0)
3 = (0, 0, 1)
4 = (1, 1, 0)
5 = (1, 0, 1)
6 = (0, 1, 1)
7 = (1, 1, 1)

The orthogonal complements of these spaces are the seven 2-dimensional subspaces of V. Each of these contains 3 one-dimensional subspaces. Explicitly, we have

1^{⊥} ∋ {2,3,6},
2^{⊥} ∋ {1,3,5},
3^{⊥} ∋ {1,2,4},
4^{⊥} ∋ {3,4,7},
5^{⊥} ∋ {2,5,7},
6^{⊥} ∋ {1,6,7},
7^{⊥} ∋ {4,5,6}.

To check, for example, that 7 is orthogonal to each of 4,5,6, just check that the scalar product of 7 with each is zero. For example,

7 · 4 = (1, 1, 1) · (1, 1, 0) = 1 · 1 + 1 · 1 + 1 · 0 = 1 + 1 + 0 = 0.

Hence, we get the following 2 − (7, 3, 1) design

2 1 1 3 2 1 4
3 3 2 4 5 6 5
6 5 4 7 7 7 6