\documentclass[12pt]{article}
\usepackage{epsf}
\usepackage[german]{babel}
\usepackage{a4wide}
\usepackage{amssymb}

\usepackage{ueb}

\begin{document}
\blatt{1}{23.04.2001}{03.05.2001}

\letztenummer{0}

Abbildung~\ref{fi:TSP10.ohne} zeigt zehn St"adte im Mittleren Westen der USA:

\begin{figure}[htbp]
\begin{center}
\epsfxsize=.6\textwidth
\ \epsfbox{TSP10.eps}
\caption{Zehn St\"adte im Mittleren Westen}
\label{fi:TSP10.ohne}
\end{center}
\end{figure}

Zwischen je zwei dieser St"adte gibt es eine direkte 
Stra"senverbindung. Die L"ange 
einer Verbindungskante $e$ bezeichnen wir mit $w_e$. Die Werte
(auf Vielfache von 10 Meilen gerundet)
sind die folgenden:

\bigskip
\begin{center}
\begin{tabular}{|l|l||r|r|r|r|r|r|r|r|r||}\hline
   & & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \hline
1 & Chicago       & 92 & 99 & 50 & 41 & 79 & 46 & 29 & 50 & 70 \\
2 & Dallas        &    & 78 & 49 & 94 & 21 & 64 & 63 & 42 & 37 \\
3 & Denver        &    &    & 60 & 84 & 61 & 54 & 86 & 76 & 51 \\
4 & Kansas City   &    &    &    & 45 & 35 & 20 & 26 & 17 & 20 \\
5 & Minneapolis   &    &    &    &    & 80 & 36 & 55 & 59 & 64 \\
6 & Oklahoma City &    &    &    &    &    & 46 & 50 & 29 & 16 \\
7 & Omaha         &    &    &    &    &    &    & 45 & 37 & 30 \\
8 & St.\ Louis    &    &    &    &    &    &    &    & 21 & 45 \\
9 & Springfield   &    &    &    &    &    &    &    &    & 25 \\
10& Wichita       &    &    &    &    &    &    &    &    &    \\
\hline
\end{tabular}
\end{center}

\newpage
Nun sollen f"ur die Aufgaben $i=1,2,3,4$
verschiedene Optimierungsprobleme m"oglichst gut gel"ost werden,
indem man jeweils eine geeignete Menge von Verbindungen $E_i$ ausw"ahlt.
Den Wert irgendeiner gefundenen L"osung f"ur Aufgabe $i$
bezeichnen wir mit $L_i$. In allen F"allen wird es darum gehen,
eine m"oglichst kleine Gesamtl"ange $L_i=\sum_{e\in E_i} w_e$ zu erzielen. 
%Als ``Zertifikat'' der Erreichbarkeit eines Wertes hat man also eine
%L"osung mit diesem Wert anzugeben.
%Der beste erreichbare Wert sei $L^{*}_i$.

Au"serdem soll jeweils eine m"oglichst gute untere Absch"atzung
f"ur den besten erreichbaren Wert $L^*_i$ bewiesen werden. 
Der Wert einer solchen unteren Schranke sei jeweils $S_i$. 
(Im Idealfall hat man $S_i=L_i$ und damit die Optimalit"at des
Wertes $L_i$ bewiesen, aber das kann unter Umst"anden
 schwer zu bewerkstelligen sein!)

\bigskip
\aufgabe{K"urzestes zusammenh"angendes Netzwerk} 

\noindent
Finden Sie eine Netzwerk $G_1$ m"oglichst kurzer Gesamtl"ange, 
in dem jeder Knoten von jedem anderen erreicht werden kann!


%\aufgabe{K"urzeste Wege}
%
%\noindent
%Finden Sie ein f"ur Verbindungen von Chicago m"oglichst sparsames Netzwerk:
%Die Summe der Abst"ande zu allen anderen St"adten soll minimal sein,
%mit Zusatzkosten von 10 Einheiten pro benutzter Kante.
%
%Wert einer L"osung: $L_2=10\cdot |E_2| + \sum_{v_j\in V} d_{G_2}(v_1,v_j)$.

\bigskip
\aufgabe{K"urzeste Knotenpaarung}

\noindent
Gruppieren Sie die St"adte in f"unf Paare, so dass die 
Summe der zugeh"origen f"unf Abst"ande m"oglichst klein ist!

\bigskip
\aufgabe{K"urzeste 2-Paarung}

Bestimmen Sie eine m"oglichst kurze Menge von Kanten, so dass
jede Stadt genau zwei Nachbarn hat!

\bigskip
\aufgabe{K"urzeste Rundreise}

\noindent
Finden Sie eine m"oglichst kurze Rundreise, die nach dem Besuch aller
zehn St"adte zum Ausgangspunkt zur"uckkehrt!

\bigskip
\bigskip
Die Gesamtpunktzahl f"ur alle vier Aufgaben ergibt sich zu
$$\mathbf{15\cdot\sum_{i=1}^4 S_i/L_i}\mbox{\bf \ Punkten}.$$
(Maximal sind also 60 Punkte erreichbar. Ohne den Beweis einer unteren Schranke f"ur eine Aufgabe $i$ wird $S_i=0$
angesetzt; ohne eine g"ultige L"osung wird $L_i=\infty$ angesetzt.)


\end{document}
