Graphen und Netzwerke erklärt
Ein Betriebsnetz eines Distributionsraums (ein gestörtes Straßenraster, wahlweise Hub-and-Spoke, Zufallsgraph oder skalenfreies Netz) durchläuft in dieser Linie dreizehn Fragen: Was ist von hier aus erreichbar, welche einzelne Straße darf nicht ausfallen, wie durchläuft man jede Straße genau einmal, wie verteilt man Ressourcen ohne Konflikt, wie wichtig ist ein Knoten wirklich, und wie verwundbar ist das ganze Netz gegen Zufall, gezielten Angriff, Folgeausfälle oder Epidemien? Zwei Stücke verlassen das Betriebsnetz: Die interne Verlinkung wendet PageRank auf den echten Linkgraphen dieser Website an (eine Analyse am realen Fall statt eines Verfahrensvergleichs), und das letzte Stück rechnet die eigene, veröffentlichte Forschungsarbeit des Autors (Bandbreite der Graphenfamilie G(n,k,b), Engel & Hanisch 2016) numerisch nach.
Alle Verfahren sind von Grund auf in Python/NumPy geschrieben und gegen networkx sowie Brute-Force auf oft über 300 Instanzen je Stück geprüft (die Analyse-Karte zur internen Verlinkung ist reine Power-Iteration auf dem echten Linkgraphen und hat statt eines Vergleichs mit networkx Konsistenztests); wo ein Aufwand verglichen wird, in Elementarschritten statt in Laufzeit. Jede Demo hält auch fest, was nicht funktioniert hat: mehrere Vorab-Hypothesen sind in der Messung gefallen, etwa dass DSATUR immer optimal sei oder dass Cuthill-McKee auf dem Stern-Lehrbuch das Optimum trifft.
In short: Covers graph algorithms and network analysis: BFS and DFS, bridges, strongly connected components, graph coloring, centrality, network robustness, cascading failures and bandwidth. Interactive demos apply them to one growing network example.
Hintergrund zum Thema: Netzwerkdesign · Hafenlogistik · Seefracht.
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
Zufall oder Angriff im Netz verständlich erklärt
Warum ein Netz mit großen Knotenpunkten zufällige Ausfälle gut verkraftet und bei gezieltem Ausfall dieser Knotenpunkte schnell zerfällt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die 13 Stücke im Überblick
Die Linie hat eine Wurzel und zwei Blöcke: einen Werkzeugkasten (BFS/DFS bis Färbung) und eine Analyse-Achse (Zentralität bis Härten), dazu Bandbreite als eigener Ast. BFS und DFS ist die Wurzel; Brücken und starke Zusammenhangskomponenten beheben je eine ihrer Lücken (Einzelausfälle, Einbahnstraßen), die Färbung übernimmt von ihr nur eine Idee (bipartit heißt 2-färbbar), Euler-Touren baut auf den Brücken auf (Fleury braucht deren Brückentest bei jedem Schritt).
Zentralität ist ein Zusammenfluss aus BFS/DFS und Brücken und führt über Strukturkennzahlen zu Robustheit, die sich in Kaskaden und in Härten verzweigt; die interne Verlinkung wendet das PageRank-Maß der Zentralität auf den echten Linkgraphen dieser Website an; Härten selbst ist ein Zusammenfluss aus Zentralität, Robustheit und Kaskaden. Bandbreite übernimmt nur eine Idee der Wurzel (Cuthill-McKee ist Breitensuche mit Gradregel) und führt zusammen mit der Färbung zum golden umrandeten letzten Stück, das auf einer eigenen, veröffentlichten Forschungsarbeit beruht. Wo ein erwarteter Vorteil in der Messung ausblieb, steht das in der Kachel.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- eigene oder frische Forschung, kein etablierter Standard
Doppelt umrandete Kästen sind Zusammenflüsse (Zentralität aus BFS/DFS und Brücken; Härten aus Zentralität, Robustheit und Kaskaden; Cliquenbandbreite aus Bandbreite und Färbung); golden umrandet und mit Doppelrahmen ist die eigene Forschungsarbeit. Gepunktete Pfeile übernehmen nur eine Idee.
Verwandt in anderen Linien
- Spannbäume — Brücken sind Kanten ohne Ersatz: die Brücken-Demo misst sie auf dem ganzen Netz, die MST-Sensitivität der Spannbaum-Linie nur am Spannbaum selbst („keine Ersatzkante“ für eine Baumkante).
- Kürzeste Wege — BFS-Ebenen sind keine kürzesten Wege: die BFS-und-DFS-Demo zählt nur die wenigste Kantenzahl vom Start, die Breitensuche der Kürzeste-Wege-Linie zeigt an genau diesem Punkt, wie stark das bei ungleichen Kosten danebenliegt (im Toronto-Netz im Median 7 %, im schlimmsten Fall 237 % zu lang).
- Matching-Algorithmen — Bipartit ist 2-Färbbarkeit: die Graphfärbung-Demo zeigt DSATUR auf Bipartitgraphen beweisbar optimal, und die Matching-Linie setzt genau diese Zweiteilung voraus: Hopcroft–Karp und die Ungarische Methode rechnen beide auf zwei Seiten.
- Netzwerkfluss — Zentralität und Bandbreite fragen nach EINEM Engpass oder EINER Ordnung; die Netzwerkfluss-Linie beantwortet dieselbe Verbundenheitsfrage für ALLE Standortpaare zugleich mit dem Gomory-Hu-Baum (Menger): die Zentralität-Demo zeigt dagegen nur, welcher einzelne Knoten oder welche Kante am stärksten belastet ist.
- Lineare Programmierung — Eine schmale Bandbreite hält die Nicht-Null-Einträge einer dünnbesetzten Matrix nah an der Diagonale und macht die Cholesky-/LU-Zerlegung billig: die Bandbreite-Demo misst genau das, während die Revised-Simplex-Demo und die Innere-Punkte-Demo der LP-Linie zeigen, warum echte Löser überhaupt dünn rechnen wollen.
- Quellentrennung — Beide Demos sind direkte Nachbauten aus meiner eigenen Dissertation über Zellnetzwerke auf Multielektrodenarrays (deren zweiter Teil behandelt die Cliquenüberdeckung): die Cliquenbandbreite-Demo rechnet die Bandbreitenformel aus Engel & Hanisch (2016) nach, der Verzögerungsgraph der Quellentrennungs-Linie nutzt dieselbe Elektrodengitter-Idee für Spike-Sorting.
- Turnierplanung — Ein Rundenturnier ist Kantenfärbung/1-Faktorisierung von K_n, nicht die Knotenfärbung der Graphfärbung-Demo hier (ein Ressourcenkonflikt-Modell), zwei unterschiedliche Färbungsbegriffe für denselben Graphen, beide gegen echte Referenzdaten geprüft: die Rundenturnier-Demo der Turnierplanung-Linie gegen die FIDE-Berger-Tafeln, Graphfärbung gegen öffentliche Testinstanzen.
- Ranking — Massey und Colley lösen ein Kleinste-Quadrate-System auf dem Vergleichsgraphen, wo PageRank einen Eigenvektor desselben Graphen sucht: ein Kontrast, kein Nachbau.
- Kausale Diagramme und Adjustierung — Ob ein Pfad im Ursachen-Diagramm offen oder blockiert ist, ist eine Pfadsuche wie hier die BFS und DFS; die d-Separation der Linie Kausale Diagramme und Adjustierung fügt die Regel hinzu, wann ein Knoten den Pfad sperrt (Kette, Gabel) und wann er ihn erst öffnet (Collider).
- Härte und Struktur — 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 der Linie Härte und Struktur löst sie für gewöhnliche Graphen mit Reduktionsregeln und rechnet die Äquivalenz mit dem Kantenclique-Graphen für wenige Kanten numerisch nach.
- Ordnung und Abhängigkeit — Die Zerlegung in starke Zusammenhangskomponenten hat einen Nachbarn in der Linie Ordnung und Abhängigkeit: Kreise liegen nur innerhalb einer Komponente, und die Di-Kreis-Demo behandelt den Kreis selbst als Beleg, während das Auflösen der Kreise den Plan zuerst in Komponenten zerlegt und jede für sich löst.
- Planarität und Zeichnen — Die Demo zum Färben planarer Graphen der Linie Planarität und Zeichnen misst, dass auf Karten schon bei 100 Standorten DSATUR die vier Farben des Vierfarbensatzes meist nicht mehr findet; Kempe-Ketten und die exakte Entscheidung ergänzen die hier gezeigten Verfahren.
- Netzwerkanalyse — Die Linie Netzwerkanalyse nimmt diese Maße in die Hand: die Einflussmaximierung wählt Starter nach Grad, Nähe und Betweenness, die strukturellen Löcher stellen die Brücken neben Burts Constraint, und die zeitlichen Netze messen, wie viel eine Ausbreitungsrechnung ohne die Reihenfolge der Kontakte überschätzt.
- Netzmodelle — Die Zufallsgraph-Demo macht die Riesenkomponente zum Thema, die hier als Perkolation nur Vehikel ist; das Konfigurationsmodell liefert das Nullmodell, das die Strukturkennzahlen nutzen, und der Potenzgesetz-Test baut, was dort ausdrücklich als nicht gebaut genannt ist. Die abhängigen Netze rechnen nur den Zusammenhang, die Kaskaden-Demo dieser Linie lastbasierte Ausfälle.
BFS und DFS: die Durchmusterung eines Netzes
Sehen Sie, wie die Breitensuche ein Netz Ring für Ring abarbeitet, während die Tiefensuche einer Straße so weit wie möglich folgt, bevor sie umkehrt. Die Demo lässt beide ein Straßenraster mit gesperrten Straßen durchmustern: Beide finden dieselben Teile, aber die Tiefensuche muss bei 30 % Sperrung bis zu 15,3-mal mehr Knoten gleichzeitig merken. Im Zufallsgraphen gilt das kaum, der Speichervorteil der Breitensuche ist also keine allgemeine Regel.
Demo starten →Brücken und Artikulationspunkte: welche Straße darf nicht ausfallen?
Sehen Sie, wie Tarjans Low-Link in einer einzigen Tiefensuche findet, welche Straße oder Kreuzung das Netz trennt, statt jedes Element einzeln auszuprobieren. Ein Regler für den Anteil gesperrter Straßen zeigt, wie häufig Brücken werden: Bei 30 % gesperrt sind 11 % der Straßen der größten Komponente Brücken. Der Ausfallschaden konzentriert sich nur nahe der Zerfallsschwelle auf wenige Elemente.
Demo starten →Starke Zusammenhangskomponenten: Einbahnstraßen im Netz
Verfolgen Sie, wie Kosaraju (zwei Tiefensuchen) und Tarjan (eine) ein Einbahnstraßennetz in Teile zerlegen, in denen jede Kreuzung jede andere hin und zurück erreicht. Die Demo lässt den Einbahn-Anteil wachsen. Ehrlich gemessen: Bei vollständiger Einbahnregelung bleiben im Zufallsgraphen 57 % der Knoten in der größten Komponente, im Raster nur 26 %, obwohl der Zufallsgraph bei mittleren Anteilen schneller zerfällt.
Demo starten →Eulertouren: jede Kante genau einmal
Verfolgen Sie, wie Hierholzer kleine Kreise zu einer Eulertour verschmilzt, die jede Kante genau einmal befährt, während Fleury bei jedem Schritt auf Brücken prüft. Die Demo vergleicht den Rechenaufwand beider: Fleury braucht im größten gemessenen Fall das 30-Fache. Der Haken: Schon ab 16 Knoten ist praktisch kein gemessenes Zufalls- oder Rasternetz mehr von selbst eulersch.
Demo starten →Graphfärbung: Greedy, Welsh-Powell, DSATUR, exakt
Sehen Sie, wie Greedy, Welsh-Powell und DSATUR Lieferzeitfenstern Rampen zuweisen, sodass sich keine überlappenden Lieferungen eine teilen, und eine exakte Suche den Optimalwert prüft. Auf Zeitfenstergraphen ist Greedy nach Startzeit beweisbar optimal. Der Haken: DSATUR ist nicht beweisbar optimal, in einem dichten Zufallsgraphen brauchte es 9 statt der optimalen 8 Farben.
Demo starten →Zentralität: Grad, Closeness, Betweenness, PageRank
Sehen Sie, wie Grad, Closeness, Betweenness und PageRank die Wichtigkeit eines Knotens auf vier Arten messen, und wie Brandes' Verfahren die Betweenness effizient berechnet. Die Demo vergleicht, welches Maß die Schwächung des Netzes beim Ausfall am besten vorhersagt: meist die Betweenness. Auf einem ungesperrten, regelmäßigen Raster ist PageRank dagegen mit 0,26 der schwächste Vorhersager.
Demo starten →Strukturkennzahlen und Nullmodelle: Clustering, Kleine Welt, Assortativität
Sehen Sie, wie Clustering, Kleine-Welt-Effekt und Assortativität (wer sich mit wem verbindet) ein Netz als Ganzes beschreiben, und wie ein Nullmodell mit gleicher Gradfolge prüft, ob eine Eigenschaft etwas Eigenes ist. Schon bei 1 % Umverdrahtung fällt die mittlere Weglänge eines Ring-Gitters auf 53 %, das Clustering bleibt hoch. Die Disassortativität des skalenfreien Netzes folgt dagegen größtenteils schon aus der Gradfolge.
Demo starten →Robustheit: Zufall gegen gezielten Angriff, Perkolationsschwelle
Sehen Sie, wie ein Netz schrumpft, wenn Knoten zufällig oder gezielt nach Grad oder Betweenness entfernt werden, gemessen am Robustheitsindex R. Auf dem skalenfreien Netz fällt R von 0,4065 bei Zufall auf 0,1112 beim gezielten Angriff auf die Hubs. Der Haken: Schon das Betriebsnetz zeigt einen messbaren Unterschied, und es gibt keinen einheitlich besten Angriff, mal gewinnt Grad, mal Betweenness.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Kaskaden und Ausbreitung: lastbasierte Ausfälle, SIR-Epidemieschwelle
Verfolgen Sie, wie der Ausfall eines Hubs eine Kettenreaktion auslöst, wenn umgeleitete Wege andere Knoten über ihre Kapazität treiben, und wie sich eine Infektion über die Kanten ausbreitet. Die Demo variiert die Toleranz: Die kritische Toleranz unterscheidet die Netze deutlich (17,0 beim skalenfreien Netz gegen 2,8 beim Betriebsnetz), der Schaden bei festem Wert dagegen kaum.
Demo starten →Kritische Knoten härten: Zufällig, Bypass, Schneider u. a. 2011
Sehen Sie, wie Schneiders Hill-Climb ein Netz mit begrenztem Budget härtet, indem er Kanten tauscht und die Gradfolge erhält. Die Demo vergleicht ihn mit zufälligen Kanten und einer Kritische-Kante-Bypass-Strategie. Der Haken: Die vermeintlich smarte Bypass-Variante lässt den Robustheitsindex auf dem skalenfreien Netz bei 0,1112 unverändert, Schneiders Variante hebt ihn auf 0,1588.
Demo starten →Interne Verlinkung: Diagnose und Wirkungsanalyse
Sehen Sie, wie PageRank am echten Linkgraphen dieser Website zeigt, wohin die Linkkraft fließt, und wie zwei feste Korrekturen sie umverteilen. Die Demo vergleicht vorher und nachher. Startseite und Kontaktseite halten zusammen 22,1 % des PageRank, mehr als alle Konzepte-Linien (6,7 %), weil jede Demo im Footer nur auf diese beiden zurückverlinkt. Eine frühere Fassung mit optimierter Rücklink-Auswahl wurde verworfen, weil sie wie Linkmanipulation gewirkt hätte.
Demo starten →Bandbreite eines Graphen: Cuthill-McKee und Reverse Cuthill-McKee
Sehen Sie, wie Cuthill-McKee Knoten per Breitensuche mit Gradregel so nummeriert, dass die Nicht-Null-Einträge einer dünnbesetzten Matrix nah an der Diagonale liegen. Die Demo prüft das an einem zufällig vertauschten Raster, das in allen 35 getesteten Fällen die natürliche Bandbreite zurückerhält. Der Haken: Auf dem Stern-Lehrbuchbeispiel verfehlt das Verfahren das nachrechenbare Optimum systematisch.
Demo starten →Bandbreite von G(n,k,b) und Cliquenüberdeckung
Verfolgen Sie, wie die exakte Bandbreitenformel und die Cliquenüberdeckungs-Äquivalenz der eigenen Forschungsarbeit (Engel und Hanisch 2016) an Zufallsinstanzen numerisch nachgerechnet werden. Die Äquivalenz hielt auf 300 zufälligen Hypergraphen ohne Abweichung. Der Haken: Die selbst entworfene Färbungs-DP gewinnt nur in der Hälfte der größeren Vergleichsfälle gegen Greedy, und alles ist Nachbau, kein neuer Beweis.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle dreizehn Stücke, entlang der Frage, was an Ihrem Netz im Vordergrund steht: Erreichbarkeit, ein einzelner Ausfall, ein Ressourcenkonflikt, Wichtigkeit, die Linkstruktur einer Website, Verwundbarkeit gegen viele Ausfälle, dünnbesetzte Gleichungssysteme oder eigene Forschung. Alle Antworten stützen sich auf Messungen in den Demos.
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 Stücke sind nicht alle gleichrangig (Zentralität und Härten sind Zusammenflüsse mehrerer Vorgänger, keine eigenständigen Blätter), und die Antworten gelten für die erzeugten Vehikel der Demos und die dort gemessenen Größen.
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.
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.