MATEMATIK Dag : xxxxxx Tid : 8.45 - 13.45. Göteborgs Universitet Hjälpmedel : Inga Peter Hegarty Vakt : Andrew Wiles 0740-350646.

Tentamenskriving i Diskret Matematik (MAN 240)

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

1 (1p+1p) (i) Ange en övre gräns på antalet bilar i Sverige, med tanke på att inga två bilar får ha samma registreringsskylt (Obs! Gör inga ytterligare antaganden). (ii) Hur många ord av längd 9 i bokståverna A,B,C innehåller minst 5 st. A:en ?

2 (3p). Formulera och bevisa Dirac’s sats om Hamitlon cykler i enkla grafer.

3 (4x1p+2p). Men hänvisning till grafen i Fig. 1,

(i) Ange det kromatiska talet av den oviktade grafen. (ii) Ange en matchning av maximal storlek i den oviktade grafen. (iii) Ange ett spanning träd av minimal vikt i grafen.

Rikta nu grafen på följande sätt : alla vertikala kanter ska riktas uppåt och alla andra kanter från vänster till höger.

(iv) Ange en kortast väg från a till z i den riktade grafen.

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

4 (1.5p+1.5p). Låt G vara en enkel graf med 21 noder och antag att för varje par x ≠ y av noder så gäller att

deg(x) + deg(y) ≥ 20.

Avgör om var och ett av föjlande påståenden är sant eller falsk Om det är sant ge ett bevis, om det är falsk ge ett motexempel :

(i) G är sammanhängande, (ii) G har en triangel.

5 (1p+2p) (i) Formulera Inclusion-Exclusion principen. (ii) Ange en formel för d_{n} = antalet ‘derangements’ av {1, ..., n}, och bevisa formeln med hjälp av I-E principen.

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

u_{n+2} = 6u_{n+1} − 9u_{n} + 2n + 3,
u_{0} = 3, u_{1} = 4.

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

Obs! Tentan beräknas vara färdigrättad den 10 juni. 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.