Scheitelpunkt (Graphentheorie)

Für andere Verwendungen siehe Scheitelpunkt (Disambiguierung).
Ein Diagramm mit 6 Scheitelpunkten und 7 Kanten, an denen der Scheitelpunkt 6 auf dem fernen links ein Blattscheitel oder ein Anhängerscheitel ist

Im Mathematik, und genauer gesagt in Graphentheorie, a Scheitel (Plural Eckpunkte) oder Knoten ist die grundlegende Einheit, von der Diagramme gebildet werden: a ungerichtete Grafik besteht aus einer Reihe von Scheitelpunkten und einer Reihe von Kanten (ungeordnete Eckpaare), während a gerichteter Graph besteht aus einer Reihe von Scheitelpunkten und einer Reihe von Bögen (geordnete Eckpaare). In einem Diagramm eines Diagramms wird ein Scheitelpunkt normalerweise durch einen Kreis mit einem Etikett dargestellt, und eine Kante wird durch eine Linie oder einen Pfeil dargestellt, der sich von einem Scheitelpunkt zum anderen erstreckt.

Aus der Sicht der Graphentheorie werden die Scheitelpunkte als unteilbar behandelt Objekte, obwohl sie je nach Anwendung, aus der aus der Grafik erfolgt, eine zusätzliche Struktur haben; Zum Beispiel a Semantisches Netzwerk ist eine Grafik, in der die Eckpunkte Konzepte oder Objektklassen darstellen.

Die beiden Scheitelpunkte, die eine Kante bilden, sollen die Endpunkte dieser Kante sind, und die Kante soll den Eckpunkten vorfallen. Ein Scheitelpunkt w soll an einen anderen Scheitelpunkt angrenzen v Wenn die Grafik eine Kante enthält (v,w). Das Nachbarschaft eines Scheitelpunkts v ist ein induzierter Untergraph der Grafik, gebildet von allen Scheitelpunkten nebenv.

Arten von Scheitelpunkten

A small example network with 8 vertices and 10 edges.
Beispielnetzwerk mit 8 Scheitelpunkten (von denen man isoliert ist) und 10 Kanten.

Das Grad Von einem Scheitelpunkt, bezeichnet (v) in einem Diagramm die Anzahl der Kanten, die ihm zugeordnet sind. Ein Isolierter Scheitelpunkt ist ein Scheitelpunkt mit Grad Null; Das heißt, ein Scheitelpunkt, der kein Endpunkt einer Kante ist (das Beispielbild zeigt einen isolierten Scheitelpunkt).[1] A Blattscheitelpunkt (Auch Anhängerscheitelpunkt) ist ein Scheitelpunkt mit Grad 1. In einem gerichteten Diagramm kann man die Außenabteilung (Anzahl der ausgehenden Kanten) unterscheiden, bezeichnet +(v) aus dem Ingr keine (Anzahl der eingehenden Kanten), bezeichnet−(v); a Quellscheitelpunkt ist ein Scheitelpunkt mit unberührtem Null, während a Waschbeckenscheitelpunkt ist ein Scheitelpunkt mit Outdegree Null. EIN Einfacher Scheitelpunkt ist einer, dessen Nachbarn a bilden Clique: Alle zwei Nachbarn sind nebensend. EIN Universeller Scheitelpunkt ist ein Scheitelpunkt, der an jeden anderen Scheitelpunkt im Diagramm nebeneinander liegt.

A Scheitelpunkt schneiden ist ein Scheitelpunkt, dessen Entfernung das verbleibende Diagramm trennen würde; a Scheitelpunktabscheider ist eine Sammlung von Eckpunkten, deren Entfernung das verbleibende Diagramm in kleine Stücke trennen würde. EIN K-Vertex-verbundenes Diagramm ist ein Diagramm, in dem weniger als k Scheitelpunkte lassen immer das verbleibende Diagramm angeschlossen. Ein unabhängiger Satz ist eine Reihe von Eckpunkten, von denen keine zwei nebeneinander sind und a Scheitelpunktabdeckung ist ein Satz von Scheitelpunkten, die mindestens einen Endpunkt jeder Kante in der Grafik enthalten. Das Scheitelpunkt eines Diagramms ist ein Vektorraum mit einer Reihe von Basisvektoren, die den Eckpunkten des Diagramms entsprechen.

Ein Diagramm ist Scheitelpunkt-transitiv Wenn es Symmetrien gibt, die einen Scheitelpunkt einem anderen Scheitelpunkt zuordnen. Im Zusammenhang mit Graph -Aufzählung und Graph Isomorphismus Es ist wichtig, zwischen zu unterscheiden beschriftete Scheitelpunkte und Unbezeichnete Eckpunkte. Ein beschrifteter Scheitelpunkt ist ein Scheitelpunkt, der mit zusätzlichen Informationen zugeordnet ist, die es ermöglichen, von anderen beschrifteten Scheitelpunkten zu unterscheiden. Zwei Diagramme können nur dann als isomorph angesehen werden, wenn die Korrespondenz zwischen ihren Scheitelpunkten Eckpunkte mit gleichen Beschriftungen kombiniert. Ein unbeschriebener Scheitelpunkt ist einer, der nur durch einen anderen Scheitelpunkt ersetzt werden kann, der nur auf seinem basiert Angrenzungen in der Grafik und nicht auf zusätzlichen Informationen.

Scheitelpunkte in Grafiken sind analog zu, aber nicht gleich wie, Scheitelpunkte von Polyeder: das Skelett Von einem Polyeder bildet ein Diagramm, dessen Eckpunkte die Eckpunkte des Polyeders sind, aber Polyedertron -Eckpunkte haben eine zusätzliche Struktur (ihre geometrische Position), von der nicht angenommen wird, dass sie in der Graphentheorie vorhanden ist. Das Scheitelpunktfigur eines Scheitelpunkts in einem Polyeder ist analog zur Nachbarschaft eines Scheitelpunkts in einem Diagramm.

Siehe auch

Verweise

  1. ^ Datei: Small Network.png; Beispielbild eines Netzwerks mit 8 Scheitelpunkten und 10 Kanten
  • Gallo, Giorgio; Pallotino, Stefano (1988). "Kürzeste Pfadalgorithmen". Annals of Operations Research. 13 (1): 1–79. doi:10.1007/bf02288320. S2CID 62752810.
  • Berge, Claude, Théorie des Graphes et Ses Anwendungen. Sammlung Universität de Mathématiques, II Dunod, Paris 1958, VIII+277 S. (English Edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moskau 1961; Spanisch, Mexiko 1962; Roumanian, Bukarest 1969; Chinese, Shanghai 1963 19633333333, 1963, 1963, 19633, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963, 1963 ; Zweiter Druck der ersten englischen Ausgabe von 1962. Dover, New York 2001)
  • Chartrand, Gary (1985). Einführungsgrafik -Theorie. New York: Dover. ISBN 0-486-24775-9.
  • Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graphentheorie, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Graphentheorie. Reading, Mass.: 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