MATEMATIK Dag : 020824 Tid : 8.45 - 13.45. Göteborgs Universitet Hjälpmedel : Inga Peter Hegarty Vakt : Håkan Samuelsson 0740-350646.

Tentamenskriving i Diskret Matematik (MAN 240)

≥ 12 poäng, inkl. bonus från inlämningsuppgifterna, ger godkännt. Denna gräns kan minskas efteråt.

1 (3p). Låt G vara en sammanhängande graf med n noder. Bevisa att G saknar cykler om och endast om G har n − 1 kanter.

2 (2p+2p+3p). Man hänvisas till grafen G i Fig. 10-5 (a).

(i) Ange en maximal matchning i den ‘unweighted’ grafen.

(ii) Ange ett spanning träd av minimal vikt i G.

(iii) Rikta nu G enligt följande regler : (a) alla vertikala kanter riktas uppåt (b) alla andra kanter riktas från vänster till höger.

Ange nu ett maximalt flöde från a till z och en minimal cut-set.

3 (0.2p+2.8p). (i) Definiera det kant-kromatiska talet Φ(G) av en graf G.

(ii) Låt G vara en bipartite graf. Bevisa att Φ(G) är lika med den maximala graden av en nod i G.

4 (3p). Låt S vara en ändlig mängd. Bevisa kombinatoriskt att antalet delmängder till S som har ett jämnt antal element är lika med antalet delmängder som har ett udda antal element. Obs! Med ett kombinatoriskt bevis menar jag att du ska ange en explicit 1-1 korrepsondens mellan ‘jämna’ och ‘udda’ delmängder.

5 (3p). Låt u_{0}, u_{1}, ... vara en följd av heltal som satisfierar recurrence relationen

2u_{n+2} = 7u_{n+1} − 3u_{n} + n,
u_{0} = 1, u_{1} = 2.

Ange en sluten formel för u_{n}.

6 (3p). Låt n, k vara positiva heltal med n ≥ 2 och k ≤ n. Låt f(n, k) beteckna antalet delmängder till {1, ..., n} som (a) innehåller k st. element (b) ej innehåller två konsekutiva heltal. Bevisa att

f(n, k) = f(n − 2, k − 1) + f(n − 1, k).

Obs! Du behöver INTE lösa denna recurrence relation.

7 (3p). Ge en explicit konstruktion av en 2 − (23, 11, 5) design. (Ledning : Använd en lämplig differens mängd i en lämplig F_{q}).

Obs! Tentan beräknas vara färdigrättad den 29 augusti. Då kan den hämtas i mottagningsrummet mellan kl. 12:30-13:00. Tentamensresultat lämnas också ut per telefon 772 35 09 efter kl. 14:00.