\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 -- 1.\ Eksamensopgave}\\[3mm]
  {\large Afleveres senest mandag den 29/2 2016 kl 14.00}.
\end{center}
\vspace{1ex}


\section*{Regler}

Dette er det f\o{}rste af to opgaves\ae{}t, som sammen med den mundtlige eksamen
i April udg\o{}r eksamen i MM541. Dette f\o{}rste opgaves\ae{}t m\aa{} l\o{}ses i grupper p\aa{} op til 3 personer. Det er ikke tilladt for forskellige grupper at arbejde sammen. I m\aa{} derfor ikke vise jeres besvarelse til andre end dem i jeres egen gruppe. P\aa{} den anden side kan I l\ae{}re meget af at diskutere opgaverne med hinanden. Derfor m\aa{} I gerne snakke om opgaverne p\aa{} et overordnet plan og I m\aa{} selvf\o{}lgelig diskutere eksaminatorieopgaver, som ligner de stillede opgaver.

Husk, at jeres besvarelse af denne opgave (og det andet s\ae{}t, som skal l\o{}ses individuelt) 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 (en per gruppe) 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 for alle deltagere i gruppen

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 en sportsturnering (f.eks ishockey) med $n$ deltagende hold, hvor hvert hold   spiller mod alle andre hold pr\ae{}cis en gang. Dvs hvis der f.eks er 4 hold $\{a,b,c,d\}$, s\aa{} er der 6 kampe, nemlig $ab,ac,ad,bc,bd,cd$, hvor $ij$ betyder $i$ mod $j$. Antag nedenfor, at ingen kampe ender uafgjort, dvs et af de to hold vinder kampen. Bem\ae{}rk yderligere, at resultatet (3-4) ikke er det samme som resultatet (4-3) for kampen mellem $i$ og $j$, da $i$ taber den f\o{}rste kamp og vinder den anden. 

