< Zurück | Weiter | Inhalt >
Adjazenzmatrix: Scheitelpunkt zu Scheitelpunkt
Die Graphenfamilie argumentiert, dass eine der besten Möglichkeiten, sie in einer Matrix darzustellen, darin besteht, die Anzahl der Kanten zwischen zwei benachbarten Eckpunkten zu zählen.
Zwei Eckpunkte werden als benachbart oder Nachbar bezeichnet, wenn sie mindestens eine gemeinsame Kante unterstützen.
Beginnen wir mit Beispiel
Diagramm unten hat drei Eckpunkte. So machen wir eine Adjazenzmatrix der Größe 3 mal 3. Dann setzen wir den Namen der Eckpunkte auf die Seite der Matrix. Schauen Sie sich das Bild an und wir beginnen mit einer leeren Matrix. Es gibt nur die Namen der Eckpunkte
Um die Adjazenzmatrix zu füllen, schauen wir uns die name des Scheitelpunkts in Zeile und Spalte. Wenn diese Eckpunkte durch eine Kante oder mehr verbunden sind, zählen wir die Anzahl der Kanten und setzen diese Zahl als Matrixelement.
Vertex 
und Vertex 
hat eine gemeinsame Kante, wir sagen, dass Vertex 
und Vertex 
sind benachbart (Nachbar). Wir geben die Anzahl der Kanten in die Matrixzelle ein, die dem Scheitelpunkt 
und dem Scheitelpunkt 
.
Vertex 
und 
grenzt an eine Kante an. Daher geben wir die Anzahl der Kanten in die Matrixzelle ein, die dem Scheitelpunkt entsprechen 
und 
.
Ebenso Vertex 
und 
ist durch eine Kante verbunden. Daher geben wir die Anzahl der Kanten in die Matrixzelle ein, die dem Scheitelpunkt entsprechen 
und 
Es gibt keine andere Kante im Graphen, daher setzen wir den Rest der ungefüllten Zellen in die Matrix als Null
Die Matrix, um einen Graphen auf diese Weise darzustellen nennt sich Adjazenzmatrix .
Die Größe der Adjazenzmatrix entspricht der Anzahl der Eckpunkte im Diagramm. Es ist eine quadratische Matrix (dh die Anzahl der Zeilen entspricht der Anzahl der Spalten).
Die Adjazenzmatrix eines Graphen ist symmetrisch, weil sie keine Richtung hat. Zwei Eckpunkte derselben Kante können vom ersten zum zweiten oder vom zweiten zum ersten aufgerufen werden. Zum Beispiel Vertex 
und vertex 
hat eine gemeinsame Kante, dann Element (a, b) = 1 und Element (b, a) = 1.
Versuchen wir ein anderes Beispiel:
Können Sie die Adjazenzmatrix dieses Diagramms erstellen? Probieren Sie es zuerst aus, bevor Sie sich die Antwort unten ansehen.
Der Graph hat 3 Eckpunkte, also machen wir eine Matrixgröße 3 mal 3. Wir setzen den Namen der Eckpunkte auf die Seite der Matrix.
Schauen Sie sich nun den Scheitelpunkt an 
und Scheitelpunkt 
. Wie viele Kanten unterstützen die beiden Eckpunkte? Ein. Dann setzen wir diesen Wert in die Matrix
Schau dir Vertex an 
und Vertex 
. Wie viele Kanten unterstützen diese Eckpunkte? Kein. Dann setzen wir den Wert Null in die entsprechende Zelle in der Matrix
Als nächstes sehen Sie sich Vertex an 
und Vertex 
. Wie viele Kanten unterstützen diese Eckpunkte? Zwei. Dann geben wir die Matrix in
Da es keine andere Kante im Graphen gibt, können wir die leere Zelle mit Nullen füllen. So haben wir die Antwort
Einige von Ihnen fragen sich vielleicht nach dem diagonalen Teil der Matrix, sind diese Zellen immer Null? Nein, wenn Sie feststellen, dass das Diagramm in einigen Scheitelpunkten eine Schleife enthält, können Sie das diagonale Element der Adjazenzmatrix mit der Anzahl der Schleifen füllen.
Wenn ein Graph einen Scheitelpunkt hat, der mit keinem anderen Scheitelpunkt verbunden ist, ist die Adjazenzmatrix, die diesem einzelnen Scheitelpunkt entspricht, Null.
Bitte üben Sie, um das Diagramm unten in der Adjazenzmatrix darzustellen.
(Siehe die Antwort auf der vorherigen Seite )
Können Sie angesichts der Adjazenzmatrix das Diagramm zurückzeichnen?
Überprüfen Sie die Beispielanwendung der Graphentheorie im Q-Learning-Tutorial
< Zurück / Weiter / Inhalt >