Diskrete Mathematik

Die Diskrete Mathematik ist als eigenes Gebiet der Mathematik noch relativ jung. Sie beschäftigt sich vornehmlich mit endlichen Mengen und hierbei stellt sich die Kombinatorik als eines der großen Teile der Diskreten Mathematik heraus. Sie beschäftigt sich mit den Ideen und Methoden des Abzählens. Beispielsweise spielt die Frage von Anzahlproblemen hier eine große Rolle. Die wohl wichtigste Variante hierbei ist das so genannte "Urnenproblem", bei dem eine Urne mit n Kugeln vorgegeben ist, die verschiedene Merkmale (z.B. Farben: rot/weiß) haben, aus der k Kugeln gezogen werden sollen. Nun dreht es sich um die Frage wieviele der Kugeln, die man gezogen hat, das gewünschte Merkmal (z.B. rot) tragen. Bei diesem Problem müssen vier verschiedene Fälle diskutiert werden, die den vier Möglichkeiten entsprechen dieses Experiment durchzuführen. Man kann die gezogenen Kugeln sofort wieder in die Urne zurücklegen oder nicht, was uns bereits zu zwei verschiedenen Fällen führt. Außerdem kann man auf die Reihenfolge der gezogenen Kugeln achten oder nicht, und landet somit bei vier Fällen. Bei der Ziehung der Lottozahlen beispielsweise werden 6 aus 49 Kugeln gezogen (also n=49, k=6), wobei die bereits gezogenen Kugeln nicht zurückgelegt werden und die Reihenfolge der Ziehung egal ist. Insgesamt gibt es hier 13.983.816 verschiedene Varianten. Bei der überlegung, der Anzahl der möglichen Telefonnummern ist n = 10 (die Zahlen 0 bis 9) und man kann gleiche Zahlen mehrmals in einer Telefonnummer haben. Auch ist diesmal im Gegensatz zum Lotto die Reihenfolge wichtig. Setzt man k = 7 (man betrachtet also siebenstellige Telefonnummern), so gibt es 10 hoch 7 = 10.000.000 Möglichkeiten.
Ein weiteres wichtiges Teilgebiet der Diskreten Mathematik ist die Graphentheorie. Sie ist besonders hilfreich beim Lösen von Optimierungsaufgaben, wie beispielsweise dem "Traveling Salesman Problem" (Problem des Handlungsreisenden), wo es darum geht, die optimale Route zu bestimmen, so dass der Handlungsreisende alle Zielorte erreicht, aber der Weg so minimal wie möglich gehalten wird. Auch eines der berühmtesten Probleme der Mathematik überhaupt, das "Vier-Farben-Problem", entspringt der Graphentheorie. Die Frage hier lautet: "Ist es möglich, jede beliebige Landkarte mit nur vier Farben so zu färben, dass keine zwei aneinander grenzenden Gebiete die gleiche Farbe haben?" Bereits 1853 stellte F. Guthrie erstmals diese Frage, jedoch dauerte es bis 1976, als K. Appel und W. Haken gelang sie mit einem Beweis positiv zu beantworten.
Im Zusammenhang mit der Graphentheorie bilden Algorithmen einen wichtigen Aspekt der Untersuchungen. Ein Ziel ist es durch Graphen als zugrunde liegender Struktur gute Algorithmen zu konstruieren, etwa um Optimierungsaufgaben zu lösen, wie z.B. die Optimierung des Verkehrsflusses.

Eugen Netto	Alfred Kempe	Percy Heawood	Kazimierz Kuratowski	Karl Menger

