MATEMATIK Dag : 030604 Tid : 8.45 - 13.45. Göteborgs Universitet Hjälpmedel : Inga Peter Hegarty Vakt : Robert Berman 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) Hur många 16-siffriga kreditkortnummer innehåller 3 nollor och 4 ettor ? (ii) Låt n > 3 vara ett heltal. Hur många permutationer av {1, ..., n} resulterar i att minst tre tal förflyttas ?

2 (4x1p+2p). Man hänvisas till grafen G i Fig.1.

(i) Ange en Hamilton cykel i den ‘oviktade’ grafen G^{∗} eller förklara varför ingen sådan existerar.

(ii) Ange χ(G^{∗}) och en explicit optimal färgning av G^{∗}.

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

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.

(iv) Genomför Dijkstra’s algoritm för att hitta en kortast väg från A till K (skriv ner vilken kant du väljer i varje steg).

(v) Kör nu FF-algoitmen för att hitta ett maximalt flöde från A till K och en minimal cut-set (skriv ner vilken augmenting väg du väljer i varje steg).

3 (3p). Låt G vara en enkel graf med n noder. Formulera och bevisa en sats om det minsta antalet kanter som garanterar att G innehar en triangel.

4 (2p). Låt G vara en sammanhängande graf med minst 2 noder. Bevisa att G har minst 2 noder v med följande egenskap :

Om vi tar bort noden v och alla kanterna igenom den, då är den återstående grafen fortfarande sammanhängande.

5 (0.3p+1.3p+1.4p) (i) Definiera Catalan talen C_{n}.

(ii) Ange och förklara rekursion formeln för C_{n}. (iii) Bevisa att genererande funktionen F (x) för Catalan talen ges av

F (x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

6 (3p). Lös fullständigt följande recurrence relation (dvs ange en sluten formel för u_{n}) :

u_{n} = 4a_{n−1} + 5a_{n−2} + 3^{n} ∀ n ≥ 2,
u_{0} = 4, u_{1} = −1.

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