Härte und Struktur erklärt
Ein Verlader fasst Sendungen zu Fuhren zusammen, aber manche dürfen nicht zusammen fahren: Gefahrgut, Temperaturen, Kundenwünsche. Diese Konflikte bilden einen Graphen, und dieselbe Frage nimmt diese Linie achtmal in die Hand: Welche Fuhren sind möglich, welche ist die größte, wie viele Sendungen muss man auslagern, welche Struktur des Graphen macht das Problem leicht, und was bleibt, wenn der Graph für jedes exakte Verfahren zu groß ist? Im Allgemeinen sind alle diese Aufgaben NP-schwer; jede Demo misst, wo Struktur sie trotzdem handhabbar macht und wo nicht.
Die Stücke bauen aufeinander auf: erst alle Cliquen aufzählen und die größte finden, dann Konflikte durch Auslagern beseitigen, dann die Struktur nutzen (chordale Graphen, Baumweite, Programmierung auf der Zerlegung) und am Ende große Graphen mit Reduktionsregeln und Lokalsuche angehen. Die Kantenclique-Überdeckung berührt die eigene Forschungsarbeit (Engel und Hanisch 2016), ohne etwas Neues zu behaupten. Gerechnet wird auf erzeugten Konfliktnetzen und dem Straßennetz eines Toronto-Ausschnitts (OpenStreetMap).
In short: Covers maximal cliques, maximum clique, vertex cover, chordal graphs, treewidth, dynamic programming on tree decompositions, edge clique cover and reductions with local search for independent sets. Interactive demos show where structure makes hard graph problems tractable.
Hintergrund zum Thema: Netzwerkdesign.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Die acht Stücke im Überblick
Die Linie hat eine Wurzel und zwei Stränge. Bron–Kerbosch zählt alle maximalen Cliquen auf und ist die Wurzel; aus ihm folgen die größte Clique mit einer Färbungsschranke, die Knotenüberdeckung (dieselbe Frage mit umgekehrtem Blick: Konflikte statt Verträglichkeit) und die chordalen Graphen, bei denen eine Ordnung die Suche ersetzt. Aus der Ordnung wird die Baumweite, und auf der Baumzerlegung rechnet die Programmierung, die als Zusammenfluss die Suche der Stücke 2 und 3 herausfordert.
Die Kantenclique-Überdeckung führt die Cliquen aus Stück 1 mit der Reduktion vor dem Lösen aus Stück 3 zusammen. Das letzte Stück vereint Reduktionsregeln, die Zerlegung und eine Lokalsuche aus der Linie der Trajektorien-Metaheuristiken für große Graphen.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelte Doppelpfeile sind Kontraste (Suche gegen Zerlegung), gepunktete Pfeile übernehmen nur eine Idee, graue gestrichelte Knoten sind Bausteine aus anderen Linien. Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Graphen und Netzwerke — Die Überdeckung durch Cliquen hat zwei Demos in verschiedenen Linien: die Cliquenbandbreite rechnet die Überdeckung der eigenen Forschungsarbeit für kleine Hypergraphen nach, die Kantenclique-Überdeckung dieser Linie löst sie für gewöhnliche Graphen mit Reduktionsregeln und rechnet die Äquivalenz mit dem Kantenclique-Graphen für wenige Kanten numerisch nach.
- Matching-Algorithmen — Auf bipartiten Graphen sind kleinste Überdeckung und größte unabhängige Menge Matching-Fragen: die Knotenüberdeckung bestätigt den Satz von König (kleinste Überdeckung gleich größtes Matching), und die Reduktions-Demo rechnet auf Rastern selbst ein Matching nach dem Verfahren von Hopcroft–Karp, um den Wert zu beweisen, wo die Zerlegung zu breit ist.
- Trajektorien-Metaheuristiken — Die Lokalsuche der Reduktions-Demo ist eine iterierte Lokalsuche wie die Iterated Local Search der Trajektorien-Linie: dort stört eine Doppelbrücke eine Rundtour, hier erzwingt die Störung einen Knoten der Menge, und der Tauschzug ersetzt das 2-opt.
- Exakte Suche — Die Schranke macht den Suchbaum klein: Branch & Bound am Rucksack lebt von seiner Schranke, die Größte-Clique-Demo ersetzt sie durch eine Färbung und zeigt live, wie viele Knoten das spart und wo die Färbung mehr kostet, als sie bringt.
- Planarität und Zeichnen — Die Separator-Demo der Linie Planarität und Zeichnen erklärt, warum Gitter und Straßennetze eine kleine Baumweite haben, und die Baker-Technik rechnet die Reste nach dem Entfernen jeder k-ten Schicht mit der Programmierung auf der Zerlegung; dort schlägt die einfache Lokalsuche das Verfahren in Güte und Zeit.
- Netzwerkanalyse — Die Kernzahl, die die Cliquensuche als Werkzeug nutzt, ist in der k-Core-Demo der Linie Netzwerkanalyse das Thema: dort gilt, dass die Cliquenzahl höchstens die Degeneracy plus 1 ist.
- Komplexitätsklassen — Wie schwer ein Problem ist, hängt am Grund der Härte: Die Reduktionskette baut aus Formeln Graphen für Clique und Knotenüberdeckung, und die parametrisierte Demo stellt beide Fragen auf demselben Graphen mit zwei Parametern nebeneinander.
Bron–Kerbosch: alle maximalen Cliquen
Verfolgen Sie, wie Bron–Kerbosch alle paarweise verträglichen Fuhren findet, die sich nicht mehr erweitern lassen: Er baut eine Fuhre schrittweise auf und meldet sie, sobald keine Sendung mehr passt. Ein Schalter für die Pivot-Auswahl zeigt live, wie viele Sackgassen sie erspart: bei 20 Sendungen und 85 % verträglichen Paaren 20 720 Aufrufe ohne, 255 mit Pivot. Der Haken: Die Degeneracy-Außenschleife senkt die Aufrufe fast nie.
Demo starten →Größte Clique: Färbungsschranke und Kernzahl
Sehen Sie, wie die Suche nach der größten verträglichen Fuhre ganze Äste auslässt, sobald eine Schranke zeigt, dass sie nicht mehr gewinnen können; die Schranke liefert eine Färbung der Sendungen. Bei 40 Sendungen und 80 % verträglichen Paaren braucht die Suche damit 88 statt 28 507 Knoten. Der Haken: Auf sehr dünnen Graphen kostet die Färbung mehr Abfragen, als sie spart, und die Kernzahl-Vorverarbeitung hilft dort nicht.
Demo starten →Knotenüberdeckung: Approximation, Kernbildung, Verzweigen
Verfolgen Sie, wie man mit möglichst wenigen Auslagerungen alle Konflikte beseitigt: Das Matching-Verfahren liegt höchstens beim Doppelten des Optimums, ein LP rundet auf, eine Kernbildung streicht, was feststeht. Ein Vergleich zeigt live, dass der einfache Greedy meist fast optimal ist, auf einer Falle mit 24 Sendungen aber das 2,50-Fache auslagert. Die Kernbildung nach Buss hilft nur, wenn das erlaubte Budget klein ist.
Demo starten →Chordale und perfekte Graphen: Eliminationsordnung statt Suche
Sehen Sie, dass es Konfliktgraphen gibt, auf denen eine einzige Ordnung ohne jede Suche größte Fuhre, kleinste Gruppenzahl und mehr zugleich liefert: Linienbelegungen und Baumnetze sind immer chordal. Ein Netztypen-Vergleich zeigt, wie selten das bei Zufall ist: bei 16 Sendungen und 20 % Konflikten nur 0,5 %. Der Haken: Gegen die Suche mit Färbungsschranke gewinnt die Ordnung kaum, ihr Gewinn ist die Garantie.
Demo starten →Baumweite: Eliminationsordnung und Baumzerlegung
Verfolgen Sie, wie eine Eliminationsordnung einen Graphen in eine Baumzerlegung verwandelt und wie schmal sie sein kann: Die Breite misst, wie baumartig ein Konfliktgraph ist. Die Heuristiken treffen den bekannten Wert auf kleinen Gittern und Zufallsnetzen, liegen auf größeren Gittern aber darüber. Beim echten Straßennetz von Toronto bleibt die Breite ein Intervall zwischen 6 und 50, einen Wert behauptet die Demo nicht.
Demo starten →Dynamische Programmierung auf der Baumzerlegung
Sehen Sie, wie eine Tabelle je Beutel der Zerlegung die wertvollste Fuhre ohne Konflikt exakt ausrechnet. Ein Vergleich mit der Suche der Stücke 2 und 3 zeigt: Die Zerlegung gewinnt nur in einem Fenster, auf Dreiecksgittern, mit Werten und auf dem Straßennetz ab etwa 800 Kreuzungen. Auf einfachen Gittern und dünnen Zufallsnetzen gewinnt die Suche; ab etwa Breite 18 bis 19 geht in Python nichts mehr.
Demo starten →Kantenclique-Überdeckung und Kernbildung
Sehen Sie, wie wenige Verladegruppen genügen, damit jedes verträgliche Paar von Sendungen mindestens einmal zusammen fährt, und wie viel davon Reduktionsregeln aus der Literatur vorab erledigen: Auf dünnen Netzen, Rastern mit Dreiecken und dem ganzen Toronto-Ausschnitt bleibt kein Rest. Der Haken: Auf dichten Graphen bleibt fast alles übrig, und der eigene Löser findet bei 30 Sendungen nur 40 Gruppen, wo ein LP-Löser 35 findet.
Demo starten →Unabhängige Menge im großen Maßstab: Reduktionen und Lokalsuche
Sehen Sie, wie fünf Regeln einen großen Konfliktgraphen verkleinern, ohne das Optimum zu ändern, und wie eine Lokalsuche mit Tauschzügen danach fast ans Optimum kommt. Das ganze Toronto-Netz wird so exakt lösbar: Die Breite sinkt von 50 auf 12, der Wert ist 2 448. Auf Rastern und 3-regulären Graphen tun die Regeln fast nichts, dort bleibt allein die Suche, ohne Beweis.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle acht Stücke, entlang der Frage, was am Konfliktgraphen gesucht wird: alle Fuhren, die größte, eine Auslagerung, eine Überdeckung der Paare oder eine Lösung für einen großen Graphen, und welche Struktur der Graph hat.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Antworten gelten für die erzeugten Konfliktnetze und den Toronto-Ausschnitt der Demos und die dort gemessenen Größen, nicht für jeden Graphen. Die Programmierung auf der Zerlegung gewinnt nur in einem Fenster (Stück 6), und für die Kantenclique-Überdeckung ist der eigene Löser auf dichten Graphen schwächer als ein LP-Löser (Stück 7).
Weitere Linien in diesem Bereich
Kürzeste Wege
Wie findet man die beste Route? Zwölf Verfahren von der Breitensuche bis zur Fahrplanauskunft, jedes mit seiner gemessenen Grenze.
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.
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.
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.
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.
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.
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.
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.
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.
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.