Vertex (Graphentheorie) - Vertex (graph theory)

Ein Graph mit 6 Knoten und 7 Kanten, wobei die Knotennummer 6 ganz links ein Blattknoten oder ein hängender Knoten ist

In der Mathematik und genauer in der Graphentheorie ist ein Knoten (Plural- Knoten ) oder Knoten die grundlegende Einheit, aus der Graphen gebildet werden: Ein ungerichteter Graph besteht aus einer Menge von Knoten und einer Menge von Kanten (ungeordnete Knotenpaare), während Ein gerichteter Graph besteht aus einer Menge von Scheitelpunkten und einer Menge von Bögen (geordnete Scheitelpunktpaare). In einem Diagramm eines Graphen wird ein Scheitelpunkt normalerweise durch einen Kreis mit einer Beschriftung dargestellt, und eine Kante wird durch eine Linie oder einen Pfeil dargestellt, der sich von einem Scheitelpunkt zum anderen erstreckt.

Aus Sicht der Graphentheorie werden Vertices als merkmallose und unteilbare Objekte behandelt , obwohl sie je nach Anwendung, aus der der Graph stammt, eine zusätzliche Struktur haben können; ein semantisches Netzwerk ist beispielsweise ein Graph, in dem die Scheitelpunkte Konzepte oder Klassen von Objekten darstellen.

Die beiden Eckpunkte, die eine Kante bilden, werden als Endpunkte dieser Kante bezeichnet, und die Kante fällt auf die Eckpunkte. Eine Ecke w heißt benachbart zu einer anderen Ecke v, wenn der Graph eine Kante ( v , w ) enthält. Die Umgebung einer Ecke v ist ein induzierter Teilgraph des Graphen, der von allen an v angrenzenden Ecken gebildet wird  .

Arten von Scheitelpunkten

Ein kleines Beispielnetzwerk mit 8 Knoten und 10 Kanten.
Beispielnetzwerk mit 8 Knoten (von denen einer isoliert ist) und 10 Kanten.

Der Grad eines Knotens, der in einem Graphen mit 𝛿(v) bezeichnet wird, ist die Anzahl der auf ihn einfallenden Kanten. Ein isolierter Knoten ist ein Knoten mit Grad Null; dh ein Scheitelpunkt, der kein Endpunkt einer Kante ist (das Beispielbild zeigt einen isolierten Scheitelpunkt). Ein Blattscheitel (auch hängender Scheitel ) ist ein Scheitel mit Grad eins. In einem gerichteten Graphen kann man den Außengrad (Anzahl der ausgehenden Kanten), bezeichnet mit 𝛿 + (v), von dem Innengrad (Anzahl der ankommenden Kanten), bezeichnet mit 𝛿 (v), unterscheiden; ein Quell-Scheitelpunkt ist ein Scheitelpunkt mit In-Grad-Null, während ein Senken-Scheitelpunkt ein Scheitelpunkt mit Außengrad Null ist. Ein simplizialer Knoten ist einer, dessen Nachbarn eine Clique bilden : alle zwei Nachbarn sind benachbart. Ein universeller Knoten ist ein Knoten, der an jeden anderen Knoten im Graphen angrenzt.

Ein geschnittener Scheitelpunkt ist ein Scheitelpunkt, dessen Entfernung den verbleibenden Graphen trennen würde; Ein Scheitelpunkttrenner ist eine Sammlung von Scheitelpunkten, deren Entfernung den verbleibenden Graphen in kleine Teile zerlegen würde. Ein mit k Knoten verbundener Graph ist ein Graph, bei dem das Entfernen von weniger als k Knoten immer den verbleibenden Graphen verbunden lässt. Ein unabhängiger Satz ist ein Satz von Scheitelpunkten, von denen keine zwei benachbart sind, und eine Scheitelpunktüberdeckung ist ein Satz von Scheitelpunkten, der mindestens einen Endpunkt jeder Kante im Graphen enthält. Der Scheitelpunktraum eines Graphen ist ein Vektorraum mit einem Satz von Basisvektoren, die den Scheitelpunkten des Graphen entsprechen.

Ein Graph ist knotentransitiv, wenn er Symmetrien hat, die jeden Knoten auf einen anderen Knoten abbilden. Im Zusammenhang mit Graphenumeration und Graphisomorphismus ist es wichtig, zwischen markierten Ecken und unbeschrifteten Ecken zu unterscheiden . Ein beschrifteter Scheitelpunkt ist ein Scheitelpunkt, dem zusätzliche Informationen zugeordnet sind, die es ermöglichen, ihn von anderen gekennzeichneten Scheitelpunkten zu unterscheiden; zwei Graphen können nur dann als isomorph angesehen werden, wenn die Korrespondenz zwischen ihren Knoten Knoten mit gleichen Labels paart. Ein nicht beschrifteter Scheitelpunkt ist ein Scheitelpunkt, der für jeden anderen Scheitelpunkt nur auf der Grundlage seiner Nachbarschaften im Diagramm und nicht auf der Grundlage zusätzlicher Informationen ersetzt werden kann.

Scheitelpunkte in Graphen sind analog zu den Scheitelpunkten von Polyedern , aber nicht mit diesen identisch : Das Skelett eines Polyeders bildet einen Graphen, dessen Scheitelpunkte die Scheitelpunkte des Polyeders sind, aber Polyederscheitelpunkte haben eine zusätzliche Struktur (ihre geometrische Lage), das heißt wird in der Graphentheorie nicht angenommen. Die Eckenfigur einer Ecke in einem Polyeder ist analog zur Nachbarschaft einer Ecke in einem Graphen.

Siehe auch

Verweise

  • Gallo, Giorgio; Pallotino, Stefano (1988). "Kürzeste Pfadalgorithmen". Annalen des Operations Research . 13 (1): 1–79. doi : 10.1007/BF02288320 .
  • Berge, Claude , Théorie des graphes et ses Anwendungen . Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 S. (englische Ausgabe, Wiley 1961; Methuen & Co, New York 1962; Russisch, Moskau 1961; Spanisch, Mexiko 1962; Rumänisch, Bukarest 1969; Chinesisch, Shanghai 1963 ; Zweiter Druck der ersten englischen Ausgabe von 1962. Dover, New York 2001)
  • Chartrand, Gary (1985). Einführung in die Graphentheorie . New York: Dover. ISBN 0-486-24775-9.
  • Biggs, Norman; Lloyd, EH; Wilson, Robin J. (1986). Graphentheorie, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Graphentheorie . Lesen, Massachusetts: Addison-Wesley Publishing. ISBN 0-201-41033-8.
  • Harary, Frank; Palmer, Edgar M. (1973). Grafische Aufzählung . New York, akademische Presse. ISBN 0-12-324245-2.

Externe Links