Schnitte und Zusammenhang erklärt
Fällt ein Standort oder eine Leitung aus, soll das Netz zusammenhängen, und will man es in Betriebshälften oder Gebiete teilen, soll möglichst wenig dazwischen liegen. Beides sind Fragen an dasselbe Verbindungsnetz zwischen Standorten, und beides läuft über Schnitte: Mengen von Leitungen oder Standorten, deren Wegfall das Netz trennt. Diese Linie nimmt die Frage achtmal in die Hand: wie viele unabhängige Verbindungen es gibt, was der kleinste Schnitt ist, wie man mehrere Standorte trennt, welche Leitungen fehlen und wie man ein Netz ausgewogen und zusammenhängend teilt.
Die Stücke haben zwei Arme. Der erste beginnt beim Zusammenhang (Menger) und führt zum globalen Schnitt, zum Trennen mehrerer Terminals und zum Verstärken. Der zweite beginnt beim ausgewogenen Halbieren und führt zum mehrstufigen und zum spektralen Teilen und am Ende zu zusammenhängenden Gebieten. Gerechnet wird auf erzeugten Netzen (Zufalls-, Gitter-, Ring-, skalenfreie, Verbund- und Kartennetze) mit festem Zufalls-Seed; echte Betriebsnetze gehören nicht dazu.
In short: Interactive demos on cuts and connectivity in networks: Menger's theorem and vertex connectivity, global minimum cut with Stoer-Wagner and Karger, multiway cut, connectivity augmentation, balanced graph bisection, multilevel and spectral partitioning, and connected balanced districts.
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 ↓
Zum Nachlesen: erst einfach, dann fachlich
Disjunkte Wege im Netz verständlich erklärt
Warum die Zahl der Wege zwischen zwei Standorten, die sich nirgends berühren, genau der Zahl der Ausfälle entspricht, die das Netz trennen, und warum der Mindestgrad die Engstelle übersehen kann: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die acht Stücke im Überblick
Die Linie hat zwei Arme. Der Zusammenhang-Arm beginnt bei Menger und geht zum globalen Min-Cut; von dort führt ein Pfeil zum Trennen mehrerer Terminals und einer zum Verstärken. Der Partitionier-Arm hängt am globalen Min-Cut: Ohne Balance wäre der kleinste Schnitt meist ein einzelner Standort, deshalb teilt man ausgewogen (Bisektion) und kann das mehrstufig oder spektral tun.
Das letzte Stück ist ein Zusammenfluss: Gebiete, die ausgewogen und zusammenhängend sein sollen, brauchen das mehrstufige Teilen (dessen Ergebnis nicht immer zusammenhängt), den Schnitt der spektralen Verfahren und die Frage nach dem Zusammenhang aus dem ersten Arm.
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
Der gestrichelte Doppelpfeil ist ein Kontrast (global statt lokal), 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
- Netzwerkfluss — Die Demo zu Menger zählt disjunkte Wege mit demselben Fluss, den Edmonds–Karp in der Nachbarlinie zeigt: ein Fluss mit Einheitskapazitäten, bei dem jeder Standort in einen Eingang und einen Ausgang gespalten wird. Den kleinsten Schnitt des ganzen Netzes liefert der globale Min-Cut ohne einen Fluss je Standortpaar.
- Planarität und Zeichnen — Die Separator-Demo teilt planare Karten mit wenigen Knoten in zwei Hälften; dieselbe Aufgabe ohne die Planarität löst die Bisektion dieser Linie mit Tauschen und Verschieben, und das mehrstufige Teilen misst, wann sich das Vergröbern lohnt.
Menger: disjunkte Wege und Zusammenhang
Verfolgen Sie, wie viele unabhängige Verbindungen ein Netz zwischen zwei Standorten hat und wo die Engstelle liegt: die kleinste Menge von Standorten oder Leitungen, deren Ausfall das Netz trennt. Die Demo zählt Wege und zeigt die Engstelle. Der Haken: Der Mindestgrad, die kleinste Zahl von Leitungen an einem Standort, sagt den Zusammenhang auf dünnen Netzen in 59 von 60 voraus, im Verbundnetz aus dichten Regionen in keinem von 10.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Globaler Min-Cut: Stoer–Wagner und Karger
Sehen Sie, wie man den kleinsten Schnitt eines ganzen Netzes findet, ohne jedes Standortpaar einzeln zu prüfen: Stoer–Wagner verschmilzt Standorte Phase für Phase, Karger würfelt Kontraktionen aus. Die Demo zählt, wie oft das Würfeln trifft. Der Haken: Bei gleichen Gewichten trennt der kleinste Schnitt dünner Netze fast immer nur einen Standort ab (58 von 60); die Würfelschranke ist dort viel pessimistischer als die Praxis.
Demo starten →Mehrere Terminals trennen: Multiway-Cut und k-Schnitt
Verfolgen Sie, wie man drei oder mehr Standorte so voneinander trennt, dass keiner mehr einen anderen erreicht. Ab drei Standorten ist das schwer; das einfache Verfahren nimmt je Standort den kleinsten Schnitt gegen die anderen und lässt den teuersten weg. Der Haken: Die Garantie ist auf einem Zyklus scharf, auf Modellnetzen in 0 von 168 Fällen; im Mittel 2 % über dem Optimum.
Demo starten →Zusammenhang verstärken und Netze entwerfen
Sehen Sie, welche Leitungen fehlen, damit kein einzelner Ausfall das Netz trennt, und was das kostet. Neue Leitungen verbinden die Blätter des Brückenbaums paarweise; den billigsten Entwurf liefert bis 14 Standorte ein ganzzahliges Programm, die Rundung kommt nahe. Redundanz kostet im Mittel das 1,53-Fache eines Spannbaums. Der Haken: Der billigste Entwurf ist verwundbar, in 27 von 56 Modellnetzen ein einziger Kreis, in dem jedes Leitungspaar das Netz trennt.
Demo starten →Ausgewogen halbieren: Kernighan–Lin und Fiduccia–Mattheyses
Verfolgen Sie, wie man ein Netz in zwei gleich große Hälften mit wenigen Leitungen dazwischen teilt: Kernighan–Lin tauscht Paare, Fiduccia–Mattheyses verschiebt einzelne Standorte mit etwas Spielraum in der Balance. Der Haken: Bei gerader Standortzahl ist ohne Spielraum jeder Zug blockiert, und ein Start trifft das Optimum in 84 gemessenen Netzen nur in rund drei von vier, das Beste aus 10 Starts in allen.
Demo starten →Mehrstufig partitionieren: Vergröbern, Teilen, Verfeinern
Sehen Sie, warum man ein großes Netz erst vergröbert, das kleine teilt und dann verfeinert: Lokale Verbesserung sieht nur die Umgebung, ein vergröbertes Netz verschiebt ganze Verbünde auf einmal. Die Demo vergleicht es mit einstufigem Teilen bei mindestens gleichem Aufwand. Der Haken: Klar vorn liegt das mehrstufige Verfahren nur auf größeren Kartennetzen (256 Standorte: rund 30 % weniger Leitungen, stark streuend), sonst ist er klein.
Demo starten →Spektrale Schnitte: Fiedler-Vektor, Sweep-Cut und Cheeger
Verfolgen Sie, wie ein Eigenvektor der Netzmatrix, der Fiedler-Vektor, einen Schnitt verrät: Man sortiert die Standorte nach seinen Werten und schneidet an der besten Stelle. Die Demo vergleicht drei Maße für einen guten Schnitt. Der Haken: Beim Gitter ist der Eigenwert doppelt; je nach Wahl im Eigenraum trifft der Sweep den dünnsten Schnitt oder nicht (bei etwa der Hälfte der Richtungen).
Demo starten →Gebiete aufteilen: ausgewogen und zusammenhängend
Sehen Sie, ob die Teile einer Teilung in einem Stück liegen: Bei vier und acht Gebieten zerfällt die Halbierung in rund der Hälfte bzw. drei Vierteln der Netze. Die Demo prüft das, hängt Inseln um und stellt das Bezirkswachstum daneben. Der Haken: Das Umhängen senkt den Schnitt, macht aber das größte Gebiet im Mittel 1,27-mal so groß wie ideal; das Wachstum hält auf Kartennetzen die Grenze öfter ein.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle acht Stücke, entlang der Frage, was man über das Netz wissen oder mit ihm tun will: wie robust der Zusammenhang ist, wo der kleinste Schnitt liegt, wie man Standorte trennt, welche Leitungen fehlen oder wie man das Netz in Teile zerlegt.
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 Netze der Demos, nicht für jedes Netz. Ein Verfahren, das immer ausgewogen, zusammenhängend und mit kleinstem Schnitt teilt, gibt es nicht (Stück 8), und der Vorteil des mehrstufigen Teilens hängt am Netztyp (Stück 6).
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.
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.
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.
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.