Der Graph besteht aus Knoten und Kanten. Die Scheitelpunkte sind durch Kanten nach einer bestimmten Eigenschaft verbunden - der Inzidenzrelation, die die Menge der Kanten definiert. In diesem Fall können sich Schleifen und isolierte Scheitelpunkte bilden.
Anleitung
Schritt 1
Gegeben sei die Menge der Kanten des Graphen und die Beziehung, entlang derer es möglich ist, eine Kante von einem Knoten zum anderen zu ziehen. Als Beispiel, die Menge der Ecken {1, 2, 3, 4, 5, 6, 7, 8}, zwei Ecken x und y stehen im Verhältnis x + y <8.
Schritt 2
Erstellen Sie eine Vertex-Adjazenz-Matrix. Erstellen Sie dazu eine quadratische Tabelle. Die Anzahl der Zeilen und Spalten in der Tabelle stimmt mit der Anzahl der Scheitelpunkte überein. Dann setze 1 an den Schnittpunkt der i-ten Zeile und der j-ten Spalte, wenn die Eckpunkte i und j das gegebene Verhältnis erfüllen. Setzen Sie 0 an den Schnittpunkt der i-ten Zeile und der j-ten Spalte, wenn das Verhältnis für die entsprechenden Elemente nicht erfüllt ist.
In unserem Beispiel wird die erste Zeile wie folgt ausgefüllt:
1 + 1 <8, es gibt also 1 am Schnittpunkt der 1. Reihe und 1. Spalte
1 + 2 <8, wieder 1
1 + 3 <8, wieder 1
1 + 7 <8, falsche Ungleichung, daher ist dieses Element der Tabelle 0
1 + 8 <8, wieder 0
Schritt 3
Um die Anzahl der Kanten herauszufinden, zählen Sie die Anzahl der Einsen in der Adjazenzmatrix, ohne die Kanten zu duplizieren.
Im Beispiel wurde eine symmetrische Matrix erhalten, also haben wir zuerst die über der Hauptdiagonale der Matrix (blau markiert) und dann die auf der Hauptdiagonale (rot markiert) gezählt. Die Gesamtzahl der Rippen beträgt 12.
Schritt 4
Erstellen Sie eine Matrix von Ereignissen (Kanten). Zeichnen Sie dazu eine Tabelle, deren Anzahl der Zeilen gleich der Anzahl der Scheitelpunkte im Diagramm und die Anzahl der Spalten gleich der Anzahl der Kanten ist. Setzen Sie Einheiten auf die Linien, die durch eine Kante verbunden werden. Die Kanten, die vom Scheitelpunkt dorthin führen, werden Schleifen genannt und werden am Ende der Matrix hinzugefügt. In den den Schleifen entsprechenden Spalten gibt es im Gegensatz zu den restlichen Kanten nur eine Einheit.
Schritt 5
Zeichnen Sie nun eine Grafik. Legen Sie die Scheitelpunkte beliebig auf das Papier und verbinden Sie sie mit den Kanten mithilfe der konstruierten Tabellen. Knoten, die nicht durch Kanten verbunden sind, werden isoliert genannt.
