In diesem Artikel werden wir die Adjazenzmatrix zusammen mit ihrer Darstellung diskutieren.

c# enthält eine Zeichenfolge

Definition der Adjazenzmatrix

In der Graphentheorie ist eine Adjazenzmatrix eine dichte Methode zur Beschreibung der endlichen Graphenstruktur. Es ist die 2D-Matrix, die verwendet wird, um die Zuordnung zwischen den Diagrammknoten abzubilden.

Wenn ein Diagramm hat N Anzahl der Eckpunkte, dann ist die Adjazenzmatrix dieses Diagramms n x n , und jeder Eintrag der Matrix repräsentiert die Anzahl der Kanten von einem Scheitelpunkt zum anderen.

Eine Adjazenzmatrix wird auch als bezeichnet Verbindungsmatrix . Manchmal wird es auch als a bezeichnet Scheitelpunktmatrix .

Darstellung der Adjazenzmatrix

Wenn ein ungerichteter Graph G aus n Eckpunkten besteht, dann ist die Adjazenzmatrix eines Graphen n x n Matrix A = [aij] und definiert durch -

A_ij= 1 {wenn es einen Pfad von V gibt_ichzu V_J}

A_ij= 0 {Sonst}

Sehen wir uns einige wichtige Punkte in Bezug auf die Adjazenzmatrix an.

• Wenn es eine Kante zwischen Scheitelpunkt V gibt_ichund V_J, wobei i eine Zeile und j eine Spalte ist, dann der Wert von a_ij= 1.
• Wenn es keine Kante zwischen Scheitelpunkt V gibt_ichund V_J, dann ist der Wert von a_ij= 0.
• Wenn es im einfachen Diagramm keine Selbstschleifen gibt, sollte die Scheitelpunktmatrix (oder Adjazenzmatrix) Nullen in der Diagonale haben.
• Eine Adjazenzmatrix ist für einen ungerichteten Graphen symmetrisch. Es gibt an, dass der Wert im i^ThReihe und j^ThSpalte ist gleich dem Wert in j^ThReihe i^Th
• Wenn die Adjazenzmatrix mit sich selbst multipliziert wird und bei i ein Wert ungleich Null vorhanden ist^ThReihe und j^ThSpalte, dann gibt es die Route von V_ichzu V_J­­mit einer Länge, die 2 entspricht. Der Wert ungleich Null in der Adjazenzmatrix gibt an, dass die Anzahl unterschiedlicher Pfade vorhanden ist.

Hinweis: In einer Adjazenzmatrix bedeutet 0, dass zwischen zwei Knoten keine Assoziation besteht, während 1 bedeutet, dass zwischen zwei Knoten eine Assoziation besteht.

Wie erstelle ich eine Adjazenzmatrix?

Angenommen, es gibt ein Diagramm G mit N Anzahl der Scheitelpunkte, dann ist die Scheitelpunktmatrix (oder Adjazenzmatrix) gegeben durch -

javatierbar

A = a_elfA₁₂. . . . . A_1nA_{einundzwanzig}A₂₂. . . . . A_2n. . . . . . . . . A_n1A_n2. . . . . A_nn

Wo die a_ijentspricht der Anzahl der Kanten vom Scheitelpunkt i bis j. Wie oben erwähnt, ist die Adjazenzmatrix für einen ungerichteten Graphen symmetrisch, also für einen ungerichteten Graphen a_ij= a_Hihi.

Wenn die Diagramme einfach sind und es keine Gewichtungen an den Kanten oder mehreren Kanten gibt, sind die Einträge der Adjazenzmatrix 0 und 1. Wenn es keine Selbstschleifen gibt, sind die diagonalen Einträge der Adjazenzmatrix 0.

Sehen wir uns nun die Adjazenzmatrix für einen ungerichteten Graphen und für gerichtete Graphen an.

Adjazenzmatrix für einen ungerichteten Graphen

In einem ungerichteten Graphen sind den Kanten keine Richtungen zugeordnet. Wenn in einem ungerichteten Graphen eine Kante zwischen Scheitelpunkt A und Scheitelpunkt B vorhanden ist, können die Scheitelpunkte sowohl von A nach B als auch von B nach A übertragen werden.

