\documentclass[a4paper,12pt]{article}
%%\pagestyle{empty}

\usepackage[left=15mm,right=20mm,top=15mm,bottom=22mm]{geometry}
\usepackage{booktabs, multicol}
\usepackage{makeidx, graphicx, amsmath, amssymb, amsthm, ae}
\usepackage[bosnian]{babel}
%%\usepackage[cp1250]{inputenc}

\usepackage[gen]{eurosym}
\usepackage[normalem]{ulem} %%sout

\usepackage{enumitem}

\usepackage{tikz,textcomp}
\newfont\fiverm{cmr5}

\usepackage{tkz-berge}



\usepackage{stackengine,hvfloat,booktabs}



\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}





\def\cm{{\mbox{\rm cm}}}
\def\Inn{{\mbox{\rm Inn}}}

\def\Sym{{\mbox{\rm Sym}}}
\def\RotSym{{\mbox{\rm RotSym}}}
\def\lcm{{\mbox{\rm lcm}}}
\def\id{{\mbox{\rm id}}}




%%\def\NN{{\mbox{$\mathbb N$}}}
\def\RR{{\mbox{$\mathbb R$}}}
\def\CC{{\mbox{$\mathbb C$}}}
\def\T{{\mbox{$\mathbb T$}}}
\def\H{{\mbox{$\mathbb H$}}}
\def\Z{{\mbox{$\mathbb Z$}}}
\def\Q{{\mbox{$\mathbb Q$}}}
\def\F{{\mbox{$\mathbb F$}}}
\def\C{{\mbox{$\mathbb C$}}}
\def\E{{\mbox{$\mathcal{E}$}}}
\def\M{{\mbox{$\mathcal{M}$}}}

\def\ZZplus{{\mbox{$\mathbb Z_+$}}}

\def\S{{\mbox{$\mathcal{S}$}}}
\def\L{{\mbox{$\mathcal{L}$}}}
\def\G{{\mbox{$\mathcal{G}$}}}
\def\P{{\mbox{$\mathcal{P}$}}}

\def\B{{\mbox{$\mathcal{B}$}}}
\def\A{{\mbox{$\mathcal{A}$}}}
\def\O{{\mbox{$\mathcal{O}$}}}

\def\X{{\mbox{$\mathcal{X}$}}}
\def\V{{\mbox{$\mathcal{V}$}}}
\def\Y{{\mbox{$\mathcal{Y}$}}}
\def\W{{\mbox{$\mathcal{W}$}}}
\def\dist{{\mbox{\rm dist}}}
\def\GL{{\mbox{\rm GL}}}
\def\SL{{\mbox{\rm SL}}}
\def\NSD{{\mbox{\rm gcd}}}

\def\exc{{\mbox{\rm exc}}}
\def\ecc{{\mbox{\rm ecc}}}
\def\Alt{{\mbox{\rm Alt}}}
\def\Aut{{\mbox{\rm Aut}}}
\def\Hom{{\mbox{\rm Hom}}}
\def\spec{{\mbox{\rm spec}}}
\def\rank{{\mbox{\rm rank}}}
\def\rang{{\mbox{\rm rang}}}
\def\mod{{\mbox{\rm mod}}}
\def\div{{\mbox{\rm div}}}
\def\trag{{\mbox{\rm trag}}}
\def\tr{{\mbox{\rm tr}}}
\def\dim{{\mbox{\rm dim}}}
\def\diag{{\mbox{\rm diag}}}
\def\Mat{{\mbox{\rm Mat}}}
\def\Sim{{\mbox{\rm Sim}}}
\def\ker{{\mbox{\rm ker}}}
\def\im{{\mbox{\rm im}}}
\def\mp{{\mbox{\rm mp}}}
\def\gcd{{\mbox{\rm gcd}}}

\def\K{{\mbox{$\pmb{K}$}}}
\def\J{{\mbox{$\pmb{J}$}}}
\def\I{{\mbox{$\pmb{I}$}}}
\def\j{{\mbox{$\pmb{j}$}}}
\def\0{{\mbox{\boldmath{$0$}}}}
\def\algmult{{\mbox{\rm alg\,mult}}}
\def\geomult{{\mbox{\rm geo\,mult}}}
\def\du{{\mbox{\rm \,d$u$}}}
\def\dx{{\mbox{\rm \,d$x$}}}
\def\dt{{\mbox{\rm \,d$t$}}}
\def\dy{{\mbox{\rm \,d$y$}}}
\def\dz{{\mbox{\rm \,d$z$}}}
\def\tg{{\mbox{\rm tg\,}}}
\def\arctg{{\mbox{\rm arc\,tg\,}}}
\def\arcsin{{\mbox{\rm arc\,sin\,}}}
\def\ctg{{\mbox{\rm ctg\,}}}

\def\a{{\mbox{\boldmath $a$}}}
\def\q{{\mbox{\boldmath $q$}}}
\def\b{{\mbox{\boldmath $b$}}}
\def\j{\mbox{\boldmath $j$}}
%%\def\u{{\mbox {\boldmath $u$}}}
\def\m{{\mbox {\boldmath $m$}}}
\def\n{{\mbox {\boldmath $n$}}}
\def\vv{{\mbox {\boldmath $v$}}}
\def\w{{\mbox {\boldmath $w$}}}
\def\x{\mbox{\boldmath $x$}}
\def\h{{\mbox {\boldmath $h$}}}
\def\y{\mbox{\boldmath $y$}}
\def\0{\mbox{\boldmath $0$}}
\def\z{\mbox{\boldmath $z$}}
\def\p{\mbox{\boldmath $p$}}
\def\l{\mbox{$\lambda$}}

\def\e{{\mbox{\boldmath $e$}}}
\def\ro{{\mbox{\boldmath $\rho$}}}

\def\ra{\rightarrow}
\def\Ra{\Rightarrow}
\def\La{\Leftarrow}




\DeclareMathOperator{\NN}{{\mathbb N}}
\DeclareMathOperator{\ZZ}{{\mathbb Z}}




\input prepictex
\input pictex
\input postpictex

\def\nula{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.4 -0.8 -0.4 0.4 /
\plot -0.4 -0.8 -0.4 0.8 /
\plot -0.4 -0.8 0.4 -0.8 /
\plot 0.4 0.8 0.4 -0.8 /
\plot 0.4 0.8 -0.4 0.8 /
\plot -0.4 0 0.4 0 /
}
\endpicture}}


\def\prva{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 0 -0.8 0.8 /
\plot -0.8 0.8 0 0.8 /
\plot 0 0.8 0 0 /
\plot 0 0 0.8 0 /
\plot 0.8 0 0.8 -0.8 /
\plot 0.8 -0.8 -0.8 -0.8 /
\plot -0.8 -0.8 -0.8 0 /
\plot -0.8 0.8 0.8 0.8 /
\plot 0.8 0 0.8 0.8 /
}
\endpicture}}



\def\druga{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 0 -0.8 0 /
\plot 0 0 0 -0.8 /
}
\endpicture}}



\def\tretja{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 0 0.8 0 /
\plot 0 0 0 -0.8 /
}
\endpicture}}



\def\cetrta{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 0 -0.8 0 /
\plot 0 0 0 0.8 /
}
\endpicture}}


\def\peta{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 -0.8 0 0.8 /
\plot -0.8 0 0.8 0 /
}
\endpicture}}





\newcommand{\ds}{\displaystyle}

\newcommand{\ol}{\overline}






