Was bedeutet die Gradfolge eines Graphen?

Der Grad eines Knotens ist die Anzahl der Kanten, die an diesem Knoten anliegen. Die Gradfolge ist die sortierte Liste der Knotengrade aller Knoten. Bei gerichteten Graphen unterscheidet man Eingangsgrad (In-degree) und Ausgangsgrad (Out-degree). Die Summe aller Grade ist immer gleich der doppelten Kantenanzahl (Handschlaglemma).

Was gibt A² (die Matrizenpotenz) an?

Das Element (A²)_ij gibt die Anzahl der Wege der Länge 2 zwischen Knoten i und Knoten j an. Allgemein gibt (Aᵏ)_ij die Anzahl der Wege der Länge k an. Dies ist nützlich zur Analyse von Verbindungen und Erreichbarkeit in Netzwerken und Graphen.

🕸️

Adjazenzmatrix-Rechner

Kantenliste zu Matrix · Gradfolge · Graphdichte · Matrixpotenzen · Gerichtet & Ungerichtet

Graphdaten eingeben

Kantenliste oder Adjazenzliste eingeben

Kantenliste (eine Kante pro Zeile: "Knoten1 Knoten2" oder "Knoten1 Knoten2 Gewicht")

Beispiel: "1 2" bedeutet eine Kante von Knoten 1 zu Knoten 2

Knoten

—

Kanten

—

Graphdichte

—

Max. Grad

—

Adjazenzmatrix

Gradfolge der Knoten

Knoten	Grad	Eingangsgrad	Ausgangsgrad

Matrixpotenz A¹

Was ist eine Adjazenzmatrix?

Eine Adjazenzmatrix ist eine der wichtigsten Darstellungsformen eines Graphen in der Graphentheorie und Informatik. Sie ist eine quadratische n×n-Matrix, wobei n die Anzahl der Knoten (Vertices) des Graphen ist. Jedes Element a_ij der Matrix gibt an, ob eine Kante zwischen Knoten i und Knoten j existiert.

Ungerichtete vs. gerichtete Graphen

Bei ungerichteten Graphen ist die Adjazenzmatrix symmetrisch: a_ij = a_ji, da eine Kante in beide Richtungen verläuft. Bei gerichteten Graphen (Digraphen) ist a_ij ≠ a_ji möglich — eine Kante von i nach j bedeutet nicht zwingend eine Kante von j nach i.

Vergleich: Adjazenzmatrix vs. Adjazenzliste

Eigenschaft	Adjazenzmatrix	Adjazenzliste
Speicherbedarf	O(n²)	O(n + m)
Kantenabfrage	O(1)	O(Grad)
Alle Nachbarn	O(n)	O(Grad)
Geeignet für	Dichte Graphen	Sparse Graphen

Häufig gestellte Fragen

Wie konvertiere ich eine Kantenliste in eine Adjazenzmatrix?

Erstelle eine n×n-Matrix mit Nullen. Für jede Kante (u, v) in der Kantenliste setze a[u][v] = 1. Bei ungerichteten Graphen auch a[v][u] = 1 setzen. Bei gewichteten Graphen schreibe das Gewicht statt der 1. Unser Rechner erledigt diesen Prozess automatisch für dich.