Graphentheorie erklärt
Netze sind überall: Straßen, Lieferketten, Rechnernetze, Beziehungen. Die elf Linien dieses Bereichs stellen jeweils eine Frage an ein Netz: wie man hindurchkommt und was hindurchpasst, wie man zuordnet, was das Netz selbst auszeichnet und was sich auf ihm ausbreitet.
Jede Linie hat eine eigene Seite mit einem Abhängigkeitsgraphen und ihren Demos. Die Themenfelder unten ordnen die Linien nach Verwandtschaft, der Beziehungsgraph am Ende zeigt, welche Linien sich Bausteine teilen.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Wege und Flüsse
Wie man durch ein Netz kommt und was durch es hindurchpasst: kürzeste Wege, maximale und kostenminimale Flüsse, billigste verbindende Bäume.
Kürzeste Wege
Wie findet man die beste Route? Zwölf Verfahren von der Breitensuche bis zur Fahrplanauskunft, jedes mit seiner gemessenen Grenze.
Zur Linie →Spannbäume
Wie verbindet man alle Standorte mit möglichst wenig Leitung? Elf Stücke vom billigsten Baum über Richtung, Kapazität und Zwischenknoten bis zum Zufallsbaum.
Zur Linie →Netzwerkfluss
Wie viel geht durch ein Netz, was kostet es, und was ändert sich, wenn Güter sich Kanten teilen, der Ausbau selbst Entscheidung ist oder die Zeit mitzählt? Neunzehn Stücke von Edmonds-Karp bis zum Fluss über die Zeit.
Zur Linie →Schnitte und Zusammenhang
Wie robust hängt ein Netz zusammen, und wie teilt man es in Teile? Acht Stücke über Engstellen, kleinste Schnitte, getrennte Terminals, fehlende Leitungen, ausgewogene Hälften und zusammenhängende Gebiete.
Zur Linie →Zuordnen und Strukturen
Paare bilden und das Netz selbst vermessen: Matching, Zentralität, Gemeinschaften, Färbung, Schnitte, Cliquen, Baumweite, Abhängigkeitspläne und planare Graphen.
Matching-Algorithmen
Wer wird womit gepaart? 13 Verfahren von der billigsten Kante zuerst bis zum Nierentausch unter medizinischen Zwängen, jedes mit seiner gemessenen Grenze.
Zur Linie →Graphen und Netzwerke
Wie durchmustert man ein Netz, welche Kante ist kritisch, wie wichtig ist ein Knoten, und wie verwundbar ist das Ganze? Dreizehn Stücke von BFS/DFS über die interne Verlinkung einer echten Website bis zur eigenen Forschung über Bandbreite.
Zur Linie →Härte und Struktur
Welche Sendungen dürfen zusammen fahren? Acht Stücke über Cliquen, Überdeckungen und Baumweite: was Struktur auf einem Konfliktgraphen leicht macht und wo sie nicht reicht.
Zur Linie →Ordnung und Abhängigkeit
Ist ein Plan einhaltbar? Neun Stücke über Kreise, kritische Pfade, Ketten und Reihenfolgen: was Abhängigkeiten zwischen Aufgaben bedeuten und wo die Rechnung teuer wird.
Zur Linie →Planarität und Zeichnen
Lässt sich ein Netz ohne Überkreuzung zeichnen, und was folgt daraus? Neun Stücke über Färben, Trennen, Zeichnen, Flüsse als kürzeste Wege, Näherung, Zählen und fast planare Netze.
Zur Linie →Ausbreitung und Dynamik
Was sich auf einem Netz bewegt oder verändert: Nachrichten, Befall, Meinungen und Standorte. Die Struktur bestimmt, wohin es läuft; die Linie misst, wo bekannte Vermutungen halten und wo nicht.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Zur Linie →Modelle und Muster
Netze aus Zufallsmodellen erzeugen, ihr Verhalten ausrechnen und gegen Theorie und Daten halten: wo ein Modell trägt, wo nicht und wie man die Familie wählt.
Netzmodelle
Welches Zufallsmodell erzeugt welche Eigenschaft eines Netzes, wie prüft man ein Netz gegen ein Modell, und was geschieht, wenn keines passt? Neun Stücke vom Zufallsgraphen bis zur Modellwahl.
Zur Linie →Empfohlene Reihenfolge
Wer einen Bereich von vorn lesen möchte: Die Reihenfolge folgt den Bausteinen, die eine Linie von einer anderen übernimmt (die Belege stehen auf den Linienseiten unter „Verwandt in anderen Linien“). Alles lässt sich auch einzeln lesen.
- Kürzeste Wege: Kürzeste Wege sind der Baustein der Netzwerkfluss-Linie: Successive Shortest Paths rechnet in jeder Runde einen kürzesten Weg.
- Spannbäume: Der billigste Spannbaum ist nicht der Baum der kürzesten Wege: Baukosten gegen Umwege.
- Matching-Algorithmen: Zuordnungen; die Ungarische Methode hat eine Dijkstra-Sicht (kürzeste Wege über reduzierte Kosten).
- Netzwerkfluss: Bipartites Matching ist Fluss auf Einheitsnetzen; hier verallgemeinert auf Kapazitäten und Kosten.
- Graphen und Netzwerke: Zentralität, Färbung und Brücken: Fragen an das Netz selbst, die die Linien davor ergänzen (bipartit heißt 2-färbbar).
- Netzwerkanalyse: Baut auf Zentralität, Brücken und Kaskaden auf und fragt weiter: Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen und Kontaktfolgen.
Wie die Linien dieses Bereichs zusammenhängen
Jede Kante steht für einen belegten Zusammenhang: Ein Verfahren nutzt innen eine Technik der anderen Linie, oder beide gehen dasselbe Problem aus verschiedenen Blickwinkeln an. Die Farbe zeigt das Themenfeld, gestrichelte Kästen sind Linien aus anderen Bereichen, mit denen es Verbindungen gibt. Die jeweilige Linienseite erklärt jeden Zusammenhang unter „Verwandt in anderen Linien“.
Die Kästen sind klickbar und öffnen die jeweilige Seite.
- Wege und Flüsse
- Zuordnen und Strukturen
- Ausbreitung und Dynamik
- Modelle und Muster
- Linie eines anderen Bereichs
Weitere Bereiche
Optimierung
Verfahren, die aus sehr vielen Möglichkeiten eine beste oder gut begründete Entscheidung suchen: mit Beweis, mit Heuristik, für Planung und unter Unsicherheit.
Maschinelles Lernen
Verfahren, die aus Daten lernen: Struktur finden, wenn niemand die Antwort vorgibt, vorhersagen, wenn Beispiele vorliegen, und handeln oder Wirkung messen.
Signalverarbeitung
Verfahren, die aus gemischten oder unscharfen Messungen die ursprünglichen Signale zurückgewinnen oder aus verrauschten Messungen einen Zustand schätzen.
Kooperation und Wettbewerb
Verfahren für Entscheidungen mit mehreren Beteiligten: Anreize und Kooperation, direkte Gegner, Turniere, Ranglisten und gemeinsames Entscheiden und Teilen.