\newcommand\barbelow[1]{\stackunder[2pt]{$#1$}{\rule{1.5ex}{.1ex}}}





\newtheoremstyle{zaFiguru} %name
  {3.4mm}    %Space above, empty = `usual value'
  {3.5mm}    %Space below
  {\rm}   %Body font
  {}     %Indent amount (empty = no indent, \parindent = para indent)
  {\bf}   %Thm head font
  {}      %Punctuation after thm head
  {2mm}   %Space after thm head: \newline = linebreak
  {\thmname{#1} \thmnumber{\Large #2.}\thmnote{\,(#3)}}       %Thm head spec





%%\swapnumbers
\theoremstyle{zaFiguru}
\newtheorem{zad}{}


\def\ug{{{\measuredangle}}}
\def\tr{{{\triangle}}}


\setlength{\textheight}{262mm}
\setlength{\textwidth}{180mm}
\begin{document}
\raggedright



\section{Množice in matematična indukcija.}





\begin{zad}
Naj bo $A$ množica moči $n\in\ZZ^+$ in naj bo $\P(A)$ potenčna množica množice $A$. Z matematično indukcijo dokažite naslednjo enakost:
$$
|\P(A)|=2^n.
$$
\end{zad}



\begin{zad}
Pokažite naslednjo trditev: če $n$ knjig razdelimo v $m$ škatel, bo ena od škatel vsebovala vsaj $\left\lfloor\frac{n - 1}{m}\right\rfloor + 1$ knjig. Podrobno razložite vsak korak svojega dokaza.
\end{zad}









\section{Osnovna kombinatorična načela: Načelo vsote. Načelo produkta. Načelo enakosti.}






\begin{zad}
Predpostavimo, da imamo na voljo $5$ (identičnih) pomaranč in $8$ (identičnih) jabolk. Koliko različnih nepraznih zbirk sadja lahko naredimo, če zbirka lahko vsebuje največ $3$ pomaranče?
Preden izračunate numerično vrednost, podajte vsaj tri primere izbir, ki jih lahko naredimo.
\end{zad}







\begin{zad}
Koliko različnih petmestnih števil lahko sestavimo iz števk $1$, $2$, $3$ in $4$, če
\begin{enumerate}[label=\rm(\alph*)]
\item ni dodatnih omejitev?
\item mora biti vsota števk soda?
\item mora biti sodih števk več kot lihih?
\end{enumerate}
Rezultat naj bo podan kot numerična vrednost.
\end{zad}







\begin{zad}
Koliko različnih $4$-mestnih števil lahko sestavimo iz cifer $2, 3, 5, 6, 7$ in $8$, če upoštevamo naslednje pogoje:
\begin{enumerate}[label=\rm(\alph*)]
\item cifre v številu so paroma različne?
\item vse cifre v številu so enake?
\item število je večje od $5688$?
\item število je deljivo s $5$?
\item število je palindrom\footnote{Palindrom je niz, ki se bere enako naprej in nazaj. Primeri: nežen, 12321, potop, dovod, omilimo, radar, V elipsi spi lev,\ldots}?
\item število je sodo in je palindrom?
\end{enumerate}
Rezultat naj bo podan kot točna numerična vrednost. V vseh delih naloge, preden izračunate numerične vrednosti, podajte vsaj tri primere $4$-mestnih števil, ki jih lahko naredimo.
\end{zad}






\begin{zad}
Na koliko različnih načinov lahko formiramo niz dolg $5$ črk, če imamo na voljo črke $x$, $y$, $a$, $b$, $u$ in $v$ in upoštevamo naslednje pogoje
\begin{enumerate}[label=\rm(\roman*)]
\item črke v nizu se lahko ponavljajo?
\item črke v nizu se ne smejo ponavljati, niz pa vsebuje črko $x$?
\item črke v nizu se lahko ponavljajo, niz pa vsebuje črko $x$?
\end{enumerate}
\end{zad}







\begin{zad}
Naj bo $A = \{-4, -3, -2, -1, 1, 2, 3, 4\}$. Na koliko načinov lahko iz množice $A$ izberemo štiri števila, če morajo izbrana števila biti različna po absolutni vrednosti
\begin{enumerate}[label=\rm(\alph*)]
\item in je vrstni red pomemben.
\item in vrstni red ni pomemben.
\end{enumerate}
\end{zad}













\section{Dirichletovo načelo}



\begin{zad}
V družini Dioklecijan je $12$ otrok. Dokažite, da sta vsaj dva družinska člana rojena v istem mesecu.
\end{zad}



\begin{zad}
Koliko študentov mora biti na pisnem izpitu iz Diskretne matematike II, da zagotovimo, da bodo vsaj štirje študenti prejeli enako število točk, če je izpit ocenjen na lestvici od $0$ do $100$ točk?
\end{zad}






\begin{zad}
Danih imamo pet točk znotraj enakostraničnega trikotnika z dolžino stranice $2$ cm. Pokažite, da obstajata dve točki, ki ležita na razdalji največ $1$ cm.
\end{zad}


\begin{zad}
Na zabavi se je zbralo $8$ študentov, starih med $18$ in $30$ let. Utemeljite, da med njimi lahko izberemo dve različni skupini oseb, tako da je vsota let oseb iz ene skupine enaka vsoti let oseb iz druge skupine.
\end{zad}






\begin{zad}
Iz množice $\{1,2,\ldots, 2n\}$ izberemo $n+1$ različnih števil. 
Dokažite, da sta med izbranimi celimi števili vedno dve, katerih največji skupni delitelj je $1$.
\end{zad}






\begin{zad}
V Luko Koper vsak teden pripluje $200$ tovornih ladij. Utemeljite, da obstajata vsaj dve ladji, ki v pristanišče priplujeta v razmaku manj kot ene ure.
\end{zad}








\begin{zad}
Na družinskem srečanju se je zbralo devet oseb, starih med $18$ in $58$ let. Utemeljite, da med njimi lahko izberemo dve različni skupini oseb, tako da je vsota let oseb iz ene skupine enaka vsoti let oseb iz druge skupine.
\end{zad}






\begin{zad}
Opazujemo igro $10$ teniških igralcev (ena na ena). Vsak od njih igra vsaj eno tekmo in nobena dva igralca ne igrata več kot enkrat drug proti drugemu (natančnega števila iger posameznega igralca ne poznamo; dva različna igralca sta lahko vključena v različno število iger).
Pokažite, da obstajata dva igralca, ki sta odigrala enako število iger.
\end{zad}





\begin{zad}
Vzemite običajno kocko s $6$ ploskvami (s ploskvami oštevilčenimi od $1$ do $6$) in izberite štiri ploskve. Dokažite, da sta izmed teh štirih ploskev dve na nasprotnih straneh kocke.
\end{zad}






\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}










\newpage
\section{Urejen izbor s ponavljanjem. Urejeni izbori brez ponavljanja.}






\hvFloat[floatPos=!htb,capPos=before,onlyText=true,]{}
{{
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1cm,y=1cm]
%%\clip(-14.34,-9.62) rectangle (15.98,10.14);
\draw [line width=2pt] (0,0)-- (3,0);
\draw [line width=2pt] (0,0)-- (0,4);
\draw [line width=2pt] (0,4)-- (3,4);
\draw [line width=2pt] (3,4)-- (3,0);
\draw [line width=2pt] (3,1)-- (0,1);
\draw [line width=2pt] (0,2)-- (3,2);
\draw [line width=2pt] (0,3)-- (3,3);
\draw [line width=2pt] (1,4)-- (1,0);
\draw [line width=2pt] (2,4)-- (2,0);
\begin{scriptsize}
\draw [fill=red] (0,0) circle (2pt);
\draw[color=black] (-0.28,-0.07) node {\large$X$};
\draw [fill=red] (3,4) circle (2.5pt);
\draw[color=black] (3.2,4.35) node {\large$Y$};
\end{scriptsize}
\end{tikzpicture}
}}
{\begin{zad}
Študent bi se rad po ulicah sprehodil od točke $X$ do točke $Y$, kot je prikazano na sliki desno. Koliko različnih najkrajših poti lahko izbere?
\end{zad}}{fg}








\begin{zad}
Iz škatle, ki vsebuje kroglice oštevilčene od $1$ do $20$, izberemo $6$ kroglic. Na koliko načinov lahko to storimo, če
\begin{enumerate}[label=\rm(\alph*)]
\item kroglice izbiramo eno po eno in jih vračamo v škatlo?
%%
%%{\color{red}Rešitev: $121^6$.}
%%
\item kroglice izbiramo eno po eno in jih ne vračamo v škatlo?
%%
%%{\color{red}Rešitev: $121\cdot 120\cdot 119\cdot 118\cdot 117\cdot 116$.}
%%
\item kroglice izbiramo po dve naenkrat in jih ne vračamo v škatlo?
%%
%%{\color{red}Rešitev: ${121 \choose 2}\cdot {119 \choose 2}\cdot {117 \choose 2}$.}
%%
\item izberemo vseh $6$ kroglic naenkrat?
%%
%%{\color{red}Rešitev: ${121 \choose 6}$.}
%%
\end{enumerate}
Rezultat naj bo podan kot točna numerična vrednost. V vseh delih naloge, preden izračunate numerične vrednosti, podajte vsaj tri primere razvrstitev, ki jih lahko naredimo.
\end{zad}








\begin{zad}
Na koliko načinov se lahko konča plavalno tekmovanje s štirimi plavalci, če so mogoči tudi izenačeni rezultati?
\end{zad}
















\begin{zad}
Nek moški ima $12$ sorodnikov, $5$ je moških in $7$ žensk. Tudi njegova žena ima $12$ sorodnikov, od tega je $7$ moških in $5$ žensk. Skupnih sorodnikov nimata. Odločila sta se, da na obisk povabita $12$ sorodnikov. Na koliko načinov lahko to storita, če
\begin{enumerate}[label=\rm(\alph*)]
\item povabita vsak $6$ sorodnikov in bo med njimi natanko $6$ moških?
\item povabita oba enako število žensk?
\end{enumerate}
Odgovorov ni potrebno zapisovati z natančnimi numeričnimi vrednostmi.
\end{zad}








\section{Permutacije}



\begin{zad}
Na koliko načinov lahko $10$ ljudi razporedimo v pare? Preden izračunate numerično vrednost, podajte vsaj tri primere možnih razporeditev.
\end{zad}






\begin{zad}
Na koliko različnih načinov lahko zložimo na polico $4$ različne matematične in $3$ leposlovne knjige ter $5$ različnih leksikonov, če
\begin{enumerate}[label=\rm(\alph*)]
  \item so knjige lahko poljubno pomešane med seboj?
  \item naj matematične knjige stojijo skupaj?
  \item knjige iste vrste stojijo skupaj?
\end{enumerate}
\end{zad}





\begin{zad}
Na koliko načinov se lahko skupina $6$ žensk in $5$ moških postavi v vrsto za fotografiranje, če nobeni dve sosednji osebi nista istega spola?
\end{zad}







\begin{zad}
Najprej podajte $12$ paroma različnih permutacij naslednjih $10$ črk: $a,a,a,b,b,n,n,e,s,t$.

Nato pa dokažite, da je število paroma različnih permutacij $n$ objektov, v katerih se prvi objekt pojavi $k_1$-krat, drugi $k_2$-krat, tretji $k_3$-krat, vsi ostali objekti pa se pojavijo natanko enkrat, enako
$$
\frac{n!}{k_1!\cdot k_2!\cdot k_3!}.
$$
Podrobno razložite vsak korak svojega dokaza.
\end{zad}







\begin{zad}
 \begin{enumerate}[label=\rm(\alph*)]
\item Koliko različnih besed lahko dobimo s premetavanjem črk besede $banana$?
\item Koliko besed iz točke (a) je takih, da črka $b$ stoji neposredno pred črko $a$?
\item Koliko besed iz točke (a) je takih, da se v njih skupaj ne pojavi zaporedje črk $bnn$?
\item Koliko besed iz točke (a) je takih, da $b$ stoji pred vsemi $a$-ji (ne nujno neposredno pred njimi)?
 \end{enumerate}
\end{zad}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%







\section{Načelo dvojnega preštevanja}





\begin{zad}
Pokažite, da velja enakost
$$
\sum_{k=0}^n \binom{n}{k}=2^n
$$
tako da podate kombinatoričen dokaz (z uporabo načela dvojnega preštevanja) in obravnavate naslednje vprašanje: Na koliko različnih načinov lahko formiramo eno besedo dolžine $n$, če imamo na voljo poljubno mnogo črk $A$ in $B$?
\end{zad}








\begin{zad}
Pokažite, da velja enakost
$$
\sum_{k=0}^n k\cdot\binom{n}{k}=n\cdot 2^{n-1}\,,
$$
tako da podate kombinatoričen dokaz (z uporabo načela dvojnega preštevanja).
\end{zad}










\begin{zad}
\label{cetiri}
Pokažite, da velja enakost
$$
\sum_{j=0}^t \binom{a}{j}\binom{b}{t-j}=\binom{a+b}{t}
$$
tako da podate kombinatoričen dokaz (z uporabo načela dvojnega preštevanja) in obravnavate naslednje vprašanje: Na koliko različnih načinov lahko formiramo dve besedi dolžine $a$ in $b$, če imamo na voljo $t$ črk $A$, ki jih moramo nujno uporabiti, ter poljubno mnogo črk $B$?
\end{zad}




\begin{zad}
Podajte kombinatoričen dokaz (z uporabo načela dvojnega preštevanja) nasledenje enakosti
$$
{{n+m}\choose k}= \sum\limits_{\ell=0}^k {{n}\choose \ell} \cdot {{m}\choose {k-\ell}}
\qquad(0\leq k \leq m \leq n).
$$
\end{zad}







\begin{zad}
Pokažite, da velja enakost
$$
\sum_{k=0}^m k\cdot \binom{n}{k}\binom{m}{k}=n\cdot \binom{n+m-1}{n}
$$
tako da podate kombinatoričen dokaz (z uporabo načela dvojnega preštevanja).
\end{zad}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\begin{zad}
Pokažite, da velja enakost
$$
\sum_{k=0}^n 2^k\binom{n}{k}=3^n.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Podajte algebraičen dokaz.
\item Podajte kombinatoričen dokaz (z uporabo načela dvojnega preštevanja), tako da obravnavate naslednji vprašanji: 
Na koliko različnih načinov lahko iz $n$-elementne množice izberemo tak par množic $(X,Y)$, da velja $X\subseteq Y$? Koliko je različnih nizov dolžine $n$, ki jih lahko sestavimo iz števk $0$, $1$, $2$?
\end{enumerate}
\end{zad}









\begin{zad}
Pokažite, da velja enakost
$$
\binom{2n}{n}=\sum_{k=0}^n \binom{n}{k}^2
$$
tako da podate kombinatoričen dokaz.
\end{zad}







\begin{zad}
Pokažite, da velja enakost
$$
\binom{n+1}{r+1}=\sum_{k=r+1}^{n+1} \binom{k-1}{r}
$$
tako da podate kombinatoričen dokaz.
\end{zad}







\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Podajte kombinatoričen dokaz enakosti
\begin{equation}
\label{ghj}
\sum_{k=2}^n \binom{n}{k}\binom{k}{2} = \binom{n}{2}2^{n-2}
\end{equation}
za $n\ge 2$.
\item Identiteto \eqref{ghj} zapišite za $n=5$ in jo interpretirajte s pomočjo Pascalovega trikotnika.
\end{enumerate}
\end{zad}








\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Podajte (algebraičen ali kombinatoričen) dokaz enakosti
\begin{equation}
\label{ztj}
\sum_{j=0}^n \binom{k+j}{j} = \binom{n+k+1}{n}
\end{equation}
za poljubni dve števili $n,k\in \ZZplus$.
\item Identiteto \eqref{ztj} zapišite za $k=1$ in z uporabo identitete izračunajte vsoto $\sum_{j = 0}^nj$.
\item Z uporabo identitete \eqref{ztj} izračunajte $\sum_{j=0}^n j^2$.
\item Identiteto \eqref{ztj} zapišite za $n=4$ in $k=2$ ter jo interpretirajte s pomočjo Pascalovega trikotnika.
\end{enumerate}
\end{zad}








\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}







\newpage
\section{Lastnosti binomskih koeficientov}



\begin{zad}
Pokažite, da za $n > 0$ velja
$${n \choose 0} - {n \choose 1} + {n \choose 2} - \dotsb + (-1)^n {n \choose n} = 0.$$
\end{zad}



\begin{zad}
Poiščite enostavnejši izraz za $$\sum_{k=0}^{n}{n \choose k} {2z \choose 2}^k x^{n-k}.$$ Končni izraz mora biti $n$ta potenca kvadratnega polinoma v spremenljivkah $x$ in $z$ zapisana v poenostavljeni obliki (to je v obliki $ax^2+bz^2+cxz+dx+ez+f$ za nekatere konstante $a,b ,c,d,e,f$).
\end{zad}




\begin{zad}
Naj bo $X$ množica moči $n >0$.
\begin{enumerate}[label=\rm(\roman*)]

\item Naj bo $\S$ množica vseh podmnožic množice $X$, ki imajo sodo moč, in $\L$ množica vseh podmnožic množice $X$, ki imajo liho moč. Naj bo $x$ poljuben element množice $X$ in naj bo $f$ preslikava, ki slika iz množice $\S$ v množico $\L$, podana s predpisom: za vse $A \in \S$ naj bo $f(A) = A\setminus \{x\}$, če je $x$ element množice $A$, in $f(A) = A\cup \{x\}$, sicer.

Dokažite, da je preslikava $f$ bijektivna.
\item Z uporabo rezultata v točki (i) podajte kombinatoričen dokaz enakosti $\ds\sum_{k = 0}^n (-1)^k {n\choose k} = 0$.
\end{enumerate}
\end{zad}




  

\begin{zad}
Tat skuša odpreti vrata s kodo: ima $12$ gumbov z oznakami $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $ \#$, $*$ in pričakuje šest števk, ki jim sledi \# ali *. Koliko kod je možnih:
\begin{enumerate}[label=\rm(\roman*)]
     \item brez dodatnih omejitev?
     \item če se nobena števka ne ponovi?
\end{enumerate}
Z opazovanjem gumbov lahko poskušamo uganiti pogostost uporabe posameznega gumba. Dejansko tat opazi, da gumbi $4,6,7,8,*$ niso nikoli uporabljeni (ni jih v kodi), gumb $1$ se pojavi vsaj dvakrat, za ostale številke pa ni nobenega jamstva.
\begin{enumerate}[resume, label=\rm(\roman*)]
\item Koliko kod je možnih s tem novim namigom?
\item Koliko kod je možnih, če tat ugotovi tudi, da se $1$ pojavi strogo večkrat kot $9$, ki se pojavi strogo večkrat kot $2$?
\end{enumerate}
\end{zad}








\section{Načelo vključitev in izključitev}




\begin{zad}
Dvojiški niz dolžine osem se imenuje zlog. Poiščite število zlogov z drugim bitom $0$ ali tretjim bitom $1$. Izračunajte natančno numerično vrednost vaše rešitve!
\end{zad}



\begin{zad}
Koliko naravnih števil $\leq 70$ je tujih številu $50$ (tj., nimajo netrivialnih skupnih deliteljev s številom $50$)?
\end{zad}






\begin{zad}
Koliko desetmestnih binarnih nizov, ki se začnejo z $111$ ali končajo z $101$ (ali oboje) lahko sestavimo, če
\begin{enumerate}[label=\rm(\alph*)]
\item ni dodatnih omejitev?
\item vsebuje niz natanko $6$ enic?
\end{enumerate}
\end{zad}






\begin{zad}
Izmed $100$ študentov se jih $46$ ukvarja z odbojko, $47$ z rokometom in $48$ z nogometom, po $12$ študentov se ukvarja s poljubnim parom od teh športov (ne pa tudi s preostalim, tretjim športom), $14$ \v studentov pa se ukvarja z vsemi tremi športi. Koliko \v studentov ne igra nobenega od teh treh športov?
\end{zad}





\begin{zad}
Med študenti v nekem študentskem domu se jih v prostem času $12$ rekreativno ukvarja z nogometom $(N)$, $20$ s košarko $(K)$, $20$ z odbojko $(O)$ in $8$ z rokometom $(R)$. $5$ študentov se ukvarja z $N$ in $K$, $7$ študentov z $N$ in $O$, $4$ študenti z $N$ in $R$, $16$ študentov s $K$ in $O$, $4$ študenti s $K$ in $R$, $3$ študenti pa z $O$ in $R$. $3$ študenti se ukvarjajo z $N$, $K$ in $O$, $2$ študenta z $N$, $K$ in $R$, $2$ študenta s $K$, $O$ in $R$, $3$ študenti pa z $N$, $O$ in $R$. $2$ študenta se ukvarjata z vsemi štirimi športi. Znano je tudi, da se $71$ študentov ne ukvarja z nobenim od omenjenih štirih športov. Poiščite skupno število študentov v študentskem domu.
\end{zad}





\begin{zad}
Na koliko načinov lahko razdelimo $20$ enakih bonbonov med tri otroke, če dovolimo, da kakšen izmed otrok ne prejme nobenega bonbona, in:
\begin{enumerate}[label=\rm(\alph*)]
\item ni omejitev glede števila bonbonov na otroka?
\item vsaj en otrok dobi vsaj $7$ bonbonov?
\item vsaj en otrok dobi vsaj $10$ bonbonov?
\end{enumerate}
\end{zad}









\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}










\newpage
\section{Neurejen izbor s ponavljanjem}





\begin{zad}
Na koliko načinov je mogoče izbrati $6$ kosov sadja iz sklede, ki vsebuje jabolke, pomaranče in hruške, če vrstni red, v katerem so izbrani kosi, ni pomemben, pomembna je le vrsta sadja in ne posamezen kos? Predpostavite, da je v skledi vsaj šest kosov vsake vrste sadja.
\end{zad}







\begin{zad}
Na koliko načinov je mogoče izbrati pet bankovcev iz blagajne, ki vsebuje bankovce za $5$\texteuro, $10$\texteuro, $20$\texteuro, $50$\texteuro, $100$\texteuro, $200$\texteuro~in $500$\texteuro ? Predpostavimo, da vrstni red, v katerem so izbrani bankovci, ni pomemben, da se bankovci iste vredosti med seboj ne razlikujejo in da obstaja vsaj pet bankovcev vsake vrste. Rezultat naj bo podan kot točna numerična vrednost.
\end{zad}







\begin{zad}
Skupina $40$ ljudi je bila usposobljena za astronavte za prvo misijo na Mars. Razdeljeni so v $5$ skupin (rdeča, rumena, modra, zelena, rjava). Vsaka skupina ima $8$ različnih članov, z vrednostmi usposabljanja od $1$ do $8$. Vrednost usposabljanja predstavlja tip usposabljanja -- vsak od članov (iz vsake skupine) je usposobljen za natanko eno od $8$ različnih nalog (in nobena dva člana iste skupine nista usposobljena za isto nalogo).
\begin{enumerate}[label=\rm(\alph*)]
\item Na koliko različnih načinov lahko izmed $40$ ljudi izberemo $6$ različnih ljudi, tako da se pojavijo tri vrednosti usposabljanja, vsaka po dvakrat? Rezultat naj bo podan kot točna numerična vrednost.
\item Na koliko načinov lahko izberemo $5$ različnih ljudi, da bomo imeli $5$ zaporednih vrednosti usposabljanja? Rezultat naj bo podan kot točna numerična vrednost.
\end{enumerate}
\end{zad}










\section{Neurejeni izbori brez ponavljanja}






\begin{zad}
Koliko celoštevilskih rešitev ima enačba $x_1+x_2+x_3+x_4=12$, če je
\begin{enumerate}[label=\rm(\alph*)]
\item $x_1\ge 0$, $x_2\ge 0$, $x_3\ge 0$, $x_4\ge 0$?
\item $x_1\ge 1$, $x_2\ge 2$, $x_3\ge 1$, $x_4\ge 2$?
\end{enumerate}
Rezultat naj bo podan kot točna numerična vrednost. V obeh delih naloge podajte vsaj tri rešitve dane enačbe, preden izračunate numerično vrednost.
\end{zad}





\begin{zad}
Koliko celoštevilskih rešitev ima enačba $x_1+x_2+x_3+x_4+x_5=22$, če je
\begin{enumerate}[label=\rm(\alph*)]
\item $x_1\ge 0$, $x_2\ge 20$, $x_3\ge 0$, $x_4\ge 0$, $x_5\ge 0$?
\item $x_1\ge 2$, $x_2\ge 3$, $x_3\ge 4$, $x_4\ge 3$, $x_5\ge 2$?
\end{enumerate}
Rezultat naj bo podan kot točna numerična vrednost. V obeh delih naloge podajte vsaj tri rešitve dane enačbe, preden izračunate numerično vrednost.
\end{zad}







\begin{zad}
Na koliko načinov lahko $33$ identičnih kap razdelimo v škatle $A$, $B$, $C$ in $D$, če velja, da škatla $A$ vsebuje vsaj dve kapi, škatla $B$ vsebuje vsaj pet kap in škatla $C$ vsebuje {\em natanko} šest kap? (Opazite, da za škatlo $D$ nimamo nobenih omejitev.)
Odgovor zapišite tudi kot natančno numerično vrednost.
\end{zad}




\begin{zad}
V trgovini so naprodaj tri vrste baterij: $AAA$, $AA$ in $9V$. Na zalogi sta samo še dve $9V$ bateriji in več kot $10$ baterij vsake od preostalih dveh vrst. Petra želi kupiti $10$ baterij in med njimi potrebuje vsaj dve bateriji vrste $AAA$. Na koliko načinov lahko to stori? Izračunajte natančno numerično vrednost vaše rešitve!
\end{zad}






\begin{zad}
Sara in Matevž na plaži nabirata kamne in školjke, skupno pa sta jih nabrala $12$. Obstajajo $4$ vrste: ostri kamni, okrogli kamni, rebraste školjke in spiralne školjke. Če ne ločimo kamnov/školjk iste vrste, koliko zbirk moči $12$ je mogoče narediti:
\begin{enumerate}[label=\rm(\roman*)]
\item brez dodatnih pogojev?
\item če želita vsaj $4$ rebraste in $2$ spiralni školjki?
\item če želita vsaj en kamen oz.~školjko vsake vrste in največ $3$ okrogle kamne?
\end{enumerate}
Na koncu sta nabrala $1$ okrogel kamen, $2$ ostra kamna, $4$ školjke in $5$ spiralnih školjk (vse pisane in zelo različne) in si želita razdeliti plen. Sara želi obdržati $2$ kamna (okrogla ali ostra) in 4 školjke (rebraste ali spiralne), ostalo pa vzame Matevž.
\begin{enumerate}[resume, label=\rm(\roman*)]
\item Koliko različnih razdelitev lahko naredita?
\end{enumerate}
\end{zad}






\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}










\newpage
\section{Linearne rekurzivne enačbe s konstantnimi koeficienti}



\begin{zad}
Rešite rekurzivno enačbo $F(n)=4F(n-2)$ z začetnima pogojema $F(0)=0$ in $F(1)=4$.
\end{zad}





\begin{zad}
Rešite rekurzivno enačbo $F(n)=4F(n-1)-3F(n-2)$ z začetnima pogojema $F(0)=2$ in $F(1)=5$.
\end{zad}






\begin{zad}
Rešite rekurzivno enačbo
$$
F(n)=F(n-1)+F(n-2)-F(n-3)
$$
z začetnima pogojema $F(0)=F(1)=0$ in $F(2) = 4$. Uporabite metodo s karakteristično enačbo.
\end{zad}







\begin{zad}
\textbf{Lucasovo zaporedje} je mogoče definirati kot $L(0) = 2$, $L(1) = 1$ in $L(n) = L(n-1) + L(n-2)$ za $n \geq 2$.
\begin{enumerate}[label=\rm(\alph*)]
\item Izračunajte prvih šest členov zaporedja.
\item Pridobite eksplicitno (nerekurzivno) formulo za $L(n)$.
\end{enumerate}
\end{zad}











\section{Rekurzivne enačbe}







\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Alja položi $1000$ evrov v lokalno banko po letni obrestni meri $8\%$ na leto. Rekurzivno definirajte znesek $a_n$, ki ga bo imela na svojem računu ob koncu $n$ let.
\item V sejni dvorani je $n$ gostov. Vsaka oseba se rokuje z vsemi ostalimi natanko enkrat. Rekurzivno definirajte število rokovanj $h(n)$, ki se zgodijo, in rešite dobljeno rekurzivno enačbo.
\end{enumerate}
\end{zad}






\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Voznik avtobusa plača cestnino, pri čemer uporablja samo kovance po $1\euro{}$ in $2\euro{}$, tako da vrže po en kovanec naenkrat v mehanski zbiralnik cestnine. Poiščite rekurzivno zvezo za število različnih načinov, na katere lahko voznik plača cestnino v višini $n\euro{}$ (pri čemer je pomemben vrstni red, v katerem so uporabljeni kovanci).
\item Rešite rekurzivno enačbo $F(n) =8F(n-1)-16F(n-2)$ z začetnima pogojema $F(0) = -1$ in $F(1) = 4$.
Uporabite metodo s karakteristično enačbo.
\end{enumerate}
\end{zad}






\begin{zad}
Na razpolago imamo kvadratne ploščice, ki imajo obliko črke $L$ in pokrijejo $3$ kvadrate. Pokriti želimo pravokotna tla velikosti $2\times n$ kvadratkov za $n\ge 0$. Poiščite rekurzivno zvezo za število načinov, na katere lahko pokrijemo pravokotna tla velikosti $2\times n$, za $n\ge 2$. Določite tudi število (numerično vrednost) načinov, na katere lahko pokrijemo pravokotna tla velikosti $2\times 12$ kvadratkov.
\end{zad}










\begin{zad}
Naj bo $a_n$ število vseh nizov dolžine $n$, ki vsebujejo le črke $A$, $B$ in $C$, ne vsebujejo pa podniza ``$\textit{CA}$''. Poiščite rekurzivno zvezo za $a_n$. Določite tudi numerično vrednost števila~$a_5$.
\end{zad}







\begin{zad}
Naj bo $a_n$ število vseh takih dvojiških zaporedij dolžine $n$ (zaporedja dolžine $n$, ki vsebujejo le cifre $0$ in $1$), ki ne vsebujejo podzaporedja $001$. 

Poiščite rekurzivno zvezo za $a_n$ in začetne vrednosti. 

Določite tudi numerično vrednost števila $a_6$.
\end{zad}










\begin{zad}
Na koliko načinov lahko pokrijemo pravokotna tla velikosti $2\times n$ kvadratkov, $n>0$, če imamo na razpolago pravokotne ploščice velikosti $1\times 2$ in $2\times 2$ kvadratka? Poiščite rekurzivno zvezo in dobljeno enačbo rešite. Na koliko načinov lahko pokrijemo tla velikosti $2\times 5$ kvadratkov?
\end{zad}








\begin{zad}
Na robu nekega ribnika se pasejo žabe in štorklje. V vsaki minuti se zgodi naslednje: v prvi polovici minute vsaka od žab, ki so se pasle v začetku te minute, privabi tri nove žabe in eno novo štorkljo. V drugi polovici minute pa vsaka od štorkelj poje po eno žabo. V začetku sta se pasli dve žabi in ena štorklja. Zapišite rekurzivno zvezo, ki bo podala število žab in štorkelj na začetku $n$-te minute za vse $n\in \ZZ^+_0$.
%%
%%\textit{(OPOMBA: Potrebujemo dve rekurzivni enačbi, ki pa sta soodvisni.)}
\end{zad}







\begin{zad}
Na razpolago imamo kvadratne ploščice velikosti $1\times 1$ kvadratek in pravokotne ploščice velikosti $1\times 2$ kvadratka. Pokriti želimo pravokotna tla velikosti $2\times n$ kvadratkov za $n\ge 0$, pri čemer morata daljša robova dveh vzporedno postavljenih pravokotnih ploščic sovpadati v celoti, tj.~ne dovolimo postavitev
\begin{center}
\includegraphics{dn1}
\end{center}
Naj $F(n)$ označuje število različnih postavitev ploščic, ki jih imamo pri pokrivanju tal velikosti $2\times n$.
\begin{enumerate}[label=\rm(\alph*)]
\item Utemeljite, da v tem primeru enačba $F(n) = 2F(n - 1) + 3F(n - 2)$ podaja rekurzivno zvezo za število različnih postavitev ploščic za $n\ge 2$.
\item Zapišite začetna pogoja in svoj rezultat preverite tako, da naštejete vse možne postavitve ploščic za tla velikosti $2\times 2$ kvadratkov in dobljeno primerjate z rezultatom izračunanim s pomočjo rekurzivne enačbe.
\item Podajte eksplicitno enačbo za $F(n)$.
\end{enumerate}
\end{zad}









\begin{zad}
Na razpolago imamo kvadratne ploščice velikosti $1\times 1$ kvadratek in ploščice ki imajo obliko črke $L$ (in pokrijejo $3$ kvadrate). Pokriti želimo pravokotna tla velikosti $2\times n$ kvadratkov za $n\ge 0$, pri čemer  ne dovolimo postavitve oblike
\begin{center}
\includegraphics{ploscice4}
\end{center}
%%Naj $F(n)$ označuje število različnih postavitev ploščic, ki jih imamo pri pokrivanju tal velikosti $2\times n$.
\begin{enumerate}[label=\rm(\alph*)]
\item Poiščite rekurzivno zvezo za število načinov na katere lahko pokrijemo pravokotna tla velikosti $2\times n$,
%%enačbo, ki podaja rekurzivno zvezo za število različnih postavitev ploščic
za $n\ge 2$.
\item Zapišite začetna pogoja in svoj rezultat preverite tako, da naštejete vse možne postavitve ploščic za tla velikosti $2\times 2$ kvadratkov in dobljeno primerjate z rezultatom izračunanim s pomočjo rekurzivne enačbe.
\end{enumerate}
\end{zad}









\begin{zad}
Na razpolago imamo kvadratne ploščice velikosti $1\times 1$ kvadratek in ploščice ki imajo obliko črke $I$ (in pokrijejo 3 kvadrate). Pokriti želimo pravokotna tla velikosti $2\times n$ kvadratkov za $n\ge 0$, pri čemer  ne dovolimo postavitve naslednjih oblik:
\begin{center}
\includegraphics[scale=.8]{plosckeOlikeCrkeI}
\end{center}
Naj $F(n)$ označuje število različnih postavitev ploščic, ki jih imamo pri pokrivanju tal velikosti $2\times n$.
\begin{enumerate}[label=\rm(\alph*)]
\item Poiščite rekurzivno zvezo za $F(n)$ za $n\ge 3$.
\item Izračunajte $F(6)$.
\end{enumerate}
\end{zad}






\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}








\newpage
\section{Porazdelitve}




\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item
Zapišite vse možnosti, kako je tri različne predmete (jabolko, pomarančo in banano) mogoče postaviti v dve {\em različni} škatli, tako da nobena škatla ne ostane prazna.
\item Naj bo $n$ naravno število. Podajte kombinatoričen dokaz naslednje enakosti
$$
S(n,2)=2^{n-1}-1.
$$
\end{enumerate}
\end{zad}







\begin{zad}
Na koliko načinov lahko razvrstimo $8$ različnih prstanov v $3$ škatle,
\begin{enumerate}[label=\rm(\alph*)]
\item če imamo identične škatle in če mora biti v vsaki škatli vsaj en prstan?
\item če imamo različne škatle in če mora biti v vsaki škatli vsaj en prstan?
\end{enumerate}
Rezultat naj bo podan kot točna numerična vrednost. Preden izračunate numerične vrednosti, podajte vsaj tri primere izbir, ki jih lahko naredimo.
\end{zad}






\begin{zad}
Na koliko načinov lahko $10$ nerazločljivih kroglic postavite v osem posod, ki jih med seboj razlikujete?
\end{zad}







\begin{zad}
Na koliko načinov lahko v tri nerazločljive pisarne postavite štiri različne zaposlene, če lahko vsaka pisarna vsebuje poljubno število zaposlenih?
\end{zad}






\begin{zad}
Štirje ribiči so šli na jezero lovit ribe. Na koncu dneva skupaj ulovijo $11$ enakih rib. Zdaj morajo teh $11$ rib razdeliti v $4$ enake vrečke. Na koliko načinov lahko to naredijo, če
\begin{enumerate}[label=\rm(\alph*)]
\item vsaka vrečka vsebuje vsaj eno ribo?
\item je lahko kakšna od vrečk tudi prazna?
\end{enumerate}
Rezultati naj bodo podani kot točne numerične vrednosti.
\end{zad}





\begin{zad}
Štirje ribiči so šli na jezero lovit ribe. Na koncu dneva skupaj ulovijo $13$ enakih rib. Zdaj morajo med seboj razdeliti ribe. Na koliko načinov lahko to storijo, če:
\begin{enumerate}[label=\rm(\alph*)]
\item mora vsak ribič dobiti vsaj eno ribo?
\item nekateri ribiči lahko ne dobijo nobene ribe?
\end{enumerate}
Rezultata naj bosta podana kot točni numerični vrednosti.
\end{zad}







\begin{zad}
Med $5$ delavcev moramo razdeliti $6$ različnih hišnih opravil, tako da vsak delavec dobi vsaj eno delo. Na koliko načinov lahko to storimo?
\end{zad}







\begin{zad}
V standardnem kupu kart je $52$ različnih kart. V vsaki od štirih barv (pik, križ, srce, karo) je $13$ kart z vrednostmi od asa (ki je najnižja) do kralja (ki je najvišja). Na koliko načinov lahko razdelimo vse karte med $4$ igralce tako, da dobi vsak igralec vsaj eno karto?
\end{zad}








\begin{zad}
Na koliko načinov je mogoče zapakirati osem DVD-jev v tri škatle, tako da vsaka škatla vsebuje vsaj en DVD, če imamo
\begin{enumerate}[label=\rm(\alph*)]
\item osem različnih DVD-jev in tri nerazločljive škatle,
\item osem različnih DVD-jev in tri različne škatle?
\end{enumerate}
Rezultata naj bosta podana kot točni numerični vrednosti.
\end{zad}





\begin{zad}
Na koliko načinov je mogoče zapakirati osem DVD-jev v tri škatle, tako da vsaka škatla vsebuje vsaj en DVD, če imamo
\begin{enumerate}[label=\rm(\alph*)]
\item osem različnih DVD-jev in tri različne škatle,
\item osem nerazločljivih DVD-jev in tri nerazločljive škatle,
\item osem nerazločljivih DVD-jev in tri različne škatle?
\end{enumerate}
Rezultati naj bodo podani kot točne numerične vrednosti.
\end{zad}





\begin{zad}
Na koliko načinov je mogoče razdeliti sedem različnih kroglic v štiri nerazločljive škatle, če lahko vsaka škatla vsebuje poljubno število kroglic?

Rezultata ni potrebno podati v obliki točne numerične vrednosti.
\end{zad}








\begin{zad}
Na koliko načinov lahko v tri nerazločljive pisarne postavite štiri različne zaposlene, če lahko vsaka pisarna vsebuje poljubno število zaposlenih?
\end{zad}




\begin{zad}
V $4$ različne likovne razrede vpišemo $12$ otrok. Med otroki sta dva para bratov in sester, bratov in sester pa ne želimo dajati v različne skupine. Preštejte različne načine, kako lahko to storimo, glede na to, da ne želimo imeti praznih razredov.
\end{zad}






\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item $12$ otrok želimo razdeliti v štiri igralne skupine. Vendar sta med otroki {\bf natanko dva para} bratov in sester, bratov in sester pa ne želimo dajati v različne skupine. Koliko možnosti imamo?
\item Na koliko načinov lahko razdelite $30$ mangov v tri enake košare? Nekatere košare so lahko prazne.
\end{enumerate}

\medskip
Napišite točne numerične vrednosti vaših rešitev.
\end{zad}








\begin{zad}
Na koliko načinov lahko razvrstimo $9$ prstanov na $4$ prste desne roke (brez palca), če:
\begin{enumerate}[label=\rm(\alph*)]
\item prstanov med seboj ne razlikujemo in so prsti lahko tudi prazni?
\item prstanov med seboj ne razlikujemo, na vsakem prstu pa mora biti vsaj en prstan?
\item so prstani različni, vrstni red prstanov na prstu ni pomemben, prsti so lahko tudi prazni?
\item so prstani različni, vrstni red prstanov na prstu ni pomemben, na vsakem prstu pa mora biti vsaj en prstan?
\item so prstani različni, vrstni red prstanov na prstu je pomemben, prsti so lahko tudi prazni?
\item so prstani različni, vrstni red prstanov na prstu je pomemben in na vsakem prstu mora biti vsaj en prstan?
\end{enumerate}
Rezultat naj bo podan kot točna numerična vrednost. Preden izračunate numerične vrednosti, podajte vsaj tri primere izbir, ki jih lahko naredimo.
\end{zad}






\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}








\newpage
\section{Graf}





\begin{zad}
Določite število povezav v grafu s $6$ točkami, $2$ stopnje $4$ in $4$ stopnje $2$. Narišite dva taka povezana grafa.
\end{zad}









\begin{zad}
Dan je naslednji graf $G$:

\begin{center}
\definecolor{uuuuuu}{rgb}{0,0,0}
\begin{tikzpicture}[scale=.7,line cap=round,line join=round,>=triangle 45,x=1cm,y=1cm]
\draw [line width=1pt] (-3.2360679774997894,1.8042260651806146)-- (0,4.155367074350506);
\draw [line width=1pt] (0,4.155367074350506)-- (3.23606797749979,1.804226065180613);
\draw [line width=1pt] (3.23606797749979,1.804226065180613)-- (2,-2);
\draw [line width=1pt] (2,-2)-- (-2,-2);
\draw [line width=1pt] (-2,-2)-- (-3.2360679774997894,1.8042260651806146);
\draw [line width=1pt] (0,4.155367074350506)-- (2,-2);
\draw [line width=1pt] (-2,-2)-- (0,4.155367074350506);
\draw [line width=1pt] (-3.2360679774997894,1.8042260651806146)-- (3.23606797749979,1.804226065180613);
\draw [line width=1pt] (-2,-2)-- (3.23606797749979,1.804226065180613);
\draw [line width=1pt] (-3.2360679774997894,1.8042260651806146)-- (2,-2);
\draw [line width=1pt] (0,0.7527638409423467)-- (-0.6180339887498946,-0.09788696740969288);
\draw [line width=1pt] (0,0.7527638409423467)-- (0.6180339887498952,-0.09788696740969335);
\draw [line width=1pt] (0,0.7527638409423467)-- (1,1.0776835371752527);
\draw [line width=1pt] (0,0.7527638409423467)-- (0,1.8042260651806137);
\draw [line width=1pt] (-1,1.0776835371752533)-- (0,0.7527638409423467);
\begin{scriptsize}
\draw [fill=uuuuuu] (-2,-2) circle (2.5pt);
\draw[color=uuuuuu] (-2.32,-2.03) node {$A$};
\draw [fill=uuuuuu] (2,-2) circle (2.5pt);
\draw[color=uuuuuu] (2.3,-2.01) node {$B$};
\draw [fill=uuuuuu] (3.23606797749979,1.804226065180613) circle (2.5pt);
\draw[color=uuuuuu] (3.5,1.97) node {$C$};
\draw [fill=uuuuuu] (0,4.155367074350506) circle (2.5pt);
\draw[color=uuuuuu] (0.16,4.59) node {$D$};
\draw [fill=uuuuuu] (-3.2360679774997894,1.8042260651806146) circle (2.5pt);
\draw[color=uuuuuu] (-3.5,2.09) node {$E$};
\draw [fill=uuuuuu] (0,0.7527638409423467) circle (2pt);
\draw[color=uuuuuu] (0.16,1.15) node {$F$};
\draw [fill=uuuuuu] (1,1.0776835371752527) circle (2pt);
\draw[color=uuuuuu] (1.28,1.35) node {$L$};
\draw [fill=uuuuuu] (0,1.8042260651806137) circle (2pt);
\draw[color=uuuuuu] (0.16,2.19) node {$M$};
\draw [fill=uuuuuu] (-1,1.0776835371752533) circle (2pt);
\draw[color=uuuuuu] (-1.38,1.51) node {$N$};
\draw [fill=uuuuuu] (-0.6180339887498946,-0.09788696740969288) circle (2pt);
\draw[color=uuuuuu] (-0.88,-0.25) node {$O$};
\draw [fill=uuuuuu] (0.6180339887498952,-0.09788696740969335) circle (2pt);
\draw[color=uuuuuu] (0.8,-0.23) node {$P$};
\draw (-2,4.09) node {\Large $G$};
\end{scriptsize}
\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Podajte primer podgrafa na $6$ točkah, ki ni induciran podgraf.
\item Podajte primer induciranega podgrafa na $6$ točkah.
\item Podajte primer sledi dolžine $7$, ki ni pot.
\item Podajte primer grafa $H$ z množico točk $\{a,b,c,d,e,f,p,l,m,n,o\}$, ki je izomorfen danemu grafu $G$ in je narisan na drugačen način.
\item Ali je $G$ ravninski? (Odgovor natančno utemeljite.)
\item Ali je $\chi(G)=2$? (Odgovor natančno utemeljite.)
\end{enumerate}
\end{zad}








\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Naj bodo $e_1,e_2,\ldots,e_n$ povezave grafa $G$ in naj bosta $x_{i-1}$ in $x_{i}$ krajišči povezave $e_i$ $(1\le i\le n)$. Pokažite, da je vsak sklenjen sprehod $(e_1,e_2,\ldots,e_n)$ dolžine vsaj $3$ s paroma različnimi točkami $x_1,x_2,\ldots,x_n$ cikel.
\item Graf, ki ne vsebuje ciklov, se imenuje {\bf acikličen}. Sprehod je acikličen, če je podgraf, sestavljen iz točk in povezav sprehoda acikličen.
Dokažite: sprehod ima vse točke različne, če in samo če je aciklična sled.
\item Če sta $u$ in $v$ različni točki grafa $G$ in če obstaja sprehod v $G$ od $u$ do $v$, pokažite, da potem obstaja aciklična sled od $u$ do $v$. {\it (Natanko razložite, da je vsak najkrajši sprehod od $u$ do $v$ dejansko aciklična sled.)}
\end{enumerate}
\end{zad}






\begin{zad}
Pokažite, da je vsota stopenj točk grafa enaka dvakratnemu številu povezav, to je
$$
\sum_{v\in V(G)} d(v) = 2\cdot |E(G)|.
$$
\end{zad}






\begin{zad}
Naj bo $G$ enostaven graf z $n$ točkami. Pokažite, da mora biti $G$ povezan, če ima več kot $\frac{(n-1)(n-2)}{2}$ povezav.
\end{zad}









\section{Drevo}





\begin{zad}
Dano je drevo, ki ima točno pet točk stopnje $2$, tri točke stopnje $3$, štiri točke stopnje $4$ in nobene točke stopnje večje od $4$. Koliko točk stopnje $1$ ima to drevo?
\end{zad}






\begin{zad}
Naj bo $G$ enostaven graf z $n$ točkami in $n-1$ povezavami. Ali je res, da je $G$ gozd, če in samo če je $G$ povezan? Trditev dokažite ali pa navedite protiprimer.
\end{zad}






\begin{zad}
Pokažite, da za poljubno drevo $T$ obstaja ena in samo ena pot med vsakim parom točk.
\end{zad}



\begin{zad}
Pokažite, če za graf $G$ obstaja ena in samo ena pot med vsakim parom točk, potem je $G$ drevo.
\end{zad}






\begin{zad}
Dokažite, da je vsako drevo ravninski graf.
\end{zad}



\begin{zad}
Naj bo $T$ drevo. Pokažite, da če $T$ vsebuje točko stopnje $k\geq 2$, potem vsebuje tudi vsaj $k$ točk stopnje $1$.
\end{zad}






\begin{zad}
Pokažite: Če je povezava $e$ povezava največje teže na ciklu $C$ v grafu $G$ z uteženimi povezavami, potem v grafu $G$ obstaja najlažje vpeto drevo, ki ne vsebuje povezave $e$.
\end{zad}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}







\newpage
\section{Homomorfizmi grafa}




\begin{zad}
Naj bosta $G = (V,E)$ in $G' = (V',E')$ (enostavna) grafa.
Pravimo, da je graf $G$ {\bf homomorfen} grafu $G'$, če obstaja taka preslikava $\phi : V\ra V'$, da za vsako povezavo $\{x,y\}\in E$ grafa $G$ velja $\{\phi(x),\phi(y)\}\in E'$.
Taki preslikavi $\phi$ pravimo {\bf homomorfizem} grafa $G$ na graf $G'$ in jo označimo s $\phi : G\ra G'$.


\medskip
Pokažite, da za poljubne tri grafe $G_1$, $G_2$, $G_3$ velja, da če obstajata homomorfizem $f : G_1\ra G_2$ in homomorfizem $g : G_2\ra G_3$, potem obstaja tudi homomorfizem $h : G_1\ra G_3$.
S pomočjo dokaza nato poiščite ustrezne homomorfizme za naslednje grafe:
\begin{center}
\includegraphics[scale=.8]{homomorfizem-triGr}
\end{center}
\end{zad}













\section{Induciranega podgraf. Izomorfizmi grafa. Sklenjen sprehod.}





\begin{zad}
Dan imamo graf $G$:
\begin{center}
\begin{tikzpicture}[scale=.35]
\node at (5.84,-2.232050807568878) {$f$};
\node at (5.84,2.232050807568878) {$e$};
\node at (-0.62,-0.6) {$c$};
\node at (1.84,-0.6) {$d$};
\node at (-4.62,2.2320508075688774) {$a$};
\node at (-4.62,-2.2320508075688774) {$b$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0); %%df
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-4.12,1.7320508075688774); %%ba
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774); %%ac
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0); %%bc
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878); %%de
\draw [line width=1pt] (-4.12,1.7320508075688776)-- (5.34,1.732050807568878); %%ae
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (5.34,-1.732050807568878); %%bf
\draw [line width=1pt] (5.34,1.732050807568878)-- (5.34,-1.732050807568878); %%ef
%% \draw [line width=1pt] (2.34,0) %%vozlisce d
%%\draw [line width=1pt] (-1.12,0)-- (2.34,0); %%cd
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
\vspace{-7mm}
\begin{enumerate}[label=\rm(\alph*)]
\item Za graf $G$ na sliki podajte primer induciranega podgrafa, ki ni dvodelen in ki ima $5$ točk.
\item Poiščite štiri izomorfizme grafa $G$ na graf $G$ (tj.~grafa $G$ nase). (Izomorfizem grafa $G$ nase se imenuje {\it avtomorfizem} grafa $G$).
\item Za graf $G$ na sliki podajte primer sklenjenega sprehoda, ki vsebuje vse povezave grafa, oziroma razložite, zakaj takšen sprehod ne obstaja.
\end{enumerate}
\end{zad}












\section{Izomorfizmi grafa}






\begin{zad}
Določite, kateri pari grafov so izomorfni.

\medskip
\centering\includegraphics[width=0.5\textwidth]{ex2-class1.png}
\end{zad}








\begin{zad}
Za graf $G$ na sliki
\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,draw,circle}]	
	\begin{scope}
	\node[vertex, label=above:$ u $] (2) at (-1.5,2) {};
	\node[vertex, label=above:$ v $] (3) at (-0.5,2) {};
	\node[vertex, label=above:$ w $] (4) at (0.5,2) {};
	\node[vertex, label=above:$ x $] (5) at (1.5,2) {};
	\node[vertex, label=right:$ y $] (1) at (0,0) {};
	\path (1) edge (2);
	\path (1) edge (3);
	\path (1) edge (4);
	\path (1) edge (5);
	\path (2) edge (3);
	\path (3) edge (4);
	\path (4) edge (5);
	\pgftext[base, x=0cm,y=-0.75cm]{$G$};
	\end{scope}
	\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item podajte primere treh paroma neizomorfnih vpetih dreves;
\item podajte primere treh paroma neizomorfnih vpetih podgrafov, ki niso dvodelni.
\end{enumerate}
Odgovor natančno utemeljite.
\end{zad}






\begin{zad}
Dana imamo naslednja grafa

\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,draw,circle}]
	
	\begin{scope}
	\node[vertex, label=below:$ a $] (1) at (0,0) {};
	\node[vertex, label=left:$ b $] (2) at (-1.5,0.5) {};
	\node[vertex, label=right:$ c $] (3) at (1.5,0.5) {};
	\node[vertex, label=left:$ d $] (4) at (-1,1) {};
	\node[vertex, label=right:$ e $] (5) at (1,1) {};
	\node[vertex, label=left:$ f $] (6) at (-2,1.5) {};
	\node[vertex, label=right:$ g $] (7) at (2,1.5) {};
	\node[vertex, label=above:$ h $] (8) at (-0.5,2) {};
	\node[vertex, label=above:$ i $] (9) at (0.5,2) {};
	\node[vertex, label=left:$ j $] (10) at (-1.5,2.5) {};
	\node[vertex, label=right:$ k $] (11) at (1.5,2.5) {};
	\node[vertex, label=above:$ \ell $] (12) at (0,3) {};
	\path (1) edge (2);	
	\path (1) edge (3);	
	\path (1) edge (8);	
	\path (1) edge (9);		
	\path (2) edge (4);	
	\path (2) edge (6);	
	\path (3) edge (5);	
	\path (3) edge (7);
	\path (4) edge (5);
	\path (4) edge (10);
	\path (5) edge (11);
	\path (6) edge (8);
	\path (6) edge (10);
	\path (7) edge (9);
	\path (7) edge (11);
	\path (8) edge (12);
	\path (9) edge (12);
	\path (10) edge (12);
	\path (11) edge (12);
	\pgftext[base, x=0cm,y=-1cm]{$G$};
	\end{scope}
	
	
	\begin{scope}[xshift=5cm, yshift=1cm]
	\node[vertex, label=below:$ p $] (1) at (3,-1) {};
	\node[vertex, label=below:$ o $] (2) at (1.5,-1) {};
	\node[vertex, label=below:$ q $] (3) at (4.5,-1) {};
	\node[vertex, label=above:$ t $] (4) at (2,0) {};
	\node[vertex, label=above:$ u $] (5) at (4,0) {};
	\node[vertex, label=right:$ s $] (6) at (1,0) {};
	\node[vertex, label=left:$ v $] (7) at (5,0) {};
	\node[vertex, label=left:$ r $] (8) at (0,0) {};
	\node[vertex, label=right:$ w $] (9) at (6,0) {};
	\node[vertex, label=above:$ x $] (10) at (1.5,1) {};
	\node[vertex, label=above:$ z $] (11) at (4.5,1) {};
	\node[vertex, label=above:$ y $] (12) at (3,1) {};
	\path (1) edge (2);	
	\path (1) edge (3);	
	\path (1) edge (8);	
	\path (1) edge (9);		
	\path (2) edge (4);	
	\path (2) edge (6);	
	\path (3) edge (5);	
	\path (3) edge (7);
	\path (4) edge (5);
	\path (4) edge (10);
	\path (5) edge (11);
	\path (6) edge (8);
	\path (6) edge (10);
	\path (7) edge (9);
	\path (7) edge (11);
	\path (8) edge (12);
	\path (9) edge (12);
	\path (10) edge (12);
	\path (11) edge (12);	
	\pgftext[base, x=3cm,y=-2cm]{$H$};
	\end{scope}
	\end{tikzpicture}
\end{center}

Ali sta grafa $G$ in $H$ izomorfna? Odgovor natančno utemeljite.
\end{zad}










\begin{zad}
Dan imamo graf $G$:
\begin{center}
\begin{tikzpicture}[scale=.4]
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878);
\node at (5.84,-2.232050807568878) {$x$};
\node at (5.84,2.232050807568878) {$y$};
\node at (-0.62,-0.6) {$v$};
\node at (1.84,-0.6) {$w$};
\node at (-4.62,2.2320508075688774) {$z$};
\node at (-4.62,-2.2320508075688774) {$u$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0);
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0);
\draw [line width=1pt] (-1.12,0)-- (2.34,0);
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
Poiščite vse izomorfizme grafa $G$ na graf $G$ (tj.~grafa $G$ nase). 
(Izomorfizem grafa $G$ nase se imenuje {\it avtomorfizem} grafa $G$). Odgovor natančno utemeljite.
\end{zad}









\begin{zad}
Dan imamo graf $G$:
\begin{center}
\begin{tikzpicture}[scale=.35]
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878);
\node at (5.84,-2.232050807568878) {$f$};
\node at (5.84,2.232050807568878) {$e$};
\node at (-0.62,-0.6) {$c$};
\node at (1.84,-0.6) {$d$};
\node at (-4.62,2.2320508075688774) {$a$};
\node at (-4.62,-2.2320508075688774) {$b$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0);
\draw [line width=1pt] (-1.12,0)-- (2.34,0);
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
Poiščite vse izomorfizme grafa $G$ na graf $G$ (tj.~grafa $G$ nase).
(Izomorfizem grafa $G$ nase se imenuje {\it avtomorfizem} grafa $G$).
\end{zad}









\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}







\newpage
\section{Eulerjev in Hamiltonski graf.}






\begin{zad}
Ali ima naslednji digraf
\begin{center}
\includegraphics[width=.35\textwidth]{digraph.png}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Eulerjev obhod?
\item nesklenjeno Eulerjevo sled?
\item hamiltonski cikel?
\item hamiltonsko pot?
\end{enumerate}
Za vsako vprašanje, če je odgovor pritrdilen, narišite obhod/sled/cikel/pot, če pa je odgovor negativen, odgovor utemeljite.
\end{zad}






\begin{zad}
Za vsakega od naslednjih grafov določite:
\begin{enumerate}[label=\rm(\alph*)]
\item ali vsebuje induciran podgraf, ki ni dvodelen in ki ima $6$ točk;
\item ali je Eulerjev;
\item ali vsebuje nesklenjeno Eulerjevo sled;
\item ali je hamiltonski.
\end{enumerate}
\begin{center}
\includegraphics[scale=1.2]{tri-grafi-e-ham_v8}
\end{center}
\end{zad}






\begin{zad}
Naj bo $G$ enostaven graf z $n$ točkami in $m$ povezavami, kjer je $n\ge 3$. Predpostavimo, da je $m\ge \frac{(n-1)(n-2)}{2}+2$. Dokažite, da je $G$ hamiltonski. Ali velja obrat?
\end{zad}







\section{Eulerjev graf. Hamiltonski graf. Kruskalov algoritem}






\begin{zad}
Uporabite Kruskalov algoritem, da poiščete vpeto drevo najmanjše teže za graf, podan na spodnji sliki. Opišite vse korake algoritma in navedite težo dobljenega drevesa.
\begin{center}
\includegraphics[width=.4\textwidth]{kruskal-dn2}
\end{center}
\end{zad}





\begin{zad}
Dan je naslednji graf $G$:
\begin{center}
\includegraphics[scale=1]{ham}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Ugotovite, ali $G$ ima ima hamiltonski cikel. Če $G$ ima hamiltonski cikel, poiščite takšen cikel. Če ga nima, navedite argument (in razložite), zakaj takšen cikel ne obstaja.%\hfill{\small[25\%]}
\item Ali je $G$ Eulerjev graf? Odgovor utemeljite.%\hfill{\small[25\%]}
\item Za graf $G$ na sliki podajte primer vpetega drevesa.%\hfill{\small[25\%]}
\item Za graf $G$ na sliki podajte primer vpetega podgrafa, ki ni dvodelen.
\end{enumerate}
\end{zad}







\begin{zad}
Dan je naslednji graf $H$:

\begin{center}
	\begin{tikzpicture}[scale=1, vertex/.style={inner sep=2pt,draw,circle}]
	\begin{scope}
	\node[vertex, label=below:$ a $] (1) at (0,0) {};
	\node[vertex, label=below:$ b $] (2) at (2,0) {};
	\node[vertex, label=below:$ c $] (3) at (4,0) {};
	\node[vertex, label=above:$ f $] (4) at (0,1.5) {};
	\node[vertex, label=above:$ e $] (5) at (2,1.5) {};
	\node[vertex, label=above:$ d $] (6) at (4,1.5) {};
	\path (1) edge (2);
	\path (1) edge (6);
	\path (1) edge (5);
    \path (1) edge[bend right=75, looseness=0.75] (3);	
	\path (2) edge (3);
	\path (2) edge (4);
	\path (2) edge (6);
	\path (3) edge (5);
	\path (3) edge (4);
	\path (4) edge (5);
    \path (4) edge[bend left=75, looseness=0.75] (6);	
	\path (5) edge (6);	
	\pgftext[base, x=5cm,y=-0.75cm]{\small$H$};
	\end{scope}
	\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
  \item Ali je $H$ regularen?
  \item Ali je $H$ hamiltonski?
  \item Ali je $H$ Eulerjev?
\end{enumerate}
Odgovore ustrezno utemeljite.
\end{zad}









\begin{zad}
Dan imamo naslednji graf $G$ s težami na povezavah:
\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,draw,circle}]
	\begin{scope}
	\node[vertex, label=below:$ a $] (1) at (0,0) {};
	\node[vertex, label=below:$ b $] (2) at (2,0) {};
	\node[vertex, label=below:$ c $] (3) at (4,0) {};
	\node[vertex, label=left:$ d $] (4) at (0,2) {};
	\node[vertex, label=above:$ e $] (5) at (2,2) {};
	\node[vertex, label=right:$ f $] (6) at (4,2) {};
	\draw (2) -- (3) -- (6) -- (2) -- (5) -- (6);
	\draw (1) -- (4) -- (2) -- (1);
	\draw (4) -- (5);
	\path (1) edge[bend right=45, looseness=0.9] (3);
	\path (1) edge[bend left=100, looseness=2.2] (5);
	\path (3) edge[bend right=100, looseness=2.2] (5);
	\pgftext[base, x=1cm,y=-0.3cm]{$13$};
	\pgftext[base, x=3cm,y=-0.3cm]{$8$};
	\pgftext[base, x=1cm,y=2.15cm]{$10$};
	\pgftext[base, x=3cm,y=2.15cm]{$13$};	
	\pgftext[base, x=-0.25cm,y=1cm]{$12$};
	\pgftext[base, x=4.25cm,y=1cm]{$10$};
	\pgftext[base, x=2cm,y=-1.15cm]{$12$};
	\pgftext[base, x=2.25cm,y=1cm]{$13$};	
	\pgftext[base, x=1cm,y=1.15cm, rotate=-45]{$13$};
	\pgftext[base, x=3cm,y=1.15cm, rotate=45]{$9$};
	\pgftext[base, x=-0.45cm,y=2.45cm, rotate=45]{$8$};
	\pgftext[base, x=4.45cm,y=2.45cm, rotate=-45]{$12$};
	\end{scope}
	\end{tikzpicture}
\end{center}


\begin{enumerate}[label=\rm(\alph*)]
\item S pomočjo Kruskalovega algoritma poiščite najlažje vpeto drevo v grafu $G$ in določite njegovo težo. Opišite vsak korak algoritma.
\item Ali je najlažje vpeto drevo enolično določeno? Odgovor utemeljite.
\item Ali lahko usmerimo povezave grafa $G$ tako, da bo dobljen digraf $D$ krepko povezan? Podajte ustrezno usmeritev ali utemeljite, zakaj ta ne obstaja.
\item Ali lahko usmerimo povezave grafa $G$ tako, da bo dobljen digraf $D$ vseboval Eulejrev obhod? Podajte ustrezno usmeritev ali utemeljite, zakaj ta ne obstaja.
\end{enumerate}
\end{zad}








\begin{zad}
Naj bo $G$ naslednji povezavno utežen graf.

\begin{center}
\begin{tikzpicture}[scale=.55]
\GraphInit[vstyle=Dijkstra]
\SetVertexMath
\SetGraphUnit{4}
\node at (-5,7) {\Large{$G$}};
				\Vertices{square}{g,d,a,f}
				\WE(f){h}
				\EA(a){b}
				\EA(d){c}
				\NO(a){e}
				\Edge[label=$1$](h)(f)
				\Edge[label=$4$](g)(f)
				\Edge[label=$2$](h)(g)
				\Edge[label=$2$](g)(d)
				\Edge[label=$3$](d)(c)
				\Edge[label=$4$](f)(e)
				\Edge[label=$3$](a)(d)
				\Edge[label=$2$](a)(e)
\Edge[label=$1$](a)(b)
\Edge[label=$2$](a)(c)
\Edge[label=$2$](c)(b)
\Edge[label=$3$](e)(b)
\end{tikzpicture}
\end{center}



\begin{enumerate}[label=\rm(\alph*)]
\item Uporabite Kruskalovo požrešno metodo, da poiščete najlažje vpeto drevo (najmanjši konektor) grafa $G$. Pojasnite vse korake, potrebne za pridobitev vaše rešitve.
\item Ugotovite, ali je drevo, izračunano v prejšnjem delu naloge, enolično določeno, tj.~ali obstaja še kakšno drugo drevo z enako težo, ki ga je mogoče dobiti s Kruskalovo metodo.
\item Ali je $G$ hamiltonski? Če je odgovor pritrdilen, poiščite hamiltonski cikel v $G$.
\item Izračunajte $\chi(G)$.
\item Pokažite, da obstaja homomorfizem grafa $G$ v graf $K_r$, kjer je $r = \chi(G)$.
\end{enumerate}
\end{zad}












\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}







\newpage
\section{Digraf}





\begin{zad}
Oglejmo si naslednji digraf $D$.
\begin{center}
\includegraphics[width=0.2\textwidth]{digraph}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Poiščite razliko med vhodno in izhodno stopnjo za vsako točko.
\item Ali $D$ vsebuje Eulerjev obhod? Odgovor utemeljite.
\end{enumerate}
\end{zad}





\begin{zad}
Dve posebni vrsti točk sta bolj zanimivi za digrafe kot za neusmerjene grafe. Točka, ki ni začetna točka (rep) nobene povezave, tj.~brez ``puščic'', ki vodijo stran od nje, se imenuje {\bf ponor}. {\bf Izvor} je točka, ki ni končna točka (glava) nobene povezave.

\medskip
Oglejmo si dan digraf $D$.
%%\includegraphics[scale=.25]{digraph-e}
\begin{center}
\begin{tikzpicture}[->,>=stealth, node distance=2cm, auto, thick, state/.style={inner sep=2pt,draw,circle}]
    \node[state] (v) {$v$};
    \node[state] (u) [right of=v] {$u$};
    \node[state] (t) [right of=u] {$t$};
    \node[state] (w) [right of=t] {$w$};
    \node[state] (z) [right of=w] {$z$};
    \node[state] (x) [below of=t] {$x$};
    \node[state] (y) [below of=w] {$y$};

    \path (u) edge[bend left] (v)
              edge[bend right] (v)
          (t) edge (u)
          (t) edge (w)
              edge (x)
          (z) edge (w)
          (w) edge (y)
          (x) edge (y);

\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Ali je $D$ šibko povezan?
\item Ali je $D$ krepko povezan?
\item Ali obstaja cikel v digrafu $D$?
\item Poiščite vse ponore grafa $D$.
\item Poiščite vse izvore grafa $D$.
\end{enumerate}
\end{zad}







\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Podajte tri različne primere usmerjenih grafov z množico točk $\{a,b,c,d,e,f,g,h\}$. Spomnimo, usmerjen graf je digraf, katerega temeljni graf je enostaven.
\item Določite število usmerjenih grafov z množico točk $\{a,b,c,d,e,f,g,h\}$.
\item Podajte tri različne primere digrafov z množico točk $\{a,b,c,d,e,f,g,h\}$, ki ne vsebujejo večkratnih povezav in zank.
\item Določite število digrafov z množico točk $\{a,b,c,d,e,f,g,h\}$, ki ne vsebujejo večkratnih povezav in zank.
\end{enumerate}
\end{zad}




\begin{zad}
Dokažite, da je za vsako naravno število $n\geq 2$ povezave polnega grafa na $n$ točkah mogoče usmeriti tako, da imajo vse točke dobljenega digrafa različne izhodne stopnje.
\end{zad}







\begin{zad}
Na vajah smo pokazali, da je število enostavnih grafov z množico točk $\{1, 2, \ldots, n\}$ enako $2^{{n \choose 2}}$.
\begin{enumerate}[label=\rm(\alph*)]
\item Določite število digrafov z množico točk $\{1, 2, \ldots, n\}$, ki ne vsebujejo večkratnih povezav (tj.~več kot ene usmerjene povezave od iste začetne do iste končne točke) in zank (tj. usmerjenih povezav, ki povezujejo neko točko s samo seboj).
\item Določite število digrafov z množico točk $\{1, 2, \ldots, n\}$, ki ne vsebujejo večkratnih povezav, v poljubni točki pa imajo lahko največ eno zanko.
\item Določite število usmerjenih grafov z množico točk $\{1, 2, \ldots, n\}$.
\item {\bf Turnir} je usmerjen graf, katerega temeljni graf je poln. Določite število turnirjev z množico točk $\{1, 2, \ldots, n\}$.
\end{enumerate}
\end{zad}





\begin{zad}
Pokažite, da je digraf $D$, v katerem imajo vse točke vhodno stopnjo enako izhodni stopnji, krepko povezan natanko tedaj ko je šibko povezan.
\end{zad}








\begin{zad}
\label{hGr}
Dve posebni vrsti točk sta bolj zanimivi za digrafe kot za neusmerjene grafe. Točka, ki ni začetna točka (rep) katere koli povezave, tj.~brez ``puščic'', ki vodijo stran od nje, se imenuje {\bf ponor}. {\bf Izvor} je točka, ki ni končna točka (glava) nobene povezave.


\medskip
Pokažite, da ima vsak acikličen digraf vsaj en ponor in vsaj en izvor.
\end{zad}








\begin{zad}
Če je točke digrafa z $n$ točkami mogoče oštevilčiti od $1$ do $n$ tako, da je $i > j$, kadar koli obstaja sprehod od točke $i$ do točke $j$, potem takšno označevanje njegovih točk imenujemo {\bf razvrščeno označevanje}.

\medskip
Pokažite, da ima vsak acikličen digraf vsaj eno razvrščeno označevanje.
\end{zad}






\section{Drevo in digraf}




\begin{zad}
Naj bo $T$ drevo. Pokažite, da je povezave drevesa $T$ mogoče usmeriti tako, da v dobljenem usmerjenem grafu za vsako točko velja, da se vhodna in izhodna stopnja razlikujeta za največ ena.
\end{zad}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\section{Prirejanje}


\begin{zad}
Če imajo vse točke grafa $G$ stopnjo enako $k$, je graf {\bf $\boldsymbol{k}$-regularen}.

Naj bo $k>0$ in $G$ dvodelen $k$-regularen graf z biparticijo $\{A,B\}$. Pokažite, da ima graf $G$ prirejanje, ki zasiči $A$.
\end{zad}







\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}







\newpage
\section{Ravninski grafi in kromatično število grafa}




\begin{zad}
Ali sta naslednja dva grafa:
\begin{enumerate}[label=\rm(\roman*)]
  \item izomorfna drug drugemu?
  \item ravninska?
\end{enumerate}
\begin{center}
  \includegraphics[width=.5\textwidth]{IsomPlanar}
  \end{center}
\end{zad}





\begin{zad}
Dan imamo graf $G$:
\begin{center}
\includegraphics{ravninski-2}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Za graf $G$ na sliki podajte primer induciranega podgrafa, ki ni dvodelen in ki ima $5$ točk.
\item Ali je $G$ ravninski?
\item Določite kromatično število grafa $G$.
\end{enumerate}
\end{zad}








\begin{zad}
Dan imamo graf $L$:
\begin{center}
\includegraphics{rav-v2}~~$L$
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Ali je graf $L$ ravninski? Odgovor utemeljite.
\item Poiščite kromatično število grafa $L$.
\item Ali je $\chi(L,2)>0$? Ali je $\chi(L,3)>0$? Ali je $\chi(L,4)>0$? Odgovore utemeljite.
\end{enumerate}
\end{zad}








\begin{zad}
Dan je naslednji graf $G$:
\begin{center}
\begin{tikzpicture}[scale=.4]
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878);
\node at (5.84,-2.232050807568878) {$f$};
\node at (5.84,2.232050807568878) {$e$};
\node at (-0.62,-0.6) {$c$};
\node at (1.84,-0.6) {$d$};
\node at (-4.62,2.2320508075688774) {$a$};
\node at (-4.62,-2.2320508075688774) {$b$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0);
\draw [line width=1pt] (-1.12,0)-- (2.34,0);
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Poiščite vse izomorfizme grafa $G$ na graf $G$ (tj.~grafa $G$ nase).
(Izomorfizem grafa $G$ nase se imenuje {\it avtomorfizem} grafa $G$).
\item Poiščite kromatično število grafa $G$ in izračunajte kromatični polinom $\chi(G,t)$.
\end{enumerate}
\end{zad}







\begin{zad}
Dan je naslednji graf 
\begin{center}
\centering\includegraphics[width=0.45\textwidth]{KspsC}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Ali je mogoče dani graf narisati, ne da bi dvignili svinčnik s papirja, tako da nikoli ne gremo skozi že narisano povezavo in da se risba začne in konča na isti točki?
\item Poiščite kromatično število danega grafa.
\item Pokažite, da graf ni ravninski.
\end{enumerate}
\end{zad}







\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Poiščite dva $4$-točkovna grafa z različnima kromatičnima polinomoma.
\item Poiščite dva neizomorfna $4$-točkovna grafa z enakima kromatičnima polinomoma.
\item Dokažite, da je število načinov za pravilno barvanje $n$-točkovnega cikla $C_n$ z $n \geq 3$ in $t$ barvami enako
\begin{itemize}
\item $(t-1)[(t-1)^{n - 1}+1]$, če je $n$ sodo število.
\item $(t-1)[(t-1)^{n - 1}-1]$, če je $n$ liho število.
\end{itemize}
\end{enumerate}
\end{zad}










\section{Različne naloge}






\begin{zad}
Dan je naslednji graf $G$:
\begin{center}
\includegraphics{graphG2-dn}
$G$
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Ali je $G$ Eulerjev?
\item Ali $G$ vsebuje Eulerjevo sled?
\item Ali je $G$ hamiltonski?
\item Določite kromatično število grafa $G$.
\end{enumerate}
\end{zad}








\begin{zad}
\label{Kg2i}
\textbf{Kolesni graf} $W_n$ z $n \ge 4$ je graf z $n$ točkami (vozlišči), ki ga tvori cikel $C_{n-1}$ (ki ga tukaj imenujemo \textit{zunanji cikel}) in eno dodatno točko v središču cikla, ki je sosednja z vsako točko v ciklu.
\begin{enumerate}[label=\rm(\alph*)]
\item Narišite kolesa $W_4, W_5, W_6$ in $W_7$. Najprej začnite z zunanjim ciklom in potem narišete točko v središču. Nato narišite vse povezave, ki jih zahteva definicija.
\item Za katere $n\ge 4$ je $W_n$ Eulerjev graf? 
Za katere $n\ge 4$ ima $W_n$ Eulerjevo sled?
\item Za katere $n\ge 4$ je  $W_n$ hamiltonski graf? 
\item Pokažite, da obstaja takšna usmeritev povezav grafa $W_n$, da je razlika vhodne in izhodne stopnje vsake točke (v absolutni vrednosti) največ ena.
\end{enumerate}
\end{zad}






\begin{zad}
Naj bo $W_n$ kolesni graf iz prejšnje naloge (glej nalogo \ref{Kg2i}).
\begin{enumerate}[label=\rm(\alph*)]
\item Izračunajte klično število  $\omega{(W_n)}$ grafa $W_n$ (največjo moč klike grafa $W_n$).
\item Poiščite kromatično število $\chi{(W_n)}$ grafa $W_n$.
%\item Izračunajte neodvisno število $\alpha{(W_n)}$ grafa $W_n$ (moč največje neodvisne  množice grafa $G$).
\item Pokažite, da je kromatični polinom grafa $W_n$ enak
	{$$\chi(W_n, t) = t\left((t-2)^{n-1}-(-1)^{n}(t-2)\right).$$}
\end{enumerate}
\end{zad}







\begin{zad}
Oglejte si spodnji graf $G$ in odgovorite na vprašanja. Odgovore utemeljite.

		\begin{center}
			\begin{tabular}{c}
				\begin{tikzpicture}[scale=.35]
					\SetVertexMath
					\GraphInit[vstyle=Classic]
					\tikzset{VertexStyle/.style = {
							shape = circle,
							fill = black,%
							inner sep = 0pt,
							outer sep = 0pt,
							minimum size = 7pt,
							%vstyle=Classic,
							draw}}
					\SetGraphUnit{5}
					\Vertices{circle}{c,b,a,h,g,f,e,d}
					\foreach \v in {c,e,f,g}{\Edge(a)(\v)}
					\foreach \v in {d,e,f,g}{\Edge(b)(\v)}
					\foreach \v in {f,g,h}  {\Edge(c)(\v)}
					\foreach \v in {f,g,h}  {\Edge(d)(\v)}
					\foreach \v in {g,h}    {\Edge(e)(\v)}
					\foreach \v in {h}      {\Edge(f)(\v)}
				\end{tikzpicture}
				\\
				\large{$G$}
			\end{tabular}
		\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Ali je $G$ hamiltonski?
\item Ali je $G$ povezan?
\item Ali je $G$ Eulerjev? Ali vsebuje Eulerjevo sled?
\item Ali je $G$ ravninski?
\item Določite $\chi(G)$.
\end{enumerate}
\end{zad}







\begin{zad}
Naj bo $G$ naslednji povezavno utežen graf.
\begin{center}
\includegraphics[scale=1]{rail}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Z uporabo Kruskalove požrešne metode določite vpeto drevo najmanjše teže v $G$ in navedite njegovo težo. Zapišite korake algoritma.
\item Ugotovite, ali je drevo, izračunano v prejšnjem delu naloge, enolično določeno, tj.~ali obstaja še kakšno drugo drevo z enako težo, ki ga je mogoče dobiti s Kruskalovo metodo.
\item Ali je $G$ Eulerjev graf? Če je odgovor pritrdilen, zapišite ustrezno sled, če pa je odgovor negativen, odgovor utemeljite.
\item Ali je $G$ hamiltonski? Ali $G$ ima hamiltonsko pot? Če je odgovor pritrdilen, zapišite ustrezen cikel/pot, če pa je odgovor negativen, odgovor utemeljite.
\item Izračunajte $\chi(G)$.
\end{enumerate}
\end{zad}





\bigskip
\begin{center}
Vse naloge so prenesene z naslednje spletne strani: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc Na isti strani lahko bralec najde vse rešitve podanih nalog.}
\end{center}








\end{document}
