Wie man eine Adjazenzmatrix eines orientierten Graphen konstruiert - Anweisungen und Beispiele

Die Adjazenzmatrix spielt eine wichtige Rolle in der Graphentheorie und ermöglicht die Darstellung von Beziehungen zwischen Scheitelpunkten. Es ist eine der wichtigsten Möglichkeiten, einen orientierten Graphen in Mathematik und Informatik darzustellen. In diesem Artikel werden wir uns ansehen, wie man eine Adjazenzmatrix erstellt und verwendet.

Die Adjazenzmatrix ist eine quadratische Tabelle mit der Größe n x n, wobei n die Anzahl der Scheitelpunkte im Diagramm ist. Jedes Element der Matrix gibt an, ob eine Kante zwischen den beiden Scheitelpunkten vorhanden ist oder fehlt. Wenn eine Kante vorhanden ist, ist der Elementwert 1, andernfalls 0. Die Adjazenzmatrix kann auch für Gewichtungsdiagramme verwendet werden, bei denen die Matrixelemente Zahlen sind, die das Gewicht der Kante angeben.

Um eine Adjazenzmatrix eines orientierten Graphen zu erstellen, wird jedem Stützpunkt eine eindeutige Zahl von 1 bis n zugewiesen. Es wird eine quadratische Matrix mit der Größe n x n erstellt, wobei alle Elemente 0 sind. Dann gehen wir durch jede Kante des Diagramms und setzen für jedes Scheitelpunktpaar, zu dem es vorkommt, den Wert auf 1 in der entsprechenden Zelle der Matrix.

Hier ist ein Beispiel für einen orientierten Graphen und seine Adjazenzmatrix:

1 2 3 4 51 0 1 0 1 02 1 0 1 0 03 0 0 0 0 14 0 0 1 0 05 1 0 0 1 0

In diesem Beispiel besteht das Diagramm aus 5 Stützpunkten mit den folgenden Kanten: (1, 2), (1, 4), (2, 1), (2, 3), (3, 5), (4, 3) und (5, 1). Die Adjazenzmatrix spiegelt diese Beziehungen mit Einsen und Nullen wider.

Die Verwendung einer Adjazenzmatrix ermöglicht es Ihnen, Informationen über die Struktur eines Diagramms bequem zu speichern und verschiedene Operationen durchzuführen, z. B. das Finden von Stützpunktnachbarn, die Überprüfung auf das Vorhandensein oder Fehlen einer Kante usw. Sie können diese Art der Diagrammdarstellung verwenden, um verschiedene Aufgaben in der Informatik, Computergrafik, Linguistik, Transportlogistik und anderen Bereichen der Wissenschaft und Technologie zu lösen.

Was ist ein orientierter Graph?

In einem orientierten Diagramm kann jeder Scheitelpunkt mehrere ausgehende und eingehende Kanten haben. Außerdem kann für jede Kante eine Markierung definiert werden, die das Bindungsmerkmal zwischen den Stützpunkten beschreibt.

Sie ermöglichen es, Verbindungen zwischen Objekten oder Ereignissen zu analysieren und darzustellen sowie Prozesse und Interaktionen in Systemen zu modellieren.

Warum brauche ich eine Adjazenzmatrix?

Eine Adjazenzmatrix ist eine quadratische Tabelle, in der Zeilen und Spalten den Eckpunkten eines Diagramms entsprechen. Der Wert in der Zelle (i, j) der Matrix gibt das Vorhandensein (oder Fehlen) einer Kante zwischen den Scheitelpunkten i und j sowie die Richtung an, wenn der Graph ausgerichtet ist.

Mithilfe einer Adjazenzmatrix können Sie schnell Informationen zu Stützpunktbeziehungen finden, z. B. die Anzahl der ein- und ausgehenden Kanten an jedem Stützpunkt ermitteln, nach Kanten zwischen bestimmten Stützpunkten suchen oder nach Nachbarn eines bestimmten Stützpunkts suchen.

