\documentclass[10pt,a4paper,danish]{article}
\usepackage[english]{babel} 
\usepackage{graphicx,multicol}
\usepackage{epic,eepic,epsfig}
\usepackage{amssymb}
\input{header}

\fancyhead{}
\fancyhead[L]{Institut for Matematik og Datalogi \\
              Syddansk Universitet, Odense}
\fancyhead[R]{11 februar 2016 \\ JBJ}

\newcommand{\tab}{\hspace*{7mm}}
\newtheorem{theorem}{Theorem}
\begin{document}
\vspace{2ex}
\begin{center}
  {\LARGE DM551 -- 2.\ Eksamensopgave}\\[3mm]
  {\large Afleveres senest fredag den 1/4 2016 kl 10.00}.
\end{center}
\vspace{1ex}


\section*{Regler}

Dette er det andet af to opgaves\ae{}t, som sammen med den mundtlige eksamen
13-15 April udg\o{}r eksamen i MM541. Dette opgaves\ae{}t skal besvares selvst\ae{}ndigt. Det er ikke tilladt at arbejde sammen med andre om opgaverne. I m\aa{} derfor ikke vise jeres besvarelse til andre.

Husk, at jeres besvarelse af denne opgave (ligesom det var tilf\ae{}ldet med den f\o{}rste) er en del af eksamen, s\aa{} g\o{}r jer umage med, at besvare alle sp\o{}rgsm\aa{}lene. {\bf Det er vigtigt, at I argumenterer, s\aa{} l\ae{}seren kan f\o{}lge jeres udregninger og forklaringer.}






\subsection*{Hvordan afleverer I jeres rapport?}

Rapporten skal afleveres  {\bf b\aa{}de (!!!)}

\begin{itemize}
\item som en   {\bf papir} kopi til instruktoren, dvs i dennes hyttefad  (hvis I \o{}nsker en kopi tilbage med rettelser p\aa{}, skal I aflevere 2 kopier!) {\bf og}
\item som en {\bf PDF} fil via Blackboard. Andre formater end PDF accepteres ikke!
  
\end{itemize}
P\aa{} forsiden skal I skrive det fulde navn og de f\o{}rste 6 cifre i cpr nummer.

Aflevering via Blackboard sker som f\o{}lger:

\begin{itemize}
\item V\ae{}lg ``MM541, Kombinatorisk Matematik, for\aa{}r 2016''.
\item Klik p\aa{} ``SDU Assignment'' (i menuen i venstre side).
\item Udfyld formularen og vedh\ae{}ft din PDF fil. Afslut med 'submit'
\item Blackboard sender en kvittering via email.
\end{itemize}

