MATEMATIK Dag : 030823 Tid : 8.45 - 13.45. Göteborgs Universitet Hjälpmedel : Inga Peter Hegarty Vakt : Johanna Pejlare 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 7-siffriga decimala tal innehåller minst tre 9:or ? (ii) I somras reste jag igenom 8 länder : Danmark, Frankrike, Italien, Liechtenstein, Schweiz, Slovenien, Tyskland och Östterrike.

Hur många möjligheter finns det då för ordningen av länderna längs min resa om jag bara berättar för dig att Danmark kom någon gång före Italien, som i sin tur kom någon gång före Liechtenstein.

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

(i) Ange en Hamilton cykel i den ‘oriktade’ 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^{∗}.

(iv) Genomför Dijkstra’s algoritm för att hitta en kortaste väg från s till t i G (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 s till t och en minimal cut-set (skriv ner vilken augmenting väg du väljer i varje steg).

3 (3p). Formulera och bevisa Philip Halls äktenskap sats.

4 (2p). Låt G vara en sammanhängande graf med n noder och n kanter, för något positivt heltal n. Ange med bevis en optimal övre gräns på χ(G).

5 (3p). Formulera och bevisa binomial satsen för negativa heltalsexponenter.

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

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

u_{0} = 2, u_{1} = 3.

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