Izpit pri predmetu DISKRETNA MATEMATIKA 2

Univerza v Mariboru

Fakulteta za naravoslovje in matematiko Oddelek za matematiko in ra£unalni²tvo

Izpit pri predmetu DISKRETNA MATEMATIKA 2

13.6.2017

1. [25] Na koliko razli£nih na£inov lahko 60 enakih zrn razdelimo med sedem ptic tako, da vsaka izmed njih dobi vsaj 4 in ne ve£ kot 10 zrn?

2. [25] Naj bop≥2,H_p Hammingova koda s kodnimi besedami dolºinen = 2^p−1in z dimenzijo kode k. Naj box=x₁. . . x_n ∈ H_p. Dokaºi naslednji trditvi.

(a) ƒex_i = 0 za vsak i≤k, potem jex_i = 0 za vsaki∈ {1, . . . , n}. (b) ω(x)6= 1.

3. [25] ’irina delno urejene mnoºice P = (X,≤) je velikost najdalj²e antiverige v P. Dokaºi, da je dimenzija poljubne delno urejene mnoºice P navzgor omejena s ²irino od P.

4. [25] Ali veljata naslednji trditvi? Odgovora utemelji.

(a) DualG^∗ nepovezanega grafa G vloºenega v ravnino je povezan.

(b) Za vsak graf G vloºen v ravnino velja: (G^∗)^∗ ∼=G.

Vse odgovore je potrebno utemeljiti.