Graphentheorie verständlich

Dieser Abschnitt ist das Herzstück zum Verständnis von SPM++. Er zeigt zuerst, wie unvorstellbar groß die Zahl möglicher Stundenpläne ist – und dann den eleganten Trick, mit dem das Programm trotzdem in Sekunden gute Pläne findet.

Teil 1 – Große Zahlen

Warum kann man einen Stundenplan nicht einfach „durchprobieren"? Weil die Zahl der Möglichkeiten jede Vorstellungskraft sprengt.

Eine einzelne Klasse

Nehmen wir eine Klasse mit 30 Wochenstunden (5 Tage × 6 Stunden). Ohne jede Bedingung gibt es so viele Pläne wie Permutationen von 30 Elementen – also 30!:

30! = 265 252 859 812 191 058 636 308 480 000 000 ≈ 2,65 · 10³²

Bedingungen schränken das stark ein (gleiche Fachstunden sind austauschbar, sollen über die Woche verteilt sein, werden zu Blöcken zusammengefasst). Realistisch bleiben pro Klasse etwa 10¹⁵ verschiedene Pläne.

Eine ganze Schule

Bei 20 Klassen würde man naiv multiplizieren – das ergäbe rund 10³⁰⁰ Pläne, wenn die Klassen völlig unabhängig wären. Rechnet man sehr vorsichtig mit nur drei wirklich unabhängigen Klassen, bleiben immer noch:

(10¹⁵)³ = 10⁴⁵ kollisionsfreie Pläne

Ein Bild für 10³⁰ gute Pläne

Selbst wenn nur einer von einer Billiarde dieser Pläne „gut" wäre, gäbe es noch 10³⁰ gute Pläne. Druckte man sie auf hauchdünnes Papier, wäre der Stapel etwa eine Milliarde Lichtjahre hoch – die Größenordnung des bekannten Universums.

Warum ist Planen dann schwer?

Nicht, weil es zu wenige gute Pläne gäbe – sondern weil die Lösungsdichte winzig ist. Auf rund 10²⁵⁵ zufällige, „naive" Pläne kommt nur ein kollisionsfreier.

Es gleicht der Suche nach einer Nadel im Heuhaufen – nur sind sehr viele Nadeln unter einer gigantischen Zahl von Strohhalmen versteckt.

Teil 2 – Der Graph als Lösung

Viele komplexe Probleme – Stundenplanung ebenso wie das Traveling-Salesman-Problem – lassen sich auf einen mathematischen Graphen abbilden. Ein Graph besteht aus Knoten und Kanten.

Ein Graph aus Knoten und Kanten. Die rot markierten, untereinander vollständig verbundenen Knoten bilden einen vollständigen Teilgraphen – er entspricht einem (Teil-)Stundenplan.

Vom Stundenplan zum Graphen

Schritt 1 – Knoten: Jedem Unterricht wird eine ganze Menge von Knoten zugeordnet – einer je möglichem Zeitpunkt. Eine Deutschstunde, die an 5 Tagen zu je 6 Stunden liegen kann, bekommt 5 × 6 = 30 Knoten. Vier Deutschstunden also 120 Knoten. Eine durchschnittliche Schule mit ~600 Unterrichtsstunden kommt so auf etwa 14 000 Knoten.

Ein Stundenplan ist dann eine kollisionsfreie Auswahl von je einem Knoten aus jeder Unterrichts-Knotenmenge.

Schritt 2 – Kanten: Eine Kante zwischen zwei Knoten bedeutet „diese beiden vertragen sich" (Verträglichkeitslinie). Daraus folgen drei Regeln:

1. Ein Stundenplan ist eine Knotenauswahl, die paarweise verbunden ist – also ein vollständiger Teilgraph.
2. Zwei Knoten desselben Unterrichts sind nie verbunden (er findet nur einmal statt).
3. Zwei Knoten verschiedener Unterrichte sind nur verbunden, wenn sie keine Ressource (Klasse, Klassenteil, Lehrer, Raum) zur gleichen Zeit teilen.

Beispiel

Knoten	Zeit	Klasse	Fach	Lehrer	Raum
kA	Do 3	8a	D	Huber	R206
kB	Do 3	10. Jgst	Eth	Huber	R206
kC	Fr 4	5b	M	Müller	R202
kD	Mo 1	6c	M	Müller	R104