\newpage
\section{Eksamens opgaver}
L\o{}s nedenst\aa{}ende opgaver. {\bf Husk at begrunde alle svar!}
\subsection*{Opgave 1}
Denne opgave handler om mindste udsp\ae{}nde tr\ae{}r.
\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.00034996in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
{\renewcommand{\dashlinestretch}{30}
\begin{picture}(6302,4725)(0,-10)
\put(465,2400){\blacken\ellipse{270}{270}}
\put(465,2400){\ellipse{270}{270}}
\put(1815,4200){\blacken\ellipse{270}{270}}
\put(1815,4200){\ellipse{270}{270}}
\put(1815,600){\blacken\ellipse{270}{270}}
\put(1815,600){\ellipse{270}{270}}
\put(3165,2400){\blacken\ellipse{270}{270}}
\put(3165,2400){\ellipse{270}{270}}
\put(4515,4200){\blacken\ellipse{270}{270}}
\put(4515,4200){\ellipse{270}{270}}
\put(4515,600){\blacken\ellipse{270}{270}}
\put(4515,600){\ellipse{270}{270}}
\put(5865,2400){\blacken\ellipse{270}{270}}
\put(5865,2400){\ellipse{270}{270}}
\path(1815,4200)(3165,2355)
\path(1815,4200)(3165,2355)
\path(510,2400)(3120,2400)
\path(510,2400)(3120,2400)
\path(1815,4200)(465,2445)
\path(1815,4200)(465,2445)
\path(465,2400)(1815,600)
\path(465,2400)(1815,600)
\drawline(4515,3750)(4515,3750)
\path(1815,4200)(4560,4200)
\path(1815,4200)(4560,4200)
\path(4515,4200)(5910,2400)
\path(4515,4200)(5910,2400)
\path(5910,2400)(3210,2400)
\path(5910,2400)(3210,2400)
\path(3210,2400)(4560,645)
\path(3210,2400)(4560,645)
\path(1815,600)(4515,600)
\path(1815,600)(4515,600)
\path(4515,600)(5865,2400)
\path(4515,600)(5865,2400)
\path(4515,4245)(3120,2400)
\path(4515,4245)(3120,2400)
\path(3210,2445)(1770,555)
\path(3210,2445)(1770,555)
\put(15,2355){\makebox(0,0)[lb]{\smash{{$a$}}}}
\put(1680,4515){\makebox(0,0)[lb]{\smash{{$b$}}}}
\put(1680,15){\makebox(0,0)[lb]{\smash{{$c$}}}}
\put(3030,2760){\makebox(0,0)[lb]{\smash{{$d$}}}}
\put(4470,4605){\makebox(0,0)[lb]{\smash{{$e$}}}}
\put(4425,105){\makebox(0,0)[lb]{\smash{{$f$}}}}
\put(6180,2355){\makebox(0,0)[lb]{\smash{{$g$}}}}
\put(1185,3075){\makebox(0,0)[lb]{\smash{{$10$}}}}
\put(1455,2175){\makebox(0,0)[lb]{\smash{{$2$}}}}
\put(2625,1275){\makebox(0,0)[lb]{\smash{{$5$}}}}
\put(2580,3480){\makebox(0,0)[lb]{\smash{{$7$}}}}
\put(3930,3210){\makebox(0,0)[lb]{\smash{{$1$}}}}
\put(3030,4335){\makebox(0,0)[lb]{\smash{{$2$}}}}
\put(5280,3480){\makebox(0,0)[lb]{\smash{{$1$}}}}
\put(4425,2085){\makebox(0,0)[lb]{\smash{{$2$}}}}
\put(3525,1275){\makebox(0,0)[lb]{\smash{{$3$}}}}
\put(2985,195){\makebox(0,0)[lb]{\smash{{$4$}}}}
\put(5415,1365){\makebox(0,0)[lb]{\smash{{$3$}}}}
\put(825,1365){\makebox(0,0)[lb]{\smash{{$3$}}}}
\end{picture}
}

\end{center}
\caption{}\label{fig1}
\end{figure}
\begin{itemize}
\item[(i)] H\aa{}ndk\o{}r Kruskals algoritme (ogs\aa{} kaldet den gr\aa{}dige algoritme) p\aa{} den v\ae{}gtede graf i Figur \ref{fig1}. Det skal fremg\aa{} klart af din besvarelse, hvilke kanter du ser p\aa{} i de enkelte skridt. Dette kan du f.eks. g\o{}re ved, at vise en lille tegning, der viser, hvordan skoven best\aa{}ende af de kanter, der er valgt indtil nu udvikler sig og forklare, hvorfor en kant evt ikke kommer med i l\o{}sningen. Du kan ogs\aa{} n\o{}jes med at forklare i ord hvad der sker med de enkelte kanter, efterh\aa{}nden som algoritmen betragter dem. Du skal naturligvis angive det endelige tr\ae{}.
\item[(ii)] Illusterer Prims algoritme p\aa{} grafen i Figur \ref{fig1}. {\bf Du skal starte dit tr\ae{} i knuden $a$}. Husk at forklare, hvordan du finder den n\ae{}ste kant at tilf\o{}je.
\item[(iii)] Antag nu, at $G=(V,E)$ er en kantv\ae{}gtet graf, hvor alle v\ae{}gte er forskellige. Bevis, at $G$ har pr\ae{}cist et minimum udsp\ae{}ndende tr\ae{}. 
\end{itemize}