Darüber hinaus ist die Adjazenzmatrix nützlich, um Graphen zu analysieren und nach bestimmten Mustern oder Strukturen wie Schleifen, Pfaden, Konnektivitätskomponenten und anderen zu suchen. Es wird auch häufig in Algorithmen verwendet, um den kürzesten Weg oder Transportprobleme zu finden.

Insgesamt ist die Adjazenzmatrix ein wichtiges Werkzeug für die Arbeit mit Graphen, und ihre Verwendung erleichtert die Analyse und Manipulation von Daten. Dank seiner benutzerfreundlichen Struktur und seiner Benutzerfreundlichkeit ist die Adjazenzmatrix ein unverzichtbares Werkzeug für die Erforschung und Arbeit mit orientierten Graphen.

Schritte zum Erstellen einer Adjazenzmatrix

Das Erstellen einer Adjazenzmatrix eines orientierten Graphen erfolgt in den folgenden Schritten:

1. Bestimmen Sie die Anzahl der Scheitelpunkte im Diagramm. In der Adjazenzmatrix entspricht jeder Scheitelpunkt einer Zeile und Spalte.
2. Erstellen Sie eine quadratische Matrix mit der Größe NxN, wobei N die Anzahl der Scheitelpunkte im Diagramm ist. Zunächst werden alle Elemente der Matrix mit Nullen gefüllt.
3. Markieren Sie für jede Kante (i, j), wobei i der Startscheitelpunkt und j der Endscheitelpunkt ist, das Element der Adjazenzmatrix am Schnittpunkt der i-ten Zeile und der j-ten Spalte mit dem Wert 1.

Nehmen wir an, wir haben einen orientierten Graph mit 4 Stützpunkten und folgenden Kanten: (1, 2), (1, 3), (3, 2), (4, 3).

Zuerst bestimmen wir die Anzahl der Scheitelpunkte - 4.

Erstellen Sie dann eine Adjazenzmatrix in der Größe 4x4:

| 1 2 3 4------------1 | 0 0 0 02 | 0 0 0 03 | 0 0 0 04 | 0 0 0 0

Markieren Sie dann die Matrixelemente, die den Kanten entsprechen:

| 1 2 3 4------------1 | 0 1 1 02 | 0 0 0 03 | 0 1 0 04 | 0 0 1 0

So haben wir eine Adjazenzmatrix für einen gegebenen orientierten Graphen erhalten.

Schritt 1: Festlegen der Eckpunkte des Diagramms

Die Eckpunkte eines Diagramms können abhängig von einer bestimmten Aufgabe oder einem bestimmten Fachgebiet durch verschiedene Objekte dargestellt werden. Beispielsweise können im Diagramm für soziale Beziehungen Eckpunkte einzelne Personen sein und im Diagramm für das Straßennetz einzelne Straßenabschnitte oder Kreuzungen.

Sie können die Eckpunkte eines Diagramms angeben, indem Sie sie nummerieren oder bestimmte Zeichen oder Buchstaben verwenden. Die Scheitelpunktnummerierung beginnt normalerweise bei eins und setzt sich bis zur Anzahl der Scheitelpunkte im Diagramm fort. In einem Diagramm mit fünf Stützpunkten können beispielsweise die Eckpunktzahlen zwischen 1 und 5 liegen.

Sie können auch Symbole oder Buchstaben verwenden, um die Eckpunkte eines Diagramms festzulegen. In diesem Fall wird jedem Eckpunkt des Diagramms ein bestimmtes Symbol oder ein bestimmter Buchstabe zugewiesen. Beispielsweise können Sie in einem Diagramm mit fünf Stützpunkten den Stützpunkten die Zeichen A, B, C, D, E zuweisen.

Das Festlegen der richtigen Nummerierung oder das Zuweisen von Symbolen zu den Eckpunkten eines Diagramms ist ein wichtiger Schritt beim Erstellen einer Adjazenzmatrix. Die Nummerierung muss konsistent und eindeutig sein, und die Symbole oder Buchstaben müssen sich voneinander unterscheiden, um Verwirrung beim Erstellen der Matrix zu vermeiden.

Nachdem Sie die Eckpunkte des Diagramms festgelegt haben, können Sie mit dem nächsten Schritt fortfahren, indem Sie die Kanten definieren und die Adjazenzmatrix füllen.