• kA ↔ kB: gleiche Zeit (Do 3), gleicher Lehrer und Raum → Konflikt, keine Kante.
• kC ↔ kD: gleicher Lehrer Müller, aber verschiedene Zeiten → verträglich, Kante.

flowchart LR
    kA["kA · Do3 · Huber · R206"]
    kB["kB · Do3 · Huber · R206"]
    kC["kC · Fr4 · Müller · R202"]
    kD["kD · Mo1 · Müller · R104"]
    kC ---|verträglich| kD
    kA -. Konflikt .- kB

Wünsche = Kanten löschen

Sonderbedingungen setzt man um, indem man Kanten entfernt. Sollen zwei Biologiestunden nicht an aufeinanderfolgenden Tagen liegen, löscht man alle Kanten zwischen den Montags-Knoten der einen und den Dienstags-Knoten der anderen Stunde – und so für jedes Tagespaar.

Teil 3 – Die Vorteile

• Keine Kollisionsprüfung nötig. Man sieht sofort, mit welchen Stunden ein Konflikt bestünde – der Graph ist ein bleibendes „Verkehrsnetz".
• Einmaliger Aufbau, dauerhafter Nutzen. Der Graphaufbau dauert nur 1–4 Sekunden und braucht 4–16 MB Speicher – investiert sich aber bei jedem Planungsschritt zurück.
• Der ganze Lösungsraum liegt im Speicher. In Sekundenbruchteilen ist entscheidbar, ob ein Plan zulässig ist.

Die Kuchenform-Metapher

Der Graph wirkt wie eine Kuchenform: Jede Lösung hat genau die Form, die Sie vorher durch Bedingungen festgelegt haben – Ausnahmen gibt es nicht. Das klingt starr, ist aber der Schlüssel: Was muss gelten, steckt in der Form (dem Graphen). Was gelten soll, wenn möglich, regeln zwei flexible Techniken – die Pseudounterrichte und die Optimierung.

Teil 4 – So plant SPM++ damit

Aus dem Graphen erzeugt SPM++ in wenigen Schritten einen Plan:

1. Datenvorbereitung – Listen und Bedingungen (mit SPE).
2. Graphaufbau – ein Klick, wenige Sekunden.
3. Erste Planung – im Planungsdialog. Sie bestimmen die Reihenfolge; schwer planbare Stunden zuerst: Elementarzeiten, Pseudounterrichte, Gleichbedingungen (Kopplungen), Mehrfachstunden.
4. Optimierung – Wünsche so weit wie möglich erfüllen.
5. Ausgabe – Text (Semigraphik), CSV/Excel oder HTML.

Planungstiefe – wie ein Schachcomputer

Wie weit SPM++ vorausschaut, steuert die Planungstiefe – vergleichbar mit dem Schwierigkeitsgrad eines Schachcomputers. Größere Tiefe = höhere Erfolgswahrscheinlichkeit, aber längere Rechenzeit. Jeder Zwischenstand ist speicherbar, jeder Schritt rückgängig zu machen. Bleiben Stunden offen, setzt man früher auf und verplant die Problemstunden zuerst – oder erhöht die Tiefe.

Optimierung – die Zielfunktion

Die Optimierung realisiert alle Wünsche („Soll-Bedingungen"), die nicht starr im Graphen stecken. Dazu berechnet SPM++ eine Zielfunktion – ein niedriger Wert = guter Plan – und minimiert sie durch Umplanung. Kategorien (individuell gewichtbar):

Kategorie	Ziel
Lehrerhohlstunden	tolerierbare Zahl und Häufung pro Tag, je Lehrer
Tagesleistungen	min./max. Stundenzahl pro Tag, je Lehrer
Fächerschnitt	Fächer nicht immer spät am Tag (mittlere Stunde optimieren)
Raumoptimierung	knappe Räume möglichst gut ausnutzen

Jeder Optimierungslauf ist jederzeit abbrechbar; das Erreichte bleibt erhalten. Manuelle Umplanung per Drag & Drop ergänzt die Automatik, eine Vergleiche-Funktion zeigt alle Änderungen.

Fazit

Der Graph als Datenmodell bringt in allen Phasen Vorteile: blitzschnelle Planung, klare Trennung von Bedingungen (Pflicht) und Wünschen (nach Möglichkeit) und flexible Optimierung. So lassen sich die vielen, oft widersprüchlichen Vorstellungen eines „guten Plans" erstaunlich weitgehend erfüllen.