\begin{itemize}
\item[(a)] Hvor mange kampe skal der spilles der ialt, hvis der er $n$ hold? Kald dette antal $K$ nedenfor.
\iffalse
\item[(b)] Bestem det st\o{}rste heltal $k=k(n)$ ($k$ afh\ae{}nger af $n$) som opfylder at uanset hvad resultatet af de $K$ kampe er, vil der altid v\ae{}re mindst et hold som har vundet mindst $k$ kampe. Giv ogs\aa{} et eksempel som viser at din fundne v\ae{}rdi af $k$ er den st\o{}rst mulige (dvs vis hvordan kampenes resultat kunne v\ae{}re s\aa{} intet hold vinder mere end $k$ kampe.
\fi
\item[(b)] Antag at intet hold laver mere end 7 m\aa{}l i en kamp. Hvor mange forskellige resultater er der s\aa{} af en kamp og hvor stor skal $n$ v\ae{}re f\o{}r der altid vil v\ae{}re to af de $K$ kampe, som  ender med det samme resultat?


\item[(c)] Turneringen spilles over en periode p\aa{} 6 m\aa{}neder. Hvor stor skal $n$ (antallet af hold) v\ae{}re for at der altid vil v\ae{}re 3 hold $x,y,z$ s\aa{}ledes at der enten g\ae{}leder, at alle de tre indbyrdes kampe mellem disse er spillet i de f\o{}rste 3 m\aa{}neder af turneringen, eller alle de tre kampe er spillet i de sidste 3 m\aa{}neder af turneringen?
\end{itemize}



\subsection*{Opgave 2}
Brug binomialformlen til at vise, at der for alle ikke negative heltal $n$ g\ae{}lder at 
$$\sum_{k=0}^n{n\choose k}3^n= \sum_{k=0}^{n}{n\choose k}5^k$$

\subsection*{Opgave 3}

\begin{itemize}
\item[(a)] Bestem antallet af ikke negative heltallige l\o{}sninger til $x_1+x_2+x_3=13$.
\item[(b)] Hvor mange l\o{}sninger er der, hvis vi ogs\aa{} kr\ae{}ver at  $x_1\geq 3,x_2\geq 1$ og $x_3\geq 2$.
\item[(c)] P\aa{} hvor mange m\aa{}der kan man fordele 13 identiske bolde i 3 forskellige kasser $k_1,k_2,k_3$, s\aa{}ledes at  $k_1$ indeholder h\o{}jst 5 bolde, $k_2$ indeholder h\o{}jst 6 bolde og $k_3$ indeholder h\o{}jst 4 bolde?
\end{itemize}

\subsection*{Opgave 4}

\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}(14177,3330)(0,-10)
\put(285,2940){\blacken\ellipse{128}{128}}
\put(285,2940){\ellipse{128}{128}}
\put(1410,2940){\blacken\ellipse{128}{128}}
\put(1410,2940){\ellipse{128}{128}}
\put(285,2040){\blacken\ellipse{128}{128}}
\put(285,2040){\ellipse{128}{128}}
\put(3660,2040){\blacken\ellipse{128}{128}}
\put(3660,2040){\ellipse{128}{128}}
\put(285,1140){\blacken\ellipse{128}{128}}
\put(285,1140){\ellipse{128}{128}}
\put(1410,1140){\blacken\ellipse{128}{128}}
\put(1410,1140){\ellipse{128}{128}}
\put(3660,1140){\blacken\ellipse{128}{128}}
\put(3660,1140){\ellipse{128}{128}}
\put(2535,2040){\blacken\ellipse{128}{128}}
\put(2535,2040){\ellipse{128}{128}}
\put(3660,2940){\blacken\ellipse{128}{128}}
\put(3660,2940){\ellipse{128}{128}}
\put(1410,2040){\blacken\ellipse{128}{128}}
\put(1410,2040){\ellipse{128}{128}}
\put(2535,2940){\blacken\ellipse{128}{128}}
\put(2535,2940){\ellipse{128}{128}}
\put(2535,1140){\blacken\ellipse{128}{128}}
\put(2535,1140){\ellipse{128}{128}}
\put(5235,2895){\blacken\ellipse{128}{128}}
\put(5235,2895){\ellipse{128}{128}}
\put(6360,2895){\blacken\ellipse{128}{128}}
\put(6360,2895){\ellipse{128}{128}}
\put(5235,1995){\blacken\ellipse{128}{128}}
\put(5235,1995){\ellipse{128}{128}}
\put(8610,1995){\blacken\ellipse{128}{128}}
\put(8610,1995){\ellipse{128}{128}}
\put(5235,1095){\blacken\ellipse{128}{128}}
\put(5235,1095){\ellipse{128}{128}}
\put(6360,1095){\blacken\ellipse{128}{128}}
\put(6360,1095){\ellipse{128}{128}}
\put(8610,1095){\blacken\ellipse{128}{128}}
\put(8610,1095){\ellipse{128}{128}}
\put(7485,1995){\blacken\ellipse{128}{128}}
\put(7485,1995){\ellipse{128}{128}}
\put(8610,2895){\blacken\ellipse{128}{128}}
\put(8610,2895){\ellipse{128}{128}}
\put(6360,1995){\blacken\ellipse{128}{128}}
\put(6360,1995){\ellipse{128}{128}}
\put(7485,2895){\blacken\ellipse{128}{128}}
\put(7485,2895){\ellipse{128}{128}}
\put(7485,1095){\blacken\ellipse{128}{128}}
\put(7485,1095){\ellipse{128}{128}}
\put(10410,2895){\blacken\ellipse{128}{128}}
\put(10410,2895){\ellipse{128}{128}}
\put(11535,2895){\blacken\ellipse{128}{128}}
\put(11535,2895){\ellipse{128}{128}}
\put(10410,1995){\blacken\ellipse{128}{128}}
\put(10410,1995){\ellipse{128}{128}}
\put(13785,1995){\blacken\ellipse{128}{128}}
\put(13785,1995){\ellipse{128}{128}}
\put(10410,1095){\blacken\ellipse{128}{128}}
\put(10410,1095){\ellipse{128}{128}}
\put(11535,1095){\blacken\ellipse{128}{128}}
\put(11535,1095){\ellipse{128}{128}}
\put(13785,1095){\blacken\ellipse{128}{128}}
\put(13785,1095){\ellipse{128}{128}}
\put(12660,1995){\blacken\ellipse{128}{128}}
\put(12660,1995){\ellipse{128}{128}}
\put(13785,2895){\blacken\ellipse{128}{128}}
\put(13785,2895){\ellipse{128}{128}}
\put(11535,1995){\blacken\ellipse{128}{128}}
\put(11535,1995){\ellipse{128}{128}}
\put(12660,2895){\blacken\ellipse{128}{128}}
\put(12660,2895){\ellipse{128}{128}}
\put(12660,1095){\blacken\ellipse{128}{128}}
\put(12660,1095){\ellipse{128}{128}}
\path(330,2940)(3660,2940)
\path(330,2940)(3660,2940)
\path(3660,2940)(3660,1140)
\path(3660,2940)(3660,1140)
\path(285,2940)(285,1185)
\path(285,2940)(285,1185)
\path(330,1140)(3615,1140)
\path(330,1140)(3615,1140)
\path(1410,2940)(1410,1140)
\path(1410,2940)(1410,1140)
\path(2535,2895)(2535,1095)
\path(2535,2895)(2535,1095)
\path(285,2040)(3660,2040)
\path(285,2040)(3660,2040)
\path(285,2940)(2535,1140)
\path(285,2040)(2535,2940)
\path(1410,2940)(3660,2040)
\path(285,2940)(1410,1095)
\path(5280,2895)(8610,2895)
\path(5280,2895)(8610,2895)
\path(8610,2895)(8610,1095)
\path(8610,2895)(8610,1095)
\path(5235,2895)(5235,1140)
\path(5235,2895)(5235,1140)
\path(5280,1095)(8565,1095)
\path(5280,1095)(8565,1095)
\path(6360,2895)(6360,1095)
\path(6360,2895)(6360,1095)
\path(7485,2850)(7485,1050)
\path(7485,2850)(7485,1050)
\path(5235,1995)(8610,1995)
\path(5235,1995)(8610,1995)
\path(5235,2895)(7485,1095)
\path(5235,2895)(6360,1050)
\path(10455,2895)(13785,2895)
\path(10455,2895)(13785,2895)
\path(13785,2895)(13785,1095)
\path(13785,2895)(13785,1095)
\path(10410,2895)(10410,1140)
\path(10410,2895)(10410,1140)
\path(10455,1095)(13740,1095)
\path(10455,1095)(13740,1095)
\path(11535,2895)(11535,1095)
\path(11535,2895)(11535,1095)
\path(12660,2850)(12660,1050)
\path(12660,2850)(12660,1050)
\path(10410,1995)(13785,1995)
\path(10410,1995)(13785,1995)
\path(11535,2895)(13785,1995)
\path(10410,2895)(11535,1050)
\path(7485,2895)(8610,1995)
\put(1635,15){\makebox(0,0)[lb]{\smash{{$G_1$}}}}
\put(240,3210){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}a}}}}
\put(2490,3165){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}c}}}}
\put(15,1995){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}e}}}}
\put(1590,2175){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}f}}}}
\put(2715,1770){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}g}}}}
\put(3885,1995){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}h}}}}
\put(195,780){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}i}}}}
\put(1365,825){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}j}}}}
\put(2445,825){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}k}}}}
\put(3570,800){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}l}}}}
\put(1410,3120){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}b}}}}
\put(3930,2895){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}d}}}}
\put(5190,3165){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}a}}}}
\put(7440,3120){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}c}}}}
\put(4965,1950){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}e}}}}
\put(6540,2130){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}f}}}}
\put(7665,1725){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}g}}}}
\put(8835,1950){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}h}}}}
\put(5145,735){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}i}}}}
\put(6315,780){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}j}}}}
\put(7395,780){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}k}}}}
\put(8520,750){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}l}}}}
\put(6360,3075){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}b}}}}
\put(8880,2850){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}d}}}}
\put(10365,3165){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}a}}}}
\put(12615,3120){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}c}}}}
\put(10140,1950){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}e}}}}
\put(11715,2130){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}f}}}}
\put(12840,1725){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}g}}}}
\put(14010,1950){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}h}}}}
\put(10320,735){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}i}}}}
\put(11490,780){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}j}}}}
\put(12570,780){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}k}}}}
\put(13695,740){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}l}}}}
\put(11535,3075){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}b}}}}
\put(14055,2850){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{6.0}{\rmdefault}{\mddefault}{\updefault}d}}}}
\put(6810,105){\makebox(0,0)[lb]{\smash{{$G_2$}}}}
\put(12030,105){\makebox(0,0)[lb]{\smash{{$G_3$}}}}
\end{picture}
}