\subsection*{Opgave 2}
J\o{}rgen har lige f\aa{}et arbejde (p\aa{} pr\o{}ve) ved  et online 
datingbureau. Han er blevet ansat, fordi han har sagt, at han er god til kombinatorik og at dette ville kunne hj\ae{}lpe bureauet til at f\aa{} flere tilfredse kunder. Hans f\o{}rste opgave bliver, at lave en dating plan til den kommende fredag for 5 kvinder Nina, Ida, Emma, Anne og Bea og 5 m\ae{}nd Jan, Bo, Per, Ib og Jon,
ud fra f\o{}lgende info givet af de 5 kvindelige deltagere (m\ae{}ndene blev ikke spurgt i denne omgang). Reglen er, at ingen kvinde m\aa{} date mere end 1 mand ad gangen og omvendt.
\begin{itemize}
\item Nina har angivet at hun gerne vil date en af Bo, Per,Ib og Jan
\item Ida har angivet at hun gerne vil date en af Jan og Bo
\item Anne har angivet at hun gerne vil date en af Ib, Jon og Per
\item Bea har angivet at hun gerne vil date en af Jan og Bo
\item Emma har angivet at hun gerne vil date en af Bo og Jan
\end{itemize}
J\o{}rgen har overvurderet sine evner og k\ae{}mper med at f\aa{} lavet en plan, men det lykkes aldrig, s\aa{} han stiller opgaven til sine MM541 elever og du skal derfor hj\ae{}lpe ham med f\o{}lgende sp\o{}rgsm\aa{}l. Du skal g\o{}re dette ved at formulere problemet som et pardannelsesproblem for en 2-delt graf.
\begin{itemize}
\item[(a)] Tegn den 2-delte graf som modellerer J\o{}rgens problem.
\item[(b)] Giv en let forklarlig grund til at J\o{}rgen ikke fandt en dating plan, dvs noget som viser, at der slet ikke findes en s\aa{}dan ud fra de opgivne data. 
\item[(c)] Hvad er det st\o{}rst mulige antal par der kan laves?
\item[(d)] Du skal ogs\aa{} forklare hvordan man, for alle tilsvarende dating problemer (hvor der kan v\ae{}re mange flere m\ae{}nd og kvinder), enten kan finde  en god plan hvor alle kan date, eller en delm\ae{}ngde af personerne som viser, at der ikke kan findes en s\aa{}dan plan. Specielt skal du kort forklare, hvordan man finder en s\aa{}dan delm\ae{}ngde, n\aa{}r der ikke findes en perfekt parring.
\end{itemize}
J\o{}rgen vender tilbage til sin chef med din l\o{}sning og bliver straks lovet fastans\ae{}ttelse, fordi chefen kan se et potentiale i din algoritme (som J\o{}rgen kom til at kalde sin egen). Men inden dette kan ske, skal J\o{}rgen finde en ny plan for de 5 kvinder ovenfor som tager f\ae{}rrest mulige dage og hvor alle de 13 dates kan afholdes, n\aa{}r kravet er, at ingen kvinde/mand m\aa{} have mere end en date den samme dag. Kan du ogs\aa{} hj\ae{}lpe ham med dette? Forklar gerne din svar med en kort beskrivelse af en algoritme, som altid producerer en plan med f\ae{}rrest mulige dating dage. Hint: benyt resultatet fra Opgave 2.5 i Tofts noter.

\subsection*{Opgave 3}
Find, ved at bruge jobtilordningsalgoritmen fra Tofts noter afsnit II.3,
en optimal pardannelse af st\o{}rrelse 5 i den 2-delte graf komplette
graf med punkter $\{A_1,\ldots{},A_5,B_1,\ldots{},B_5\}$ og kantv\ae{}gte som angivet i tabellen nedenfor. \\