Wie bereits oben erwähnt, ist die Diskrete Mathematik als eigenständiges Teilgebiet der Mathematik noch relativ jung. Das erste Lehrbuch in deutscher Sprache zur Kombinatorik erschien 1901 von E. Netto (1848-1919). Ebenfalls 1901 erschien das Buch Choice and Chance von Whitworth, in welchem die Abzählung von Strukturen unter Nebenbedingungen (heutzutage als Konfigurationen geläufig) wie Permutationen oder Kombinationen im Mittelpunkt steht. Schon in dem Titel ist der enge Zusammenhang der damaligen Kombinatorik zur Wahrscheinlichkeitstheorie zu erkennen.
Ein neuer Gesichtspunkt, die Existenz von Konfigurationen, rückte in den 20er Jahren in den Fokus der Diskreten Mathematik. Die ersten bedeutenden Ergebnisse in diesem Gebiet wurden von Algebraikern wie B. van der Waerden (1903-1996) oder P. Hall (1904-1982), Logikern wie F. Ramsey (1903-1930) und Topologen wie K. Kuratowski (1896-1980) oder K. Menger (1902-1985) erzielt, was die Verbindung dieses Gebiets zur abstrakten Algebra verdeutlicht.
Eine weitere, das Gebiet der Kombinatorik revolutionierende Entwicklung, war die Frage nach "optimalen" Konfigurationen, welche sich z.B. im oben bereits erwähnten "Traveling Salesman Problem" stellt. Das Problem wurde 1930 erstmals von K. Menger unter dem Titel "Botenproblem" gestellt und beeinflusste die Entwicklung der Optimierungsaufgaben zu Beginn der 40er Jahre wesentlich. Dies ging einher mit der Entwicklung der ersten Computer, welche gerade bei Abzählfragen durch ihre immer größeren Kapazitäten als wesentliche Hilfe eingesetzt werden konnten.

Frank Ramsey	Bartel van der Waerden	Philip Hall	Hassler Whitney	William Tutte

Die Entwicklung der Graphentheorie war bis etwa 1930 durch das Bemühen um eine Lösung des "Vier-Farben-Problems" gekennzeichnet. Die eigentliche Graphentheorie entstand in den 30er Jahren, wobei H.Whitney (1907-1989) eine wesentliche Rolle spielte. Sowohl in der Theorie, als auch in den Anwendungen nahm die Graphentheorie in den 50er und 60er Jahren, besonders durch W.T. Tutte (1917-2002), einen großen Aufschwung. In dieser Zeit gelang es den Mathematikern einen Großteil der Optimierungsaufgaben zu formulieren und auch zu lösen. In der Gegenwart spielt die Graphentheorie eine bedeutende Rolle bei Datenstrukturen und algorithmischen Beschreibungen diskreter Phänomene.
Der Höhepunkt war jedoch die Lösung des "Vier-Farben-Problems". 1876 wurde von dem englische Rechtsanwalt A. Kempe (1849-1922) die erste Lösung des Problems vorgestellt, welche jedoch 1890 von P. Heawood (1861-1955) als fehlerhaft erkannt wurde. Er konnte jedoch beweisen, dass die Aussage für fünf Farben stimmt. Zur Lösung des eigentlichen "Vier-Farben-Problems" wurden seit den 30er Jahren unzählige Ansätze zu Lösungen entwickelt, jedoch alle ohne Erfolg. Es dauerte dann, wie oben bereits erwähnt, noch einige Zeit, bis, mit Hilfe von neusten Hochgeschwindigkeitsrechnern aus dem "Vier-Farben-Problem" der "Vier-Farben-Satz" wurde.

Interview mit Prof. Aigner

Beschreiben Sie bitte kurz das Gebiet der Diskreten Mathematik.
Die Diskrete Mathematik beschäftigt sich mit endlichen Mengen, besser gesagt mit endlichen Konfigurationen. Im Wesentlichen gibt es drei Gesichtspunkte. Als ersten Punkt die abzählende Kombinatorik, z.B. Binomialkoeffizienten. Außerdem beschäftigt sie sich mit der Frage, ob gewisse Konfigurationen existieren und wie sie zu konstruieren sind. Als Beispiel kann man die Frage nehmen, wie man einen Code konfiguriert, damit er das leistet, was man gerne möchte. Der dritte Punkt der Diskreten Mathematik ist die Bereitstellung von Datenstrukturen, wie z.B. Graphen oder Bäumen und die Analyse von Algorithmen. Enge Verbindungen der Diskreten Mathematik gibt es zur theoretischen Informatik.

Wie sind Sie zu diesem Gebiet gekommen?
Wie es oftmals ist, bin ich durch große Persönlichkeiten zur Diskreten Mathematik gekommen. Nach meinem Studium bin ich für fünf Jahre in die USA gegangen und habe dort einige berühmte Kombinatoriker kennen gelernt. Mein Vorbild, wenn man so will Mentor, Gian-Carlo Rota hat mich zu diesem Gebiet gebracht.