Schritt 2: Festlegen der Kanten des Diagramms

Die Kanten des Diagramms definieren die Beziehungen zwischen den Stützpunkten. Um eine Adjazenzmatrix eines orientierten Graphen zu erstellen, müssen Sie die Richtung jeder Kante festlegen. Dazu können Sie eine Kantenliste oder eine Adjazenztabelle verwenden.

Eine Kantenliste ist eine Liste von Scheitelpunktpaaren, die durch eine Kante verbunden sind. Beispielsweise kann eine Kante zwischen den Scheitelpunkten A und B als (A, B) geschrieben werden. Wenn der Graph Gewichte an den Kanten hat, können Sie diese auch angeben, z. B. als (A, B, 5), wobei 5 das Gewicht der Kante ist.

Die Adjazenztabelle ist ein zweidimensionales Array, bei dem jede Zeile und Spalte den Eckpunkten eines Diagramms entspricht. Wenn zwischen den Scheitelpunkten i und j eine Kante vorhanden ist, ist das entsprechende Tabellenelement nicht null. Im Falle eines orientierten Graphen wird das Element (i, j) von Null abweichen und das Element (j, i) ist Null.

Die Auswahl zwischen der Kantenliste und der Adjazenztabelle hängt von der jeweiligen Aufgabe und der Art des Diagramms ab. Beide Methoden sind gleichwertig und können verwendet werden, um eine Adjazenzmatrix eines orientierten Graphen zu konstruieren.

Schritt 3: Erstellen einer Adjazenzmatrix

Um eine Adjazenzmatrix eines orientierten Graphen zu erstellen, weisen wir dem Matrixelement am Schnittpunkt von Zeile und Spalte eine Einheit zu, wenn es eine Kante von Zeile zu Spalte gibt. Wenn keine Kanten zwischen den Stützpunkten vorhanden sind, wird dem Matrixelement Null zugewiesen.

Der Prozess der Erstellung einer Adjazenzmatrix kann als Tabelle dargestellt werden, in der die Eckpunkte horizontal und vertikal auch die Eckpunkte angeordnet sind. Der Wert des Matrixelements am Schnittpunkt von Zeile und Spalte gibt an, ob zwischen den entsprechenden Stützpunkten eine Kante vorhanden ist oder nicht.

Hier ist ein Beispiel für die Adjazenzmatrix eines orientierten Graphen:

Hier sind die Eckpunkte des Graphen mit den Buchstaben A, B und C gekennzeichnet. Matrixelemente weisen darauf hin, dass zwischen den entsprechenden Scheitelpunkten eine Kante (1) oder keine Kante (0) vorhanden ist. Zum Beispiel gibt es in diesem Beispiel eine Kante von Scheitelpunkt A nach Scheitelpunkt B, sodass das entsprechende Matrixelement den Wert 1 hat.

Das Erstellen einer Adjazenzmatrix kann ein nützlicher Schritt bei der Analyse und Visualisierung von Graphen sein, da Sie die Beziehungen zwischen den Stützpunkten in einer bequemen Form darstellen können.

Beispiele für die Konstruktion einer Adjazenzmatrix

Betrachten wir einige Beispiele für die Konstruktion einer Adjazenzmatrix für einen orientierten Graphen.

Beispiel 1:

Lassen Sie uns einen orientierten Graph mit 4 Eckpunkten haben. Die Kanten des Diagramms werden wie folgt dargestellt:

Kante 1: Scheitelpunkt 1 ist mit Scheitelpunkt 2 verbunden

Kante 2: Scheitelpunkt 2 ist mit Scheitelpunkt 3 verbunden

Kante 3: Scheitelpunkt 3 ist mit Scheitelpunkt 4 verbunden

Kante 4: Scheitelpunkt 4 ist mit Scheitelpunkt 1 verbunden

Die Adjazenzmatrix für dieses Diagramm sieht folgendermaßen aus:

Beispiel 2:

Lassen Sie uns einen orientierten Graph mit 3 Eckpunkten haben. Die Kanten des Diagramms werden wie folgt dargestellt:

