Univerza v Mariboru
Fakulteta za naravoslovje in matematiko Oddelek za matematiko in ra£unalni²tvo
Izpit pri predmetu DISKRETNA MATEMATIKA 2
24.5.2017
1. [25] Poi²£i rodovno funkcijo zaporedja (ar), kjer je ar ²tevilo na£inov razporeditve r enakih objektov v pet razli£nih posod, kjer je v prvih dveh posodah sodo ²tevilo objektov manj²e od 12, v ostalih pa med 3 in 5 objektov. Izra£unaj a9 ina24. 2. [25] Na koliko na£inov lahko pobarvamo povezave tetraedra
(a) s £rno in rde£o barvo?
(b) tako, da bodo ²tiri povezave £rne in dve rde£i?
3. [25] Naj bon ≥k(k+ 1)in naj bodo vozli²£a grafaGn,kpostavljena tako, da tvorijo vozli²£a enakostrani£negan-kotnika. Vsako vozli²£e je sosednje sknajbliºjimi sosedi v vsako smer. Dokaºi, da je
χ(Gn,k) =
k+ 1; k+ 1 deli n,
k+ 2; sicer.
4. [25] Naj boG graf z δ(G)≥ |V(G)| −2. Dokaºi, da jeκ(G) =δ(G). Dokaºi ²e, da za vsak n≥4 obstaja grafG z δ(G)<|V(G)| −2za katerega velja κ(G)6=δ(G).
Vse odgovore je potrebno utemeljiti.