\begin{figure}[h!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\hline
&$B_1$&$B_2$&$B_3$&$B_4$&$B_5$\\\hline
$A_1$&13&10&11&7&10\\\hline
$A_2$&7&8&8&5&10\\\hline
$A_3$&13&10&10&12&10\\\hline
$A_4$&6&1&4&3&5\\\hline
$A_5$&11&8&10&9&11\\\hline
\end{tabular}
\end{center}
\caption{V\ae{}rdien p\aa{} plads $(A_i,B_j)$ angiver v\ae{}gten $c_{ij}$ af kanten mellem $A_i$ og $B_j$.} 
\end{figure}
Du skal anvende f\o{}lgende strategi for at finde de initielle $\alpha,\beta$ v\ae{}rdier:

\begin{itemize}
\item For $i=1,2,3,4,5$ s\ae{}ttes $\alpha_i$ lig med mindste v\ae{}rdi af $c_{ij}$ i r\ae{}kken for $A_i$.
\item For  $j=1,2,3,4,5$ s\ae{}ttes $\beta_j$ lig med mindste v\ae{}rdi af $c_{ij}-\alpha_i$ i s\o{}jlen for $B_j$.
\end{itemize}

\noindent{} Herefter markerer du alle de celler hvor $\alpha_i+\beta_j=c_{ij}$ og markerer en st\o{}rst mulig pardannelse, som  du kan finde blandt de markerede celler 
(der er en af st\o{}rrelse 4).\\

\noindent{} Nu skal du vise, hvordan algoritmen udf\o{}res herfra. Dette inkluderer at vise hvordan du finder v\ae{}rdien af $\delta$ i algoritmen og opdaterer i hvert af de skridt algoritmen tager, n\aa{}r den startes som ovenfor.\\

N\aa{}r algoritmen slutter (med en pardannelse af st\o{}rrelse 5) skal du angive denne, samt argumentere for at den er optimal (dvs har mindst mulig omkostning).
\subsection*{Opgave 4}
Betragt f\o{}lgende lin\ae{}re programeringsproblem kaldet $P$ nedenfor.

\begin{tabular}{lrrr}
minimer & $5y_1 + 4y_2 +10y_3$&&\nonumber\\
ufa &     $2y_1+y_2$&$\geq 4$&\nonumber\\
          &  $y_2+2y_3$&$\geq 2$&\label{primal}\\
      &$-y_1+y_3$&$\geq -1$&\nonumber\\
      &$y_1,y_2,y_3$&$\geq 0$&\nonumber\\\nonumber
\end{tabular}

\begin{itemize}


\item[(a)] Opskriv det duale problem $D$ til $P$, hvor du bruger tre duale variable $x_1,x_2,x_3$, svarende til hver af de tre uligheder i $P$ taget oppefra. Du skal forklare, hvordan du konstruerer $D$
\item[(b)] G\o{}r rede for, at $(y_1,y_2,y_3)=(1,2,0)$ er en optimal l\o{}sning til det primale problem. Hint: brug s\ae{}tningen om komplement\ae{}re rester til at finde en l\o{}sning til $D$ med samme v\ae{}rdi.
\end{itemize}

\subsection*{Opgave 5}
Denne opgave omhandler rekursionsligninger (eng. recurrence relations).
 
\begin{itemize}
\item[(a)] L\o{}s rekursionsligningen $a_{n}=a_{n-1}+6a_{n-2}$ med startbetingelserne $a_0=2$ og $a_1=4$. Forklar hvordan du kommer frem til din l\o{}sning.
\item[(b)] L\o{}s rekursionsligningen $a_{n}=a_{n-1}+6a_{n-2}+4n$ med startbetingelserne $a_0=2$ og $a_1=8$.
\end{itemize}
\end{document}

\begin{figure}[h!]
\begin{center}

\end{center}
\caption{}
\end{figure}