Betrachten wir den folgenden ungerichteten Graphen und versuchen, die Adjazenzmatrix davon zu erstellen.

Zeichenfolge enthält

Im Diagramm sehen wir, dass es keine Selbstschleife gibt, sodass die diagonalen Einträge der angrenzenden Matrix 0 sind. Die Adjazenzmatrix des obigen Diagramms lautet:

Adjazenzmatrix für einen gerichteten Graphen

In einem gerichteten Graphen bilden Kanten ein geordnetes Paar. Kanten stellen einen bestimmten Pfad von einem Scheitelpunkt A zu einem anderen Scheitelpunkt B dar. Knoten A wird als Anfangsknoten bezeichnet, während Knoten B als Endknoten bezeichnet wird.

Betrachten wir den folgenden gerichteten Graphen und versuchen, die Adjazenzmatrix davon zu erstellen.

Im obigen Diagramm sehen wir, dass es keine Selbstschleife gibt, sodass die diagonalen Einträge der angrenzenden Matrix 0 sind. Die Adjazenzmatrix des obigen Diagramms lautet:

Eigenschaften der Adjazenzmatrix

Einige der Eigenschaften der Adjazenzmatrix sind wie folgt aufgeführt:

• Eine Adjazenzmatrix ist eine Matrix, die Zeilen und Spalten enthält, die zur Darstellung eines einfachen beschrifteten Diagramms mit den Zahlen 0 und 1 an der Position (V) verwendet werden_ICH, IN_J), abhängig von der Bedingung, ob die beiden V_{ich ­} und V_Jliegen nebeneinander.
• Wenn für einen gerichteten Graphen eine Kante zwischen dem Scheitelpunkt i oder V vorhanden ist_ichzum Scheitelpunkt j oder V_J, dann ist der Wert von A[V_ich][IN_J] = 1, andernfalls ist der Wert 0.
• Für einen ungerichteten Graphen, wenn es eine Kante zwischen dem Scheitelpunkt i oder V gibt_ichzum Scheitelpunkt j oder V_J, dann ist der Wert von A[V_ich][IN_J] = 1 und A[V_J][IN_ich] = 1, andernfalls ist der Wert 0.

Sehen wir uns einige Fragen der Adjazenzmatrix an. Die folgenden Fragen beziehen sich auf die gewichteten ungerichteten und gerichteten Diagramme.

HINWEIS: Ein Graph wird als gewichteter Graph bezeichnet, wenn jeder Kante eine positive Zahl zugewiesen ist, die als Gewicht der Kante bezeichnet wird.

Frage 1 - Wie sieht die Adjazenzmatrix für den folgenden ungerichteten gewichteten Graphen aus?

Lösung - In der gegebenen Frage gibt es keine Selbstschleife, daher ist klar, dass die diagonalen Einträge der angrenzenden Matrix für den obigen Graphen 0 sind. Der obige Graph ist ein gewichteter ungerichteter Graph. Die Gewichte an den Diagrammkanten werden als Einträge der Adjazenzmatrix dargestellt.

Die Adjazenzmatrix des obigen Diagramms lautet:

Frage 2 - Wie sieht die Adjazenzmatrix für den unten dargestellten gerichteten gewichteten Graphen aus?

Lösung - In der gegebenen Frage gibt es keine Selbstschleife, daher ist klar, dass die Diagonaleinträge der angrenzenden Matrix für den obigen Graphen 0 sind. Der obige Graph ist ein gewichteter gerichteter Graph. Die Gewichte an den Kanten des Diagramms werden als Einträge der Adjazenzmatrix dargestellt.

Die Adjazenzmatrix des obigen Diagramms lautet:

10 ml zu Unzen

Ich hoffe, dass dieser Artikel für Sie hilfreich ist, um die Adjazenzmatrix zu verstehen. Hier haben wir die Adjazenzmatrix sowie ihre Erstellung und Eigenschaften besprochen. Wir haben auch die Bildung einer Adjazenzmatrix auf gerichteten oder ungerichteten Graphen diskutiert, unabhängig davon, ob sie gewichtet sind oder nicht.