Was fasziniert Sie an diesem Gebiet?
Diese Frage ist nicht einfach zu beantworten. Insbesondere zur Kombinatorik finden oftmals sogar sehr begabte Leute schwer einen Zugang. Bei mir war am Anfang die abzählende Kombinatorik das Faszinierendste mit ihren Formeln und Strukturen. Durch schöne Codes oder Algorithmen gibt es auch eine sehr ästhetische Komponente.

Wo liegen die Anwendungsmöglichkeiten in Ihrem Gebiet?
Anwendungen liegen besonders in der Codierung, Kryptographie und in der kombinatorischen Optimierung. Ohne diese beiden Gebiete könnten wir heute wohl keinen Tag mehr leben. In der Codierungstheorie gibt es zwei Aspekte: Zum einen die Korrektur von Fehlern (z.B. bei der übertragung von Bildern von Weltraumsonden oder auf CDs), zum anderen die Geheimhaltung (so ziemlich jede Bank benutzt das RSA-System, welches auch bei uns in der Vorlesung behandelt wird).

Was gibt es für Aussichten (Berufschancen)?
Derzeit sind die Breufschancen ausgesprochen gut. In Berlin gibt es da z.B. das ZIB mit einer Abteilung, welche die gesamte Palette der Diskreten Mathematik bearbeitet. Hier wurden beispielsweise die Routen für Telebusse optimiert, was zu großen Geldeinsparungen geführt hat. Aussichten gibt es auch im Bereich der Telekommunikation, Kryptographie oder auch der Unternehmensberatung.

Woran arbeiten Sie zurzeit?
Angenehmerweise hatte ich gerade ein Freisemester, in welchem ich zwei Neuauflagen meiner Bücher "Diskrete Mathematik" und "Das Buch der Beweise" in Zusammenarbeit mit Prof. Ziegler (dt. & engl.) herausgebracht habe. Ansonsten schreibe ich zurzeit Artikel für Fachzeitschriften und arbeite im Umfeld des Vier-Farben-Problems.

Wie lange arbeiten Sie so an einem Problem?
Bis ich es gelöst habe. Jetzt sitze ich z.B. seit vier Monaten an einem Problem und habe sicherlich schon 17 Anläufe genommen, aber irgendwann werde ich es hoffentlich lösen. Das ist ja auch das Besondere an der Mathematik, dass man sehr hartnäckig wird, man will es einfach wissen.

Gab es ein besonderes Ereignis für Sie auf diesem Gebiet?
Als ich mein erstes Buch in den USA "Combinational Theory" schrieb war ich noch sehr jung. Es wurde zu einem großen Erfolg und wird auch heute nach 25 Jahren noch aufgelegt. Nachdem dann 1989 die Berliner Mauer fiel und ich Kontakt zu russischen und chinesischen Kombinatorikern bekam, stellte ich fest, dass sie alle das Buch gelesen hatten. Dadurch bekam ich das Gefühl dafür, dass Mathematik eine universelle Sprache ist.

Was ist das Ihrer Meinung nach bedeutendste Ergebnis, wer der bedeutendste Mathematiker im Bereich der Diskreten Mathematik?
Das kann man so nicht sagen, da man dann 10 bis 20 Namen nennen müsste. Es gibt bedeutende Mathematiker in einzelnen Gebieten der Diskreten Mathematik, wie Shannon in der Codierungstheorie oder Tutte und Erdös in der Graphentheorie. Von den offenen Problemen ist sicherlich das P-NP-Problem das bedeutendste. Fast noch mehr fasziniert mich jedoch das Graphenisomorphie-Problem. Viele der berühmtesten Probleme auf meinem Gebiet wurden in der jüngeren Vergangenheit gelöst, wie z.B. das Vier-Farben-Problem oder der Minorensatz, welcher wohl das größte gelöste Problem der letzten 20 Jahre darstellt. Der komplette Beweis von Robertson und Seymour wird an die 1000 Seiten umfassen, ist jedoch noch nicht vollständig publiziert.