MATEMATIK Dag : 020604 Tid : 8.45 - 13.45. Göteborgs Universitet Hjälpmedel : Inga Peter Hegarty Vakt : Jonas Juel 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). Formulera och bevisa Philip Hall’s sats om matchningar i bipartite grafer.

2 (2p+2p). (i) Ange ett spanning träd av minimal vikt i den underliggande grafen i Fig. 1 (se bilaga). (ii) Ta från Fig. 1 bort de noder varifrån man inte kan nå h. Ange en kortast väg från a till h i grafen som finns kvar.

3 (3p). Låt G vara en 3-regulär graf. Visa att G har minst 2 olika cykler (Obs! Olika cykler får ha gemensamma kanter).

4 (3p) Som i F.2 (ii), ta från Fig. 1 bort de noder varifrån man inte kan nå h. Ange denna gång, i grafen som finns kvar, ett maximalt flöd från a till h och en minimal cut-set.

5 (0.2p+2.8p). (i) Låt t vara ett reelt tal och k ≥ 0 ett heltal. Definiera

binomialkoefficienten ( \begin{matrix}t \\ k \end{matrix} ).

(ii) Låt nu t = −m där m ≥ 0 är ett heltal. Bevisa att, om |x| < 1, då

(1 + x)^{t} = ∑_{k=0}^{∞} ( \begin{matrix}t \\ k \end{matrix} ) x^{k}.

Obs! Du behöver inte bry dig om konvergens frågor.

6 (3p). Låt 0 ≤ i ≤ k ≤ n vara heltal. Bevisa kombinatoriskt att

( \begin{matrix}n \\ k \end{matrix} ) × ( \begin{matrix}k \\ i \end{matrix} ) = ( \begin{matrix}n \\ i \end{matrix} ) × ( \begin{matrix}n − i \\ k − i \end{matrix} ) .

Obs! Med ett kombinatoriskt bevis menar jag att du ska visa att båda leden räknar samma saker, men på två olika sätt. Du får alltså INTE använda formeln för binomial koefficienterna från F.5 (i).

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

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

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

8 (3p). Ge en fullständig konstruktion av det projektiva planet över F_{2} och den motsvarande 2-designen.

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.