% 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 1
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ 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 und Physik widmen. Da in der offiziellen Vereinszeitschrift von Mensa \"{O}sterreich, TOPIQ, im Allgemeinen zu wenig Platz f\"{u}r Artikel zu diesen speziellen Themenbereichen ist, gebe ich im Namen der MathSIG nun einen eigenen Newsletter heraus. Nat\"{u}rlich steht es jedem frei, Beitr\"{a}ge sowohl f\"{u}r diesen Newsletter als auch an TOPIQ einzusenden (ich habe selbst vor, das zu tun). Die beiden Publikationen sollen zueinander nicht in Konkurrenz stehen, sondern einander erg\"{a}nzen.
\\
\\ Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in den Beitr\"{a}gen mathematische Sonderzeichen vorkommen, bitte ich aber, zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung die Beitr\"{a}ge 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 Titelbild des Newsletters willkommen. Die Rechte an den Illustrationen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ Ich denke mir, dass es bei Mensa viele Mitglieder gibt, die sich f\"{u}r Mathematik und verwandte Themengebiete interessieren. Die Mitgliederschaft ist in dieser Beziehung sicherlich sehr heterogen. Es gibt Sch\"{u}ler ebenso wie Studierende und Hochschulabsolventen, zum Teil sogar solche, die im Bereich der Mathematik, Informatik oder Physik wissenschaftlich arbeiten, und auch reine Hobbyisten. Nat\"{u}rlich ist MATHEMATIQ kein wissenschaftliches Journal und ist auch nicht in erster Linie dazu gedacht, bahnbrechende wissenschaftliche Erkenntnisse zu publizieren. Aber theoretisch sind auch solche Ver\"{o}ffentlichungen willkommen. Allgemein ist MATHEMATIQ jedoch f\"{u}r all jene in der Mensa gedacht, die an der Mathematik Freude haben und gerne dar\"{u}ber schreiben bzw. sich mit anderen Mathematikbegeisterten austauschen wollen. Es sind also Beitr\"{a}ge auf jedem Niveau, von der Volksschule bis zur Universit\"{a}t und dar\"{u}ber hinaus, willkommen.
\\
\\ In dieser Ausgabe fange ich mit der Logik an, weil das eines meiner Spezialgebiete im Informatikstudium war. Grunds\"{a}tzlich verf\"{u}ge ich \"{u}ber Kenntnisse in vielen f\"{u}r diese SIG relevanten Gebieten und k\"{o}nnte zahlreiche Artikel selbst schreiben. Aber es w\"{a}re trotzdem sch\"{o}ner, auch von anderen Mitgliedern Beitr\"{a}ge zu erhalten.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen/Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Eine Einf\"{u}hrung in die Logik}
\end{center}
\normalsize Schon seit Jahrhunderten besch\"{a}ftigen sich Menschen mit Logik. Die alten Griechen und nach ihnen mittelalterliche Gelehrte versuchten, Listen mit Regeln zu entwickeln, welche logischen Schl\"{u}sse zul\"{a}ssig sind und welche nicht. Das fr\"{u}heste bekannte Beispiel daf\"{u}r sind die Aristotelischen Syllogismen. Die mittelalterlichen Gelehrten griffen das Verm\"{a}chtnis des Aristoteles auf und benannten diese Syllogismen mit Merkworten. Beispielsweise stand ``Modus Barbara'' f\"{u}r einen logischen Schluss der Bauart: ``Wenn alle x y sind und alle y z, dann sind alle x z.''
\\
\\Aus Sicht einer Person, die f\"{u}r das logische Denken begabt ist, muten diese Versuche, Logik in eine Form zu gie\ss{}en, die man auswendig lernen kann, umst\"{a}ndlich an, weil wir in der Lage sind, leicht selbst zu \"{u}berpr\"{u}fen, ob ein Gedankengang wohlgeformt und g\"{u}ltig ist.
\\
\\Ab dem 18. Jahrhundert fing die moderne mathematische Logik an sich zu entwickeln. Pioniere waren unter anderem George Boole (dessen Boolesche Algebra jedem Programmierer ein Begriff sein sollte), Gottlob Frege und Bertrand Russell. Diese ``klassische'' Logik ist inzwischen gut erforscht, aber es gibt daneben auch Erweiterungen, etwa um modale oder temporale Konzepte, sowie alternative Ans\"{a}tze, die mit der klassischen Logik nicht kompatibel sind. Einige von ihnen werde ich in diesem Artikel vorstellen.
\\
\begin{center}
\Large Klassische Aussagenlogik
\end{center}
\normalsize Klassische Aussagenlogik ist die in der Praxis wichtigste Form der Logik. Ihre Sprache gestattet es, Aussagen wie ``Wenn Behauptung A wahr ist und Behauptung B falsch, dann ist Behauptung C wahr'' zu formulieren.
\\
\\In der klassischen Logik ist jede Behauptung entweder wahr oder falsch. Es gibt keine dritte M\"{o}glichkeit. Wenn nicht bekannt ist, ob eine Aussage wahr ist, k\"{o}nnen wir mit ihr nicht arbeiten.
\\
\\Beim Programmieren werden meistens nur Kenntnisse der klassischen Aussagenlogik ben\"{o}tigt. Es gibt verschiedene logische Operatoren, die verwendet werden k\"{o}nnen, um Schl\"{u}sse zu ziehen. Die grundlegendsten sind Negation, Konjunktion und Disjunktion.
\\
\\Es gibt in der Logik verschiedene Notationen. Eine g\"{a}ngige Notation f\"{u}r die Negation ist $\neg a$. Die Semantik ist einfach: Wenn eine Aussage wahr ist, ist ihre Negation falsch, und wenn eine Aussage falsch ist, ist ihre Negation wahr.
\\
\\Konjunktion wird gew\"{o}hnlich als $a \wedge b$ ausgedr\"{u}ckt und Disjunktion als $a \vee b$. Die Semantik der Konjunktion: Das logische Produkt ist genau dann wahr, wenn beide Parameter wahr sind. Die logische Summe der Disjunktion ist im Unterschied dazu genau dann falsch, wenn beide Parameter falsch sind. (Wenn man sagt, eine Aussage $a$ sei genau dann wahr, wenn auch eine Aussage $b$ wahr sei, bedeutet dies: Wenn $a$ wahr ist, ist $b$ wahr, und wenn $b$ wahr ist, ist auch $a$ wahr. Analog verh\"{a}lt es sich, wenn man sagt, eine Aussage $a$ sei genau dann falsch, wenn eine Aussage $b$ wahr sei.)
\\
\\Ein anderer weit verbreiteter Operator ist die Implikation, man schreibt $a \to b$ und meint ``a impliziert b''. Die Bedeutung: Wenn a wahr ist, muss auch b wahr sein. Das impliziert, dass, wenn a falsch ist, der Wert von b entweder wahr oder falsch sein kann. Implikation kann leicht durch Disjunktion und Negation ausgedr\"{u}ckt werden: $a \to b$ ist \"{a}quivalent zu $\neg a \vee b$.
\\
\\Der letzte weit verbreitete Operator ist logische \"{A}quivalenz. Die Aussagen $a$ und $b$ sind zueinander genau dann \"{a}quivalent, wenn entweder beide wahr oder beide falsch sind. Wir werden \"{A}quivalenz durch $a \equiv b$ ausdr\"{u}cken.
\\
\\In der Elektrotechnik werden oft auch die Operatoren NAND und NOR verwendet. Die Bedeutung: $\neg (a \wedge b)$ bzw. $\neg (a \vee b)$. Diese Operatoren sind f\"{u}r die Entwicklung von Schaltkreisen n\"{u}tzlich, weil man Konjunktion, Disjunktion und Negation leicht durch sie ausdr\"{u}cken und man so Produktionskosten sparen kann. Es sei dem geneigten Leser als \"{u}bungsaufgabe \"{u}berlassen herauszufinden, wie Konjunktion, Disjunktion und Negation durch NAND oder NOR ausgedr\"{u}ckt werden k\"{o}nnen.
\\
\\Die Boolesche Algebra kennt auch einige Gesetze, die benutzt werden k\"{o}nnen, um logische Ausdr\"{u}cke umzuwandeln oder zu vereinfachen, beispielsweise die De Morganschen Gesetze $\neg (a \vee b) = \neg a \wedge \neg b$ und $\neg (a \wedge b) = \neg a \vee \neg b$ sowie die Distributivgesetze $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$ und $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$.
\\
\begin{center}
\Large Pr\"{a}dikatenlogik
\end{center}
\normalsize Die ber\"{u}hmte Aussage ``Alle Menschen sind sterblich, Sokrates ist ein Mensch, daher ist Sokrates sterblich'' kann nicht mit Aussagenlogik ausgedr\"{u}ckt werden. Man ben\"{o}tigt eine Erweiterung ihrer Syntax zur Pr\"{a}dikatenlogik erster Ordnung. Wenn man $S$ und $M$ als Pr\"{a}dikate definiert und $k$ f\"{u}r Sokrates steht, kann man im Prinzip schreiben: ``Alle $x$, f\"{u}r die gilt $M(x)$, haben die Eigenschaft $S(x)$, $M(k)$, daher $S(k)$.'' Formal w\"{u}rde man das folgenderma\ss{}en ausdr\"{u}cken:
\\
\\$((\forall x M(x) \to S(x)) \wedge M(k)) \to S(k)$
\\
\\Diese Art zu schlie\ss{}en wird \"{u}brigens auch \textit{modus ponens} genannt. $\forall$ ist hierbei das so genannte Allquantor-Symbol. $\forall x P(x)$ bedeutet: Was auch immer $x$ ist, es gilt $P(x)$. In Analogie dazu bedeutet $\forall x M(x) \to S(x)$: Was auch immer $x$ ist, wenn $M(x)$, dann $S(x)$.
\\
\\Neben dem Allquantor $\forall$ kennt die Pr\"{a}dikatenlogik auch den Existenzquantor $\exists$. $\exists x P(x)$ bedeutet, dass es mindestens ein $x$ gibt, f\"{u}r das $P(x)$ gilt. Die beiden Quantoren stehen miteinander in folgendem Zusammenhang:
\\
\\$\neg \exists x P(x) \equiv \forall x \neg P(x)$
\\$\exists x \neg P(x) \equiv \neg \forall x P(x)$
\\
\\Es gibt neben der Pr\"{a}dikatenlogik erster Ordnung Erweiterungen, die man Pr\"{a}dikatenlogik h\"{o}herer Ordnungen nennt. Die Pr\"{a}dikatenlogik zweiter Ordnung erlaubt es etwa, Pr\"{a}dikate selbst zu quantifizieren. Dadurch wird es m\"{o}glich, Aussagen wie die folgenden zu formulieren:
\\
\\$\exists P P(x) \wedge \neg P(y)$
\\
\\Das bedeutet, dass es ein Pr\"{a}dikat $P$ gibt, f\"{u}r welches gilt $P(x)$, aber nicht $P(y)$.
\\
\begin{center}
\Large Modallogiken
\end{center}
\normalsize Ein fortgeschrittenes Thema der Logik sind die Modallogiken. Ich verwende die Mehrzahl, weil es viele Arten davon gibt. Allen ist gemeinsam, dass sie von M\"{o}glichkeiten handeln, und die meisten werden durch die Kripke-Semantik definiert. Die Kripke-Semantik geht davon aus, dass es verschiedene Welten gibt. Da Modallogiken Erweiterungen der klassischen Logik sind, kann jede Formel der klassischen Logik auch in einer Modallogik verwendet werden. Schreibt man die Formel nur so hin, bedeutet dies, dass die Aussage sich auf die aktuelle Welt bezieht. Schreibt man hingegen eine Aussage der Form $\Diamond P(x)$, so bedeutet dies, dass $P(x)$ m\"{o}glich ist, das hei\ss{}t, es gibt einen \"{U}bergang von der aktuellen Welt zu einer anderen Welt, in der $P(x)$ g\"{u}ltig ist. Man kann auch sagen, die aktuelle Welt stehe mit einer anderen Welt, in der die genannte Formel g\"{u}ltig ist, in Beziehung (Relation).
\\
\\ Ferner gibt es den Operator $\Box$: $\Box P(x)$ hat die Bedeutung, dass es keinen \"{U}bergang von der aktuellen Welt zu einer anderen Welt gibt, in der P(x) ung\"{u}ltig ist, P(x) ist also in allen Welten, zu denen es einen \"{U}bergang von der aktuellen Welt gibt, g\"{u}ltig. Die beiden Operatoren stehen zueinander in folgender Beziehung:
\\
\\$\Diamond P(x) \equiv \neg \Box \neg P(x)$
\\$\neg \Diamond \neg P(x) \equiv \Box P(x)$
\\
\begin{center}
\Large Intuitionistische Logiken
\end{center}
\normalsize Intuitionistische Logiken stellen eine Alternative zur klassischen Logik dar, die zu dieser \textit{nicht} kompatibel ist. Der Unterschied: W\"{a}hrend in der klassischen Logik die Formel $x$ bedeutet, dass die Aussage $x$ wahr ist, und die Formel $\neg x$, dass die Aussage $x$ falsch ist, bedeutet die Formel $x$ in intuitionistischer Logik, dass die Aussage $x$ beweisbar ist, und die Formel $\neg x$, dass die Aussage $x$ widerlegbar ist. Dies hat zur Folge, dass das in der klassischen Logik g\"{u}ltige Prinzip ``tertium non datur'', dass $x \vee \neg x$ immer wahr ist, in der intuitionistischen Logik nicht gilt. Wenn man $x$ nicht beweisen kann, reicht das nicht aus, um daraus zu schlie\ss{}en, dass $x$ widerlegt werden kann, und wenn man $x$ nicht widerlegen kann, reicht das nicht aus, um daraus zu schlie\ss{}en, dass $x$ bewiesen werden kann. Dies macht das Rechnen mit den intuitionistischen Logiken sehr verschieden von der klassischen Logik. Einige Formeln, die in der klassischen Logik g\"{u}ltig sind, sind in den intuitionistischen Logiken nicht beweisbar. Wieder verwende ich den Plural, weil es verschiedene Arten von intuitionistischer Logik gibt, wie etwa intuitionistische Modallogiken.
\\
\begin{center}
\Large Weitere Logiken
\end{center}
\normalsize Es gibt noch viele weitere Arten von Logiken, zum Beispiel temporale, substrukturale oder mehrwertige Logiken. Ein Beispiel f\"{u}r mehrwertige Logiken ist die ber\"{u}hmte Fuzzy-Logik. In diesen Logiken gibt es nicht nur die Wahrheitswerte wahr und falsch, sondern viele verschiedene Wahrheitswerte. Dies macht das Rechnen deutlich schwieriger.
\\
\begin{center}
\Large Summa summarum
\end{center}
\normalsize Ich hoffe, mit diesem Artikel einen kleinen Einblick in die mathematische Logik gegeben zu haben. Zur Erweiterung des Wissens \"{u}ber Logik empfiehlt sich der Besuch von einschl\"{a}gigen Lehrveranstaltungen an den Universit\"{a}ten, zum Beispiel von der Vorlesung \textit{Logic and Computability} an der TU Wien.
\\
\begin{center}
\Large Habt ihr es verstanden?
\end{center}
\normalsize Zum Schluss noch eine \"{U}bungsaufgabe, mit der der geneigte Leser testen kann, ob er den Inhalt dieses Artikels begriffen hat. Es geht um die Modallogik: Man zeige, dass die Formel $A \to \Box \Diamond A$ symmetrische Beziehungen charakterisiert, das sind Beziehungen $R$, f\"{u}r die gilt, dass eine Welt $w$ genau dann mit einer Welt $v$ in Beziehung $R$ steht, wenn auch $v$ mit $w$ in Beziehung $R$ steht. Den Sachverhalt, dass eine Welt $w$ mit einer anderen Welt $v$ in Beziehung $R$ steht, kann man kurz durch $R(w, v)$ ausdr\"{u}cken.
\\
\\ Zwei der L\"{o}sung dienliche Hinweise: Erstens: Man stelle sich $w$ und $v$ als zwei m\"{o}gliche Welten vor, wobei in Welt $w$ die Formel $A$ g\"{u}ltig ist. Zweitens: Dass eine Formel einen bestimmten Sachverhalt charakterisiert, bedeutet, dass diese Formel genau dann g\"{u}ltig ist, wenn dieser Sachverhalt vorliegt. 
\\
\\ Viel Spa\ss{} beim Knobeln - und nicht traurig sein, wenn es schwerf\"{a}llt: Das ist immerhin eine \"{U}bungsaufgabe auf dem Niveau der TU Wien (Masterstudium Computational Intelligence) und kein IQ-Test.
\\
\begin{center}
\Large L\"{o}sung
\end{center}
\normalsize
\begin{enumerate}
\item Die Formel $A \to \Box \Diamond A$ bedeutet: Wenn in einer Welt $w$ die Formel $A$ gilt, dann gilt in jeder Welt $v$ die Formel $\Diamond A$, wenn $w$ mit $v$ in Beziehung $R$ steht, und wenn in $v$ die Formel $\Diamond A$ gilt, gibt es eine Welt $u$, in der die Formel $A$ gilt, so dass $v$ mit $u$ in Beziehung $R$ steht. Es gilt also $R(w, v)$ und $R(v, u)$. Wenn wir $w$ mit $u$ gleichsetzen, ist die Beziehung $R$ symmetrisch und die modallogische Formel $A \to \Box \Diamond A$ erf\"{u}llt, ergo ist in jeder symmetrischen Beziehung die Formel $A \to \Box \Diamond A$ g\"{u}ltig.
\item Die andere Richtung kann indirekt bewiesen werden, indem man zeigt, dass in dem Fall, dass eine Beziehung nicht symmetrisch ist, die Formel $A \to \Box \Diamond A$ nicht erf\"{u}llt wird. Wie gesagt, gilt $R(w, v)$ und $R(v, u)$. Wenn die Beziehung nicht symmetrisch ist, m\"{u}ssen $w$ und $u$ verschieden sein. Entweder gibt es also keine Welt $u$, in der die Formel $A$ gilt, so dass eine andere Welt $v$ mit ihr in Beziehung $R$ steht; in diesem Fall ist die modallogische Formel $A \to \Box \Diamond A$ nicht erf\"{u}llt. Oder aber es gibt ein solches $u$, aber es ist von $w$ verschieden. In diesem Fall gibt es aber eine Welt $v'$, zu der $u$ in Beziehung $R$ steht, usw. Letzten Endes muss es also ein Knotenpaar $w_i, v_i$ geben, f\"{u}r das sowohl $R(w_i, v_i)$ als auch $R(v_i, w_i)$ gilt, sonst kann die Formel $A \to \Box \Diamond A$ nicht erf\"{u}llt werden. (Zur Veranschaulichung dieses Arguments: Wenn man einer Schlange erlaubt, pl\"{o}tzlich grenzenlos zu wachsen, dann wird sie sich zwangsl\"{a}ufig in den eigenen Schwanz bei\ss{}en. Denn das Universum ist zu jedem Zeitpunkt endlich.) Daher ist jede Beziehung, die $A \to \Box \Diamond A$ erf\"{u}llt, symmetrisch.
\end{enumerate}
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Summationsformeln}
\end{center}
\normalsize Vielen wird wahrscheinlich die folgende Formel aus der Schule bekannt sein:
\\
\\ $\sum_{i=1}^{n} i = (n + 1) n / 2$.
\\
\\ Vor einiger Zeit bin ich darauf gekommen, dass analog dazu auch folgende Gesetze gelten:
\\
\\ $\sum_{i=1}^{n} i (i - 1) = (n + 1) n (n - 1) / 3$,
\\ $\sum_{i=1}^{n} i (i - 1) (i - 2) = (n + 1) n (n - 1) (n - 2) / 4$.
\\
\\ Ich fragte mich daher, ob auch die allgemeine Form
\\
\\ $\sum_{i=1}^{n} \prod_{j=0}^{k - 1} i - j = (\prod_{j=0}^{k} n + 1 - j) / (k + 1)$
\\
\\ g\"{u}ltig sei und, wenn ja, wie man dies beweisen k\"{o}nnte. Ich wurde dann auf die Differenzenrechnung (engl. \textit{finite calculus}) aufmerksam gemacht, mit der sich diese Formel leicht herleiten l\"{a}sst.
\\
\\ Es gilt:
\\
\\ $\Delta f(x) = f(x + 1) - f(x)$.
\\
\\ In der Differenzenrechnung kann analog zur Differentialrechnung gerechnet werden, wobei folgendes Gesetz gilt:
\\
\\ $\Delta x^{\underline{m}} = m x^{\underline{m - 1}}$.
\\
\\ (Erinnert doch sehr an die Differentialrechnung, oder?) Dabei ist die Bedeutung der Notation $x^{\underline{m}}$ die folgende:
\\
\\ $x^{\underline{m}} = \prod_{i=0}^{m - 1} x - i$.
\\
\\ Nun ist nat\"{u}rlich
\\
\\ $\sum_{i=1}^{n} \Delta f(i) = f(n + 1) - f(1)$.
\\
\\ Wenn wir also
\\
\\ $f(x) = \prod_{j=0}^{k - 1} x - j = x^{\underline{k}}$
\\
\\ setzen, so gilt, da in diesem Fall $f(1) = 0$,
\\
\\ $f(n + 1) - f(1) = f(n + 1) = (n + 1)^{\underline{k}} = \sum_{i=1}^{n} \Delta x^{\underline{k}} = \sum_{i=1}^{n} k x^{\underline{k - 1}}$.
\\
\\ Daraus folgt:
\\
\\ $(n + 1)^{\underline{k}} = k \sum_{i=1}^{n} x^{\underline{k - 1}}$
\\
\\ oder eben
\\
\\ $\sum_{i=1}^{n} x^{\underline{k - 1}} = (n + 1)^{\underline{k}} / k$,
\\
\\ was zu beweisen war. (Von der anfangs genannten, zu beweisenden Formel unterscheidet sich diese Formulierung nur dadurch, dass die Kurzschreibweise $x^{\underline{m}}$ verwendet und mit $k - 1$ statt $k$, ergo also auch mit $k$ statt $k + 1$ gerechnet wurde - von der Bedeutung her sind die beiden Formeln identisch.)
\\
\\ Zu einem vertiefenden Einstieg in dieses Thema empfiehlt sich das Skriptum von David Gleich (damals Stanford, inzwischen Purdue University):
\\ \url{http://www.stanford.edu/~dgleich/publications/finite-calculus.pdf}
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Zu guter Letzt}
\end{center}
\normalsize Meine Diplomarbeit ist fertig und kann auf der Homepage des Arbeitsbereichs f\"{u}r Algorithmen und Datenstrukturen des Instituts f\"{u}r Computergrafik und Algorithmen der TU Wien eingesehen werden. Das Thema ist das Selective Graph Coloring Problem, ein graphentheoretisches Problem, f\"{u}r das ich einen L\"{o}sungsalgorithmus entwickelt und analysiert habe.
\\ \url{https://www.ads.tuwien.ac.at/}
\\
\\ Mit der Graphentheorie zusammenh\"{a}ngend, habe ich mich auch mit der Frage besch\"{a}ftigt, ob es einen eleganteren Beweis f\"{u}r den Vier-Farben-Satz geben k\"{o}nnte als diejenigen, die bisher bekannt sind. Mein momentaner Denkansatz: Es ist bekannt, dass jeder vollst\"{a}ndige Graph $K_n$ mit $n \leq 4$ planar und kein $K_n$ mit $n \geq 5$ planar ist. Sicher ist es kein Zufall, dass die Grenze gerade 4 betr\"{a}gt. Ich schlage folgenden Algorithmus vor, um einen Graphen zu einem $K_n$ mit derselben chromatischen Zahl zu reduzieren: Finde zuerst eine minimale(!) F\"{a}rbung des Graphen; vereinige dann Schritt f\"{u}r Schritt alle mit der gleichen Farbe gef\"{a}rbten Knoten, ohne etwas an der Planarit\"{a}t oder Nichtplanarit\"{a}t des Graphen zu \"{a}ndern. Wenn dabei ein $K_n$ mit $n \geq 5$ herauskommt, bedeutet dies, dass der Ursprungsgraph eine chromatische Zahl von 5 oder h\"{o}her hatte. Wenn in jedem Reduktionsschritt die Planarit\"{a}t oder Nichtplanarit\"{a}t des Graphen gewahrt blieb, so muss der Ursprungsgraph ebenfalls nichtplanar gewesen sein. Daher k\"{o}nnen nur planare Graphen zu einem $K_n$ mit $n \leq 4$ reduziert werden, wenn die Planarit\"{a}t oder Nichtplanarit\"{a}t in jedem Schritt erhalten bleibt. Bewiesen werden muss also, dass es f\"{u}r jeden planaren Graphen einen Ausf\"{u}hrungspfad dieses Algorithmus gibt, in dem die Planarit\"{a}t gewahrt bleibt. Zugegeben: Vielleicht ist gerade das schwierig zu beweisen.
\\
\\ Au\ss{}erdem w\"{a}re ich pers\"{o}nlich nat\"{u}rlich sehr an der L\"{o}sung des $\P$-$\NP$-Problems interessiert (siehe TOPIQ 365). $\ddot\smile$
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}