Kante 1: Scheitelpunkt 1 ist mit Scheitelpunkt 2 verbunden

Kante 2: Scheitelpunkt 2 ist mit Scheitelpunkt 3 verbunden

Die Adjazenzmatrix für dieses Diagramm sieht folgendermaßen aus:

Beispiel 3:

Lassen Sie uns einen orientierten Graph mit 5 Eckpunkten haben. Die Kanten des Diagramms werden wie folgt dargestellt:

Kante 1: Scheitelpunkt 1 ist mit Scheitelpunkt 3 verbunden

Kante 2: Scheitelpunkt 2 ist mit Scheitelpunkt 4 verbunden

Kante 3: Scheitelpunkt 3 ist mit Scheitelpunkt 5 verbunden

Kante 4: Scheitelpunkt 5 ist mit Scheitelpunkt 1 verbunden

Die Adjazenzmatrix für dieses Diagramm sieht folgendermaßen aus:

1 | 0 | 0 | 1 | 0 | 1 |

2 | 0 | 0 | 0 | 1 | 0 |

3 | 0 | 0 | 0 | 0 | 1 |

4 | 0 | 0 | 0 | 0 | 0 |

5 | 1 | 0 | 0 | 0 | 0 |

Die beschriebenen Beispiele zeigen, wie eine Adjazenzmatrix für ein orientiertes Diagramm basierend auf Informationen über die Scheitelpunkte und Kanten eines Diagramms erstellt wird.

Beispiel 1: Adjazenzmatrix für ein einfaches Diagramm

Betrachten Sie für ein anschauliches Beispiel einen einfachen orientierten Graphen.

Lassen Sie uns einen Graph mit vier Ecken und fünf Kanten haben:

Gipfel: A, B, C, D

Rippen: AB, AC, AD, BC, CD

Um eine Adjazenzmatrix zu erstellen, stellen wir die Eckpunkte des Diagramms als Matrixindizes vor.

Dann würde die Adjazenzmatrix wie folgt aussehen:

In diesem Beispiel:

• Der Wert 1 am Schnittpunkt von Zeile und Spalte gibt an, dass eine Kante vom Scheitelpunkt, der der Zeile entspricht, zu dem Scheitelpunkt, der der Spalte entspricht, vorhanden ist.
• Der Wert 0 am Schnittpunkt von Zeile und Spalte gibt an, dass zwischen den angegebenen Stützpunkten keine Kante vorhanden ist.

In unserem Fall werden die Kanten AB, AC, AD, BC und CD in der Adjazenzmatrix wie folgt dargestellt:

• AB: Wert 1 in Zelle A-B der ausgehenden Kanten
• AC: Wert 1 in Zelle A-C der ausgehenden Kanten
• AD: wert 1 in Zelle A-D der ausgehenden Kanten
• BC: Wert 1 in Zelle B-C der ausgehenden Kanten
• CD: Wert 1 in Zelle C-D der ausgehenden Kanten

So ermöglicht die Adjazenzmatrix, die Beziehungen zwischen den Eckpunkten des Diagramms visuell darzustellen und das Vorhandensein und Fehlen von Kanten zu bestimmen.

Beispiel 2: Adjazenzmatrix für einen Graphen mit Schleifen

Betrachten Sie zum Beispiel das folgende Diagramm:

Gipfel: A, B, C

Rippen: (A, B), (B, B), (C, A), (C, C)

Lassen Sie uns eine Adjazenzmatrix für dieses Diagramm erstellen:

A B CA 0 1 0B 0 1 0C 1 0 1

Hier entspricht jede Zelle der Matrix einer Kante im Diagramm. Bedeutung 1 gibt an, dass zwischen den entsprechenden Scheitelpunkten eine Kante vorhanden ist, und 0 - keine Rippe. Zum Beispiel hat unser Diagramm Kanten (A, B), (B, B), (C, A), (C, C), daher haben diese Zellen einen Wert 1. Es gibt keine Kanten (A, C) und (B, C) im Diagramm, daher sind diese Zellen von Bedeutung 0.

Die Adjazenzmatrix für ein gegebenes Diagramm mit Schleifen würde also wie oben gezeigt aussehen.