Adjazenzmatrix-Rechner

Adjazenzmatrix-Rechner

Der Adjazenzmatrix-Rechner ist ein Hilfsmittel der Graphentheorie, das zwischen den drei kanonischen Graphendarstellungen – Adjazenzmatrix, Kantenliste und Adjazenzliste – konvertiert und das Ergebnis durch Strukturanalysen bereichert: Gradfolge, Graphendichte, zusammenhängende Komponenten und Matrixpotenzen. Er erkennt automatisch, ob Ihre Eingabe einen gerichteten oder ungerichteten Graphen beschreibt, und erstellt neben jedem Ergebnis eine Live-SVG-Visualisierung.

Was ist eine Adjazenzmatrix?

Gegeben sei ein Graph G = (V, E) mit n Knoten. Seine Adjazenzmatrix ist die quadratische n × n-Matrix A, deren Eintrag A[i][j] gleich 1 ist, wenn eine Kante vom Knoten i zum Knoten j existiert, und ansonsten 0.

Für einen ungerichteten Graphen ist die Adjazenzmatrix immer symmetrisch: Jede Kante {u, v} trägt sowohl zu A[u][v] = 1 als auch zu A[v][u] = 1 bei. Bei einem gerichteten Graphen (Digraph) kann die Matrix asymmetrisch sein, was die Richtung jedes Bogens widerspiegelt.

Drei Darstellungen — Wählen Sie, was zu Ihrem Problem passt

Berechnete Kennzahlen

Gradfolge

Für ungerichtete Graphen ist der Grad eines Knotens die Anzahl der an ihn angrenzenden Kanten (wobei Selbstschleifen doppelt zählen). Bei gerichteten Graphen hat jeder Knoten einen In-Grad (eingehende Bögen) und einen Out-Grad (ausgehende Bögen). Die sortierte Liste der Grade ist eine klassische Grapheninvariante, die bei Isomorphietests und dem Erdős–Gallai-Theorem verwendet wird.

Graphendichte

Die Dichte misst, wie „voll“ ein Graph im Verhältnis zur maximal möglichen Anzahl von Kanten bei n Knoten ist.

Eine Dichte von 0 bedeutet keine Kanten, 1 bedeutet, dass der Graph vollständig ist, und Werte unter 0,1 weisen typischerweise auf einen dünnbesetzten Graphen hin, bei dem eine Adjazenzliste speichereffizienter als eine Matrix ist.

Zusammenhängende Komponenten

Eine zusammenhängende Komponente ist eine maximale Teilmenge von Knoten, bei der jedes Paar durch einen Pfad verbunden ist. Bei gerichteten Graphen gibt dieser Rechner schwach zusammenhängende Komponenten aus (unter Ignorierung der Pfeilrichtungen) – dieselben Teilmengen, die man erhielte, wenn man jeden Bogen als ungerichtete Kante behandelte.

Matrixpotenzen (A², A³ ... )

Ein grundlegendes Theorem der algebraischen Graphentheorie besagt, dass der (i, j)-Eintrag von A^k der Anzahl der Pfade der Länge genau k vom Knoten i zum Knoten j entspricht. Folglich:

• A²[i][i] entspricht dem Grad des Knotens i (ungerichtet), da ein 2-Schritt-Pfad von i zu sich selbst bedeutet: „zu einem Nachbarn gehen und zurück“.
• Die Spur von A³ geteilt durch 6 zählt die Dreiecke in einem ungerichteten Graphen.
• Ob Aⁿ⁻¹ Null-Einträge hat, sagt aus, ob der Graph zusammenhängend ist.

Akzeptierte Eingabeformate

1. Kantenliste

Eine Kante pro Zeile oder durch Komma getrennt. Jeder dieser Trenner funktioniert: A-B, A B, A,B, A->B, A--B. Verwenden Sie ->, wenn Sie eine gerichtete Interpretation erzwingen möchten.

2. Adjazenzliste

Eine Zeile pro Knoten in der Form Knoten: Nachbar1, Nachbar2, .... Die Reihenfolge spielt keine Rolle; fehlende Knoten werden automatisch aus den Nachbarschaftslisten hinzugefügt.

3. Adjazenzmatrix

Eine Zeile pro Zeile mit durch Leerzeichen oder Komma getrennten 0/1-Werten. Die Matrix muss quadratisch sein. Optional können Sie benutzerdefinierte Labels im Feld 'Matrix-Labels' angeben (andernfalls wird A, B, C… verwendet).

So verwenden Sie diesen Rechner

1. Wählen Sie ein Eingabeformat über den Tab-Selector: Kantenliste, Adjazenzliste oder Adjazenzmatrix.
2. Fügen Sie Ihren Graphen ein oder tippen Sie ihn ein. Bei der Matrix-Eingabe können Sie optionale Labels hinzufügen.
3. Wählen Sie den Graphentyp — lassen Sie ihn auf 'Automatisch erkennen', und der Rechner leitet die Gerichtetheit aus Pfeilen (->) oder der Matrixsymmetrie ab. Erzwingen Sie 'Gerichtet' oder 'Ungerichtet', wenn Sie dies überschreiben möchten.
4. Klicken Sie auf 'Graph konvertieren & analysieren'. Die Ergebnisseite zeigt die Adjazenzmatrix, ein interaktives SVG, die anderen beiden Textdarstellungen, Gradstatistiken, zusammenhängende Komponenten und Pfadanzahl-Matrizen A² und A³, sofern der Graph klein genug ist.
5. Bewegen Sie den Mauszeiger über eine Matrixzeile oder einen Graphenknoten, um die passende Zeile/Spalte und die angrenzenden Kanten hervorzuheben – ein sofortiger visueller Beweis, dass jedes Format dieselbe Information kodiert.

Beispiel

Betrachten Sie einen ungerichteten Graphen mit den Knoten {A, B, C, D} und den Kanten AB, BC, CA, CD. Die Adjazenzmatrix ist:

Wichtige Fakten, die der Rechner ableitet:

• Symmetrisch? Ja – bestätigt ungerichtet.
• Gradfolge: (3, 2, 2, 1) – Knoten C ist das Zentrum (Hub).
• Dichte: 2·4 / (4·3) = 0,667 – ein mäßig dichter Graph.
• Zusammenhängend? Ja, eine einzige Komponente.
• Dreiecke: genau eines (A–B–C), wie durch tr(A³) = 6 bestätigt wird.

Häufige Anwendungen

• Soziale Netzwerkanalyse — Freundschafts- / Follower-Graphen, Zentralität.
• Web- & Zitationsgraphen — PageRank und HITS arbeiten direkt auf A und A^T.
• Routing & Netzwerke — Kürzester Pfad, Min-Cut, Max-Flow.
• Chemie — Molekülgraphen mit Atomen als Knoten und Bindungen als Kanten.
• Zeitplanung & Abhängigkeiten — gerichtete azyklische Graphen (DAGs) in Build-Systemen.
• Markow-Ketten — aus Graphen abgeleitete zeilenstochastische Matrizen kodieren Übergangswahrscheinlichkeiten.

Häufig gestellte Fragen

Was ist eine Adjazenzmatrix?

Eine Adjazenzmatrix ist eine quadratische n × n-Matrix zur Darstellung eines endlichen Graphen. Jede Zelle A[i][j] ist 1, wenn eine Kante von Knoten i zu Knoten j existiert, und ansonsten 0. Bei ungerichteten Graphen ist die Matrix symmetrisch, also A[i][j] = A[j][i]. Die Matrix ermöglicht es, in konstanter Zeit zu prüfen, ob zwei Knoten verbunden sind, und Matrixpotenzen kodieren die Anzahl der Pfade zwischen Knoten.

Wie erkenne ich an der Adjazenzmatrix, ob ein Graph gerichtet ist?

Wenn die Adjazenzmatrix symmetrisch ist, also A[i][j] gleich A[j][i] für jedes Indexpaar ist, ist der Graph ungerichtet. Gibt es mindestens ein Paar, bei dem A[i][j] von A[j][i] abweicht, ist der Graph gerichtet. Dieser Rechner führt diese Symmetrieprüfung automatisch durch, wenn Sie die Option 'Automatisch erkennen' wählen.

Was stellt die k-te Potenz einer Adjazenzmatrix dar?

Der Eintrag (i, j) von A^k zählt die Anzahl der Pfade der exakten Länge k vom Knoten i zum Knoten j. Beispielsweise ist A²[i][j] die Anzahl der 2-Schritt-Pfade, was bei ungerichteten Graphen der Anzahl der gemeinsamen Nachbarn zwischen i und j entspricht. Diese Eigenschaft wird in Algorithmen zur Dreieckszählung, Erreichbarkeit und PageRank-Berechnungen verwendet.

Was ist die Graphendichte?

Die Graphendichte ist das Verhältnis der Anzahl der vorhandenen Kanten zur maximal möglichen Anzahl von Kanten. Für einen ungerichteten einfachen Graphen mit n Knoten gilt: Dichte = 2m / (n(n-1)). Für einen gerichteten Graphen gilt: Dichte = m / (n(n-1)). Eine Dichte nahe 0 bedeutet einen dünnbesetzten Graphen; eine Dichte von 1 bedeutet einen vollständigen Graphen.

Wie unterscheidet sich eine Adjazenzmatrix von einer Adjazenzliste?

Eine Adjazenzmatrix speichert Verbindungen für jedes Knotenpaar mit n² Bits, was die Nachbarsuche O(1) macht, aber den Speicherbedarf auf O(n²) erhöht. Eine Adjazenzliste speichert nur die tatsächlichen Nachbarn jedes Knotens, was O(n + m) Speicher benötigt – deutlich weniger bei dünnbesetzten Graphen –, aber die Nachbarsuche erfordert einen linearen Scan. Matrizen sind besser für dichte Graphen und Matrix-Algebra; Listen sind besser für dünne Graphen und Traversierungsalgorithmen wie BFS/DFS.

Kann dieses Tool gewichtete Graphen verarbeiten?

Der aktuelle Rechner konzentriert sich auf ungewichtete Adjazenzmatrizen mit 0/1-Einträgen. Wenn Sie eine Matrix mit numerischen Gewichten ungleich Null einfügen, wird jede Zelle ungleich Null für die Strukturanalyse als 1 behandelt. Für Berechnungen in gewichteten Graphen, wie z. B. kürzeste Pfade, sollten Sie ein spezielles Tool für gewichtete Graphen nutzen.

Weiterführende Literatur

• Adjazenzmatrix — Wikipedia
• Gradfolge — Wikipedia
• Graphendichte — Wikipedia
• Zusammenhangskomponenten — Wikipedia