% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 15
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die f\"{u}nfzehnte Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Hinweis: Autoren sind f\"{u}r den Inhalt ihrer Artikel oder Werke selbst verantwortlich. Die in MATHEMATIQ ver\"{o}ffentlichten Beitr\"{a}ge widerspiegeln ausschlie\ss{}lich die Meinung ihrer Autoren und nicht jene des Vereins Mensa. Die Zusendung von Beitr\"{a}gen gilt auch als Einverst\"{a}ndnis zu deren Ver\"{o}ffentlichung in MATHEMATIQ.}
\\
\\ \textbf{Diese Ausgabe} befasst sich mit einem Problem aus der Graphentheorie.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Snarks}
\end{center}
\normalsize Ab und zu schaue ich mir an, welche Diplomarbeiten an der Fakult\"{a}t, an der ich studiert habe, ausgeschrieben sind, weil mich interessiert, woran geforscht wird - auch wenn meine eigene Diplomarbeit schon l\"{a}ngst abgeschlossen ist. Ein Thema, das ich sehr interessant finde, ist das Thema Snarks. Dabei handelt es sich um eine spezielle Art von Graphen, n\"{a}mlich um solche, bei denen jeder Knoten mit genau drei anderen Knoten verbunden ist und die nicht mit drei, sondern erst mit vier Farben f\"{a}rbbar sind. Das hei\ss{}t, dass zwei einander benachbarte Knoten nicht die gleiche Farbe zugewiesen bekommen d\"{u}rfen, und wenn man dies tut, dann sind mindestens vier Farben erforderlich, um den Graphen zu f\"{a}rben. Auch in meiner eigenen Diplomarbeit habe ich mich mit Graphenf\"{a}rbung besch\"{a}ftigt; in diesem Diplomarbeitsthema geht es nun darum, ein Programm zu schreiben, das s\"{a}mtliche Snarks mit 39 bis 46 Knoten findet (denn die Snarks mit 38 oder weniger Knoten sind angeblich bereits alle bekannt). Prinzipiell kein besonders schwieriges Thema f\"{u}r einen begabten Algorithmiker, allerdings k\"{o}nnte es durchaus eine Herausforderung zu sein, nicht nur einen Algorithmus zu entwickeln und zu implementieren, der dieses Problem grunds\"{a}tzlich l\"{o}st, sondern einen, der m\"{o}glichst schnell (und dennoch pr\"{a}zise) arbeitet.
\\
\\ Interessant ist, dass ein Mathematiker bereits im 19. Jahrhundert bewiesen hat, dass aus der Nichtexistenz planarer Snarks der Vier-Farben-Satz folgt. Da sich der Beweis letzteren Satzes sehr aufw\"{a}ndig gestaltete, ist auch anzunehmen, dass es nicht ganz so einfach ist, einen wirklich \textit{effizienten} Algorithmus zum Auffinden neuer Snarks zu entwickeln - also einen Algorithmus, der nicht nur alle M\"{o}glichkeiten durchprobiert, sondern schon von vornherein m\"{o}glichst viele Graphen ausschlie\ss{}t (also feststellt, dass es sich bei ihnen nicht um Snarks handelt). Was die Komplexit\"{a}t des Problems betrifft: Jeder der $n$ Knoten muss mit genau drei anderen Knoten verbunden sein. Wir m\"{u}ssen also pro Knoten ${n - 1 \choose 3}$ M\"{o}glichkeiten ausprobieren. Und das pro Knoten! Da aber durch die Wahl der drei Nachbarknoten automatisch auch drei Knoten jeweils einen Nachbarknoten zugewiesen bekommen haben, betr\"{a}gt der L\"{o}sungsraum daher $n / 3 * {n - 1 \choose 3}$. Ob und wie sehr man den tats\"{a}chlichen Suchraum begrenzen kann - ja, das erfordert Hirnarbeit. Die Gr\"{o}\ss{}e des L\"{o}sungsraums verh\"{a}lt sich jedenfalls in Bezug auf die Gr\"{o}\ss{}e der Eingabedaten exponentiell. Die L\"{o}sung des derart simpel formulierten Problems erfordert also einen enormen Rechenaufwand.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Uhrzeigersinn und Kr\"{u}mmung}
\end{center}
\normalsize Es war in der ersten Vorlesungseinheit Physik f\"{u}r Mediziner im Wintersemester 2001. Ich hatte damals mit meinem Medizinstudium gerade angefangen und sah einer ungewissen Zukunft entgegen, denn ich war ein mathematischer Typ, der gerne logisch dachte, aber im Medizinstudium ging es ja vor allem ums Auswendiglernen - w\"{u}rde ich das schaffen? Jedenfalls war die Physikvorlesung noch eine der wenigen eher mathematisch orientierten Vorlesungen im Medizinstudium - f\"{u}r viele Studienkollegen von mir eine Qual, aber mir hat sie gefallen.
\\
\\ Nun war es so, dass der Professor uns erkl\"{a}ren wollte, warum man eine Drehung gegen den Uhrzeigersinn als mathematisch positiv bezeichnet. Er begr\"{u}ndete das mit der Erdrotation, die Erde drehe sich ja auch gegen den Uhrzeigersinn. Als er dies erkl\"{a}rte, murmelte ich vor mich hin: ``Das kann man auch mit der Differentialrechnung erkl\"{a}ren.'' Da ich zuf\"{a}lligerweise in der ersten Reihe sa\ss{}, h\"{o}rte dies der Professor - und seine Neugierde war geweckt. Er bat mich, ihm es zu erkl\"{a}ren. Also sagte ich: ``Gut, dann zeichnen Sie eine U-f\"{o}rmige Parabel auf.'' Er tat es, und ich erkl\"{a}rte: ``Der Bogen dieser Parabel ist gegen den Uhrzeigersinn gekr\"{u}mmt. Wenn man die zweite Ableitung der zugrundeliegenden mathematischen Funktion berechnet, dann wird man feststellen, dass sich eine Konstante gr\"{o}\ss{}er Null, also eine positive Konstante, ergibt. Deswegen nennt man eine Drehung gegen den Uhrzeigersinn mathematisch positiv.'' Der Professor hielt, die Kreide in der Hand, kurz inne, dachte nach - und meinte dann: ``Stimmt. Sie haben Recht. Aber das mit der Erdrotation merkt man sich leichter.''
\\
\\ So fiel ich gleich in der ersten Vorlesung einem meiner Professoren auf. Das sollte auch nicht das letzte Mal gewesen sein.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
