Das Diagramm besteht aus Eckpunkten und Kanten. Die Eckpunkte sind durch Kanten gemäß einer bestimmten Eigenschaft verbunden - der Inzidenzbeziehung, die die Menge der Kanten definiert. In diesem Fall können sich Schleifen und isolierte Eckpunkte bilden.
Bedienungsanleitung
1
Es sei eine Menge von Kanten eines Graphen gegeben und eine Beziehung gegeben, durch die man eine Kante von einem Scheitelpunkt zu einem anderen zeichnen kann. Als Beispiel für die Menge der Eckpunkte {1, 2, 3, 4, 5, 6, 7, 8} stehen die beiden Eckpunkte x und y im Verhältnis x + y <8.
2
Erstellen Sie eine Scheitelpunkt-Adjazenzmatrix. Erstellen Sie dazu eine quadratische Tabelle. Die Anzahl der Zeilen und Spalten in der Tabelle entspricht der Anzahl der Scheitelpunkte. Setzen Sie dann 1 an den Schnittpunkt der i-ten Zeile und der j-ten Spalte, wenn die Eckpunkte i und j das angegebene 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 gefüllt:
1 + 1 <8, also am Schnittpunkt der 1. Zeile und 1. Spalte 1
1 + 2 <8, wieder 1
1 + 3 <8, wieder 1
…
1 + 7 <8, falsche Ungleichung, dann ist dieses Tabellenelement 0
1 + 8 <8, wieder 0
3
Um die Anzahl der Kanten zu ermitteln, zählen Sie die Anzahl der Einheiten in der Adjazenzmatrix, ohne die Kanten zu zerreißen.
In dem Beispiel wurde eine symmetrische Matrix erhalten, daher wurden zuerst die Einheiten über der Hauptdiagonale der Matrix (blau markiert) und dann die Einheiten auf der Hauptdiagonale (rot markiert) berechnet. Die Gesamtzahl der Rippen beträgt 12.
4
Erstellen Sie eine Matrix von Vorfällen (Kanten). Zeichnen Sie dazu eine Tabelle. Die Anzahl der Zeilen entspricht der Anzahl der Scheitelpunkte des Diagramms und die Anzahl der Spalten entspricht der Anzahl der Kanten. Setzen Sie die Einheiten in die Linien, die durch eine Kante verbunden werden. Die von oben nach oben führenden Kanten werden als Schleifen bezeichnet und am Ende der Matrix hinzugefügt. In den Spalten, die den Schleifen entsprechen, gibt es im Gegensatz zu den anderen Kanten nur eine Einheit.
5
Zeichnen Sie nun eine Grafik. Ordnen Sie die Eckpunkte beliebig auf Papier an und verbinden Sie sie mit den Kanten mithilfe der konstruierten Tabellen. Scheitelpunkte, die nicht durch Kanten verbunden sind, werden als isoliert bezeichnet.
beachten Sie
Die Abbildung zeigt die Rippen zur Verdeutlichung. Normalerweise wird das Gewicht der Rippe über die Rippe geschrieben.