\end{center}
\caption{Tre grafer som hver har 12 punkter betegnet $\{a,b,c,d,e,f,g,h,i,j,k,l\}$.}
\end{figure}

Lad $G_1,G_2,G_3$ v\ae{}re graferne i Figur 1.
\begin{itemize}
\item[(a)] Hvilke (om nogen) af graferne har en lukket Eulertur? For dem der har en s\aa{}dan, skal du angive en kantr\ae{}kkef\o{}lge, som er en Eulertur i grafen.
\item[(b)] Hvilke (om nogen) af graferne har en \aa{}ben Eulertur? For dem der har en s\aa{}dan, skal du angive en kantr\ae{}kkef\o{}lge som er en \aa{}ben Eulertur i grafen.
\item[(c)] Antag nu, at vi m\aa{} tilf\o{}je nye kanter till de tre grafer, s\aa{} hver af disse nye grafer har en lukket Eulertur. De nye kanter m\aa{} forbinde vilk\aa{}rlige to forskellige punkter ogs\aa{} selvom disse ikke var forbundet i $G_i$. Hvad er det mindste antal nye kanter der skal tilf\o{}jes til hver af graferne $G_1,G_2,G_3$ for at opn\aa{} nye grafer $G^+_i$, $i=1,2,3$, som har en lukket Eulertur?
\item[(d)] Lad nu $G$ v\ae{}re en sammenh\ae{}ngende graf hvor alle valenser er lige, dvs $G$ har en lukket Eulertur. Bevis, at der for vilk\aa{}rlige to forskellige punkter $x$ og $y$ i $G$ g\ae{}lder at $G$ har to veje $P_{x,y}$ og $P_{y,x}$, som begge har endepunkter i $x$ og $y$ (dvs vejene g\aa{}r mellem disse to  punkter) og som ingen f\ae{}lles kanter har.
\iffalse
\item[(d)] Antag at $G$ er en graf hvor alle valenser er lige og som har et 
 punkt $x$  af valens 2, dvs $x$ har pr\ae{}cis 2 kanter $xy,xz$ ind til sig. Argumenter for, at kanterne $xy$ og $xz$ vil komme lige efter hinanden i enhver lukket Eulertur $T$.
\item[(e)] Brug (d) til at bevise, at hvis $G$ er en sammenh\ae{}ngende graf med pr\ae{}cis $2k$ punkter $x_1,x_2,\ldots{},x_{2k}$ af ulige valens (eng: degree), s\aa{} indeholder $G$ $k$ veje $P_1,P_2,\ldots{},P_k$ som ikke har nogen f\ae{}lles kanter (de er kantdisjunkte) og som opfylder at $P_i$ starter i $x_{2i-1}$ og ender i $x_{2i}$. Hint tilf\o{}j nogle nye punkter og kanter s\aa{} der opn\aa{}s en graf med en lukket Eulertur.
\fi
\end{itemize}

\subsection*{Opgave 5}
J\o{}rgen har l\aa{}nt en elbil til den kommende weekend og vil gerne k\o{}re en s\o{}ndagstur. Desv\ae{}re kan han ikke finde ud af at f\aa{} elbilen opladt, s\aa{} han kan ikke k\o{}re l\ae{}ngere end bilen kan k\o{}re p\aa{} en opladning (bilen er fuldt opladt n\aa{}r han l\aa{}ner den). Bilen kan k\o{}re  $20K$ kilometer\footnote{$K$ ikke er vigtig i denne opgave, men blot er med for at g\o{}re tallene i Figur 2. lettere at arbejde med. Da $K$ er betydeligt st\o{}rre end 1, f.eks 25 for en Tesla, kan vi se blot fra afstande indenfor den samme by.} n\aa{}r den starter fuldt opladt. J\o{}rgen, som bor i by $A$, har udvalgt sig 7 mulige byer $B,C,D,E,F,G,H$, som han godt kunne t\ae{}nke sig at bes\o{}ge.

Afstandene (kun de direkte, dvs ikke via andre byer) mellem disse byer er angivet i Figur 2 (som multipla af $K$).
J\o{}rgens problem er nu at finde ud af, hvilke byer blandt de 7 han ville kunne bes\o{}ge og n\aa{} tilbage til sin hjemby, uden at l\o{}be t\o{}r for str\o{}m.
Bem\ae{}rk, at han blot vil vide hvilke af de 7 byer han ville kunne n\aa{} ud til og tilbage igen, ikke hvor mange han ville kunne bes\o{}ge p\aa{} den samme rute!

J\o{}rgen, der ikke er s\aa{} god til at regne, beder derfor sine MM541 studerende om hj\ae{}lp. Her er mange kvikke hoveder og en af dem siger, at det kan klares ved at udregne de korteste veje fra J\o{}rgens by $A$ til alle de andre byer. J\o{}rgen bliver meget glad og beder derfor om forklaring p\aa{} dette.

\begin{itemize}
\item[(a)] Vis, hvordan man udregner de korteste afstande fra byen $A$ til alle de andre ved hj\ae{}lp af Dijkstras algoritme (Rosen side 684). Du skal vise de enkelte skridt i algoritmen (dvs for hver gang et nyt punkt inds\ae{}ttes i m\ae{}ngden $S$.)
\item[(b)] For hvilke af de 7  byer $B,C,D,E,F,G,H$ vil J\o{}rgen kunne bes\o{}ge byen og n\aa{} tilbage til $A$ uden at l\o{}be t\o{}r for str\o{}m?
\item[(c)] Beskriv hvilke byer der ligger p\aa{} den korteste vej fra $A$ til $H$.
\end{itemize}
\begin{figure}[h!]
\begin{center}
\setlength{\unitlength}{0.0006in}
%
\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}(4983,3240)(0,-10)
\put(330,1635){\blacken\ellipse{128}{128}}
\put(330,1635){\ellipse{128}{128}}
\put(1680,2760){\blacken\ellipse{128}{128}}
\put(1680,2760){\ellipse{128}{128}}
\put(1680,1680){\blacken\ellipse{128}{128}}
\put(1680,1680){\ellipse{128}{128}}
\put(1680,510){\blacken\ellipse{128}{128}}
\put(1680,510){\ellipse{128}{128}}
\put(3255,2760){\blacken\ellipse{128}{128}}
\put(3255,2760){\ellipse{128}{128}}
\put(3255,1635){\blacken\ellipse{128}{128}}
\put(3255,1635){\ellipse{128}{128}}
\put(3255,510){\blacken\ellipse{128}{128}}
\put(3255,510){\ellipse{128}{128}}
\put(4560,1635){\blacken\ellipse{128}{128}}
\put(4560,1635){\ellipse{128}{128}}
\path(375,1635)(1680,2760)
\path(375,1635)(1680,2760)
\path(1680,2760)(3255,2760)
\path(1680,2760)(3255,2760)
\path(3300,2760)(4605,1590)
\path(3300,2760)(4605,1590)
\path(330,1635)(1725,1680)
\path(330,1635)(1725,1680)
\path(330,1635)(1725,465)
\path(330,1635)(1725,465)
\path(1680,2760)(1680,1680)
\path(1680,2760)(1680,1680)
\path(1680,1680)(3255,1635)
\path(1680,1680)(3255,1635)
\path(3255,1635)(4560,1635)
\path(3255,1635)(4560,1635)
\path(1680,1680)(3300,2760)
\path(1680,1680)(3300,2760)
\path(1680,1635)(3255,465)
\path(1680,1635)(3255,465)
\path(1725,510)(3255,510)
\path(1725,510)(3255,510)
\path(3255,510)(4560,1635)
\path(3255,510)(4560,1635)
\path(3255,1635)(3255,510)
\path(3255,1635)(3255,510)
\path(3255,2715)(3255,1635)
\path(3255,2715)(3255,1635)
\path(1680,510)(3300,1635)
\path(1680,510)(3300,1635)
\put(15,1635){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}A}}}}
\put(1590,3075){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}B}}}}
\put(3165,3030){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}C}}}}
\put(3210,15){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}G}}}}
\put(4830,1590){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}H}}}}
\put(735,2355){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(1050,1815){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(780,870){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}6}}}}
\put(2445,2985){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}10}}}}
\put(2310,2265){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(1725,2220){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(1410,1365){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}D}}}}
\put(3435,1770){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}F}}}}
\put(2400,1815){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}7}}}}
\put(2040,1095){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}4}}}}
\put(2355,195){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(3345,1140){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(3840,1770){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(3075,2085){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}1}}}}
\put(2310,735){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(4020,825){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}5}}}}
\put(4020,2400){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}2}}}}
\put(1635,15){\makebox(0,0)[lb]{\smash{{\SetFigFont{10}{7.2}{\rmdefault}{\mddefault}{\updefault}E}}}}
\end{picture}
}

\end{center}
\caption{Grafen viser de direkte afstandene mellem de 8 byer i J\o{}rgens problem. Tallene p\aa{} kanterne representerer den direkte afstand mellem det tilsvarende par af byer. Alle afstande er angivet som multipla af $K$, dvs 4 st\aa{}r for $4K$.}
\end{figure}
 
\end{document}





