Im unlängst begonnen Sommersemester 2007 findet an der Technischen Universität Dresden eine Ringvorlesung zum Thema Geschichte der Mathematik statt. Jeweils dienstags um 16.40 sprechen unterschiedliche Sprecher im Rahmen des Studium Generale über die Entwicklung der Mathematik. Los geht es heute mit der Geschichte der Graphentheorie.
Tag-Archiv für 'Graphentheorie'
Ein neuer Trend beherrscht die Rätselspalten der Zeitungen: Sudoku.
Das Spielfeld besteht aus 9 x 9 Felder, unterteilt in 9 Regionen zu je 3 x 3 Felder. In die Felder müssen die Ziffern 1 bis 9 eingetragen werden. Bestimmte Felder sind bei Spielbeginn schon ausgefüllt. Eine Lösung ist erreicht, wenn in jeder Spalte, jeder Zeile und jeder Region jede Ziffer jeweils nur einmal vorkommt und alle Felder gefüllt sind. Durch unterschiedliche Ausgangspositionen können leichte, moderate oder schwere Rätsel gestaltet werden.
Online kann man Sudoku bei websudoku.com spielen.
Graphentheoretisch betrachtet ist das Problem ein Problem der Färbung. Ein gegebener Graph mit 81 Knoten und partieller 9-Färbung soll eine vollständige 9-Färbung erhalten. Den Knoten sind als Bezeichnungen ihr Koordinaten zugeordnet und zwei Knoten sind verbunden, wenn die zugehörigen Felder in der gleichen Reihe, Spalte oder Region liegen.
Die Lösungen von Sudoku-Problemen sind immer Lateinische Quadrate, allerdings gibt es durch die Regionen viel weniger Sudoku-Lösungen als Lateinische Quadrate. Insgesamt sind es 6670903752021072936960.
Auf den Seiten von Prof. Diestel findet sich das Buch Graphentheorie als vollständige elektronische Ausgabe.
Das Buch führt in die Graphentheorie ein und behandelt die wichtigsten Methoden der heutigen Graphentheorie, einschließlich moderner Techniken wie Regularitätslemma, Zufallsgraphen, Baumzerlegungen und Minoren. Spannender Lesestoff für das Wochenende.
Kommentare