Glossar  A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z -$?-?$

A

Arboreszenz: Wurzelbaum, bei dem alle Kanten einheitlich in Richtung des eindeutigen Pfades zur Wurzel (oder von der Wurzel weg) orientiert sind.

adjazent: Zwei Knoten heißen adjazent, wenn es eine Kante gibt, die beide enthält. Zwei Kanten heißen adjazent, wenn sie einen gemeinsamen Knoten haben.

Adjazenzmatrix: Matrix, deren Zeilen und Spalten mit den Knoten eines Graphen indiziert ist und bei der an der Stelle i,j genau dann eine 1 steht, wenn Knoten i und Knoten j adjazent sind (0 sonst).

alternierend: ein Pfad heißt alternierend bezüglich einer Korrespondenz wenn er abwchselnd Kanten enthält, die zu dieser gehören und nicht zu dieser gehören.

Antikette: Eine Antikette ist eine Menge paarweise nichtvergleichbarer Elemente einer Ordnung.

Artikulation: (engl. cut-vertex) Ein Knoten ist eine Artikulation, wenn die Menge, die nur ihn enthält, ein Schnitt ist.

augmentierend: Ein Pfad heißt augmentierend bezüglich einer Korrespondenz wenn er alternierend ist und sowohl mit einem freien Knoten beginnt also auch mit einem freien Knoten endet. Er heißt augmentierend bezüglich eines Flusses, wenn weitere Flußeinheien über ihn fließen können.

Automorphismus: Ein Graph-Automorphismus ist eine Permutation der Knoten mit der zusätzlichen Bedingung, dass zwei
Knoten ganau dann adjazent sind, wenn ihre Bilder unter der Permutation adjazent sind.

Automorphismengruppe: Die Autormorphismengruppe eines Graphen ist die (algebraische) Gruppe seiner Automorphismen.

azyklisch: Ein Graph ist azyklisch, wenn er keinen Zyklus enthält.

B

bipartit: Ein Graph ist bipartit, wenn sich sine Knotenmenge in zwei Mengen A und B zerlegen lassen, so daß jede Kante einen Knoten aus A und einen Knoten aus B enthält.

Blatt: Ein Blatt in einem Baum ist ein Knoten mit Grad 1. Ein Blatt eines Wurzelbaums ist ein Knoten, der keine Söhne hat.

Brücke: Eine Kante ist eine Brücke, wenn die Menge, die nur sie enthält, ein Schnitt ist.

Bruder: Zwei Knoten in einem Wurzelbaum sind Brüder, wenn sie einen gemeinsamen Vater haben.

C

chordal: Ein Graph ist chordal, wenn jeder Kreis mit mehr als vier Knoten eine Sehne hat.

chromatische Zahl: (engl. chromatic number, $?$) Minimale Zahl von Farben, die benötigt wird, um die Knoten eines gegebenen Graphen zu färben.

chromatischer Index: (engl. chromatic index) Mimimale Zahl von Faben, die benötigt wird, um die Kanten eines gegebenen Graphen zu färben.

chromatisches Polynom: Polynom das zu jeder Zahl von Farben angibt, wieviele verschiedene Färbungen mit dieser Zahl von Farben bei einem gegebenen Graphen möglich sind.

Clique: Menge von paarweise adjazenten Knoten

Cliquenzahl($?$): Größe einer größtenClique

Cliquengraph: Graph C der aus einem Graphen G gebildet wird, indem man die maximalen Cliquen von G zu den Knoten von C erklärt und zwei davon genau dann verbindet, wenn die korrespondierende Cliquen in C einen Knoten gemeinsam haben.

D

Dual: Das Dual eines planaren Graphen G ist der Graph H der entsteht, wenn man alle Flächen in die die Einbettung von G die Ebene zerteilt als Knoten von H interpretiert und von diesen genau dann zwei durch eine Kante verbunden sind, wenn sie benachbart liegen, d.h, nur nurch das Bild einer einzigen Kante von G getrennt werden.

Durchmesser: (diameter) Größter Abstand zweier Knoten

doppelt zusammenhängend: andere Bezeichnung für zweizusammenhängend

E

Einbettung: Unter der Einbettung eines Graphen versteht man seine Dastellung in einem metrischen Raum, wobei die Knoten durch Punkte und die Kanten durch Streckenzüge die die jeweiligen Knoten verbinden dargestellt werden. Dabei dürfen sich die Streckenzüge außer in ihren Anfangs und Endpunkten nicht berühren.
Jeder Graph ist in der dreidimensionalen Raum einbettbar. Graphen die man in die ebene einbettbar sind, heißen plättbar, nach der Einbettung bezeichnet man sie als planar.

einfach: Ein Pfad/Kreis heißt einfach, wenn er jeden Knoten nur einmal enthält. Ein Graph heißt einfach, wenn er es von jeder Kante höchstens eine gibt.

Exzentrizität: Die Exzentrizität eines Knotens ist der maximale Abstand von ihm zun einem anderen Knoten.

F

Faktor: Ein k-Faktor eines Graphen ist eine Teilmenge der Kanten, so daß jeder Knoten zu k von diesen incident ist. (Eine perfekte Korrespondenz ist ein 1-Faktor)

faktorkritisch: Ein Graph heißt faktorkritisch, wenn jeder induzierteSubgraph, der durch Entfernen eines Knotens entsteht eine perfekteKorrespondenz (einen 1-Faktor) hat.

Färbung: (engl. AE:coloring/BE: colouring) Zuordnung von Farben zu Knoten/Kanten, so daß adjazente Objekte verschiedene Farben haben. Bei Hypergraphen gibt es mehrere Definitionsvarianten, z.B. die Forderung, daß bei einer Knotenfärbung keine Kante monochromatisch ist.

Färbungszahl: anderes Wort für chromatische Zahl

Fläche: (eines planarenGraphen) von den Einbettungs-Bildern von  Kanten begrenztes Flächenstück der Ebene

Fluss: (engl flow) Zuordnung reeler Zahlen zu den Kanten eines Netzwerks. Man stellt sich vor, daß eine bestimmte Menge vom Schwanz einer Kante zu ihrem Kopf fließt. Der Fluss  muß die sog. Erahltungsbedingung erfüllen, d.h. dass der Überschuss an jedem
Knoten außer den Quellen und den Senken Null sein muß. Der Überschuss in den Quellen ist stets nichtnegativ und der Überschuss in den Senken nicht positiv.

G

gerichtet: Ein Graph heißt gerichtet, wenn seine Kanten gerichtet sind.

Gerüst: Ein Gerüst eines Graphen ist ein Teilgraph dessen Schnitt mit jeder Komponente jeweils einen minimalenspannenden Baum dieser Komponente bildet.

Gerüstanzahl: Zahl der Gerüste eines Graphen

Grad: der Grad eines Knotens ist die Zahl der zu ihm incidenten Kanten.

Graph: Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten. Er wird häufig mit G=(V,E) bezeichnet. Dabei meint V die Knoten und E die Kanten.

Größe: Die Größe eines Graphen ist die Zahl seiner Kanten (vgl. Ordnung)

größte(r): (engl. maximum) Eine Menge mit einer Eigenschaft ist eine größte Menge dieser Art, wenn es keine andere gibt, die mehr Elemente enthält und ebenfalls diese Eigenschaft erfüllt. vgl. maximal
Groupie: Ein Knoten eines Graphen heißt ein Groupie, wenn der durchschnittliche Grad seiner Nachbarn größer ist als der durchschnittliche Grad  aller Knoten im Graphen.

H

Hypergraph: Graph, der Hyperkanten enthält.

Hyperkante: (engl. hyperedge) Eine Hyperkante ist eine Kante, die mehr als zwei Knoten beinhalten kann.

I

isomorph: Zwei Graphen heißen isomorph, wenn es eine Abildung der Knoten und Kanten des einen auf die Knoten und Kanten des anderen gibt, die die Incidenz erhält, d.h. wenn man die Graphen durch geeignetes Umbennen der Knoten ineinander überführen kann.

incident: Ein Knoten und eine Kante heißen incident, wenn der Knoten in der Kante enthalten ist.

induziert: Ein Subgraph heißt induziert, wenn er unter allen Subgraphen mit der gleichen Knotenmenge die maximale Zahl von Kanten hat. D.h wann immer zwei Knoten des Subgraphs im ursprünglichen Graphen verbunden waren, sind sie es auch im Subgraphen.

Inverses: Das Inverse eines Graphen ist sein Komplement.

Isthmus:  Ein Isthmus ist eine Brücke, nach deren Entfernen jede Komponente noch mindestens eine Kante enthält

J

K

Kante: (engl. edge) Eine Kante ist eine Menge von Knoten.  Sind es mehr als zwei so spricht man von einer Hyperkante, ist es nur eine, von einer Schleife. Kanten können gerichtet und ungerichtet sein. Bei einer gerichteten Kante erhält jeder Knoten der Kante ein zusätzliches Prädikat. Er kann Kopf, Schwanz oder beides sein. Die Interpretation dieser Prädikate folgt meist der Anschauung, daß man eine Kante verwenden kann um von einem Knoten zum anderen zu gelangen. Im Fall einer einfachen Kante hat diese einen Kopf und einen Schwanz und man kann mittels dieser Kante nur noch vom Kopf zum Schwanz aber nicht mehr vom Schwanz zum Kopf gelangen.
Häufig ersetzt man hier um die Prädikate zu kodieren die Mengenschreibweise {a,b} durch die Tupelnotation (a,b), wobei das erste Element den Schwanz und das zweite den
Kopf bezeichnet. Ist ein Knoten in einer Kante enthalten, so bezeichnet man diese als incident. Zwei Knoten, die Element der selben Kante sind heißen adjazent. Einfache
Kanten werden häufig als Linien zwischen Punkten, die Knoten representieren dargestellt. Die Richtung der Kante - so gegeben - wird als Pfeil in richtung auf den Kopf angezeigt.
Kanten werden häufig weitere Parameter wie Kapazität oder Länge zugeordnet.

kantendisjunkt: Zwei Mengen, die Kanten enthalten (also z.B. auch Pfade) heißen kantendisjunkt, wenn es keine Kante gibt, die in beiden enthalten ist.

Kantenfolge: Eine Kantenfolge ist eine alternierende Folge von Knoten (v₀..v_n) und Kanten (e₁..e_n) der Form (v₀,e₁,v₁,e₂,v₂, ... , e_n,v_n). Ist eine Kante
e_i gerichtet, so muß v_i-1 ihr Schwanz und v_i ihr Kopf sein. v₀ ist der Anfang und v_n das Ende der Kantenfolge. Man sagt auch, die Kantenfolge führt von v₀ (Startknoten) nach v_n (Ziel-/Endknoten).

Kantenraum: Raum der Funktionen E -> Z₂ (teilweise auch E -> C), weobei E die Kantenmenge des Graphen ist.

Kantenüberdeckung: Teilmenge der Kanten eines Graphen, so daß jeder Knoten zu mindestens einer davon incident ist.

Kantenüberdeckungszahl($?$): Größe einer kleinsten Kantenüberdeckung

kleinste(r): (engl. minimum) Eine Menge mit einer Eigenschaft ist eine kleinste Menge dieser Art, wenn es keine andere gibt, die weniger Elemente enthält und ebenfalls diese Eigenschaft erfüllt. vgl. minimal

Knoten: (engl. vertex, node), Knoten sind das atomare Basiselement der Graphentheorie und als solche nicht definierbar. In der Praxis werden Knoten häufig als direkte Abstraktion konkreter Objekte (Städte, Kreuzungen, Gene, Buchstaben etc.) verwendet. Knoten werden graphisch meistens durch Punkte veranschaulicht.

knotendisjunkt: Zwei Mengen, die Knoten enthalten, heißen Knotendisjunkt, wenn es keinen Knoten gibt, der in beiden enthalten ist. bei Pfaden werden hierbei häufig die Start- und Zielknoten ausgenommen.

Knotenraum: Raum der Funktionen V -> Z₂ (oder V -> C), wobei V die Knotenmenge des Graphen ist.

Knotenüberdeckung: Teilmenge von Knoten eines Graphen, so daß jede Kante zu mindestens einem davon incident ist.

Knotenüberdeckungszahl($?$): Größe einer kleinsten Knotenüberdeckung

Komplement: Das Komplement eines Graphen G ist derjenige Graph, der die gleichen Knoten hat wie G, aber genau dort Kanten, wo G keine hat.

Komponente: s. Zusammenhangskomponente.

Komposition: die Komposition zweier Graphen G₁ und G₂ ist der Graph  G₁[G₂]der entsteht, wenn man die 2-Tupel (v₁,v₂), v1 aus G₁ und v₂ aus G₂ zu den Knoten des neuen Graphen erklärt und jeweils eine Kante einfügt, wenn die Elemente der  ersten Komponenten des Tupels adjazent sind oder wenn diese indentisch sind und die Elemente der jeweils zweiten Komponenten adjanzent sind.

Komplexität: Unter der Komplexität eines Graphen versteht man die Zahl seiner Spannenden Bäume. (nicht zu verwechseln mit der Komplexität von Algorithmen)

Kontraktion: Unter der Knotraktion einer Kante versteht man das Zusammenziehen der Kante zu einem Knoten, d.h. alle Knoten dieser Kante werden entfernt, ein neuer Knoten wird eingefügt und in alle Kanten aufgenommen, die einen der gelöschten Knoten enthielten. (Schleifen werden entfernt)

Kopf: (engl. head) Ende einer gerichtetenKante

Korrespondenz: (engl. Matching). Ein Matching (verbreiteterer Begriff) ist eine Menge von unabhängigenKanten. Bilden diese Kanten gleichzeitig eine Überdeckung, so heißt sie perfekt.

Kostenfunktion: Funktion die Knoten oder Kanten eines Graphen Kosten zuweist, die entstehen, wenn man diese benutzt.

Kreis: (engl. circle) Ein Kreis ist ein einfacher Pfad, bei dem Anfang und Ende übereinstimmen.

kreisfrei: (engl. circle free) Ein Graph ist kreisfrei, wenn er keinen Kreis enthält.

kritisch: Ein Graph heißt kritisch bezüglich einer Eigenschaft, wenn das Hinzufügen oder Entfernen eines Knotens oder einer Kante diese Eiganschaft ändert.

kubisch: Ein Graph heißt kubisch, wenn er 3-regulär ist.

L

leer: Ein Graph heißt leer, wenn er keine Kanten enthält.

Liniengraph: (engl. line-graph) Graph L der aus einem Graphen G gebildet wird, indem man dessen Kanten zu den Knoten des Graphen L erklärt und zwei vo diesen genau dann durch eine Kante verbindet, wenn die korrespondierenden Kanten in G adjazent waren.

Listenchromatische Zahl: Wählt man bei einem Listen-Kontenfärbungsproblem alle Listen gleich groß, so ist die Listenchromatische Zahl die mindestgröße dieser Listen, so daß es eine Listenfärbung der Knoten gibt.

Listenchromatischer Index: Analog zu Listenchromatischer Zahl für Kantenfärbungen.

Listenfärbung: (engl list-coloring) Färbung bei denen die Farbe für jedes Objekt aus einer diesem zugeordneten Liste sein muß.

M

Matchingzahl($?$): Größe eines größten Matchings

maximal: (engl. maximal) Eine Teilmenge einer Menge heißt maximal bzgl. einer Eigenschaft wenn sie diese Eigenschaft hat und  kein weiteres Element der Obermenge zu ihr hinzugefügt werden kann, ohne daß sie die Eigenschaft verliert. (vgl. größte)

Maximalgrad ($?$): Größter Grad eines Knotens in einem Graphen

minimal: (engl. minimal) Eine Menge heißt minimal bzgl. einer Eigenschaft, wenn kein Element aus ihr entfernt werden kann, ohne daß sie die Eigenschaft verliert.

Minimalgrad ($?$): kleinster Grad eines Knotens in einem Graphen

Minor: Ein Minor eines Graphen ist ein Graph, der aus diesem durch Kontraktion und Entfernen von Knoten/Kanten gewonnen werden kann.

monochromatisch: Eine Kante/Hyperkante heißt monochromatisch, wenn alle incidetenKnoten die gleiche Farbe haben.

Multigraph: In einem Multigraphen kann es mehrere identische Kanten geben. (Gegenteil: einfacher Graph)

N

Nachbarschaft: Die Nachbarschaft ($?$) einer Knotenmenge sind diejenigen Knoten, die Nachbar eines der Knoten aus dieser Menge sind.

Netzwerk: Ein Netzwerk ist ein zweigerichteterGraph mit mehereren ausgrezeichneten Knoten, den Quellen und den Senken. Den Knoten/Kanten eines Netzwerks sind häufig mehrere Parameter zugeordnet, die im Zusammenhang mit Flußproblemen eine Rolle spielen: minimale und maximale Kapazität, Kostenfunktion, Delay etc.

O

Ordnung: a) Die Ordnung eines Graphen ist die Zahl seiner Knoten. b) Fasst man gerichtete Kanten als 2-Tupel auf, so kann man die so definierte Relation, wenn der Graph azyklisch ist, als eine Ordnungsrelation verstehen. Die  eigentliche Ordungsrelation ergibt sich als Transitive Hülle der Kanten.

Orientierung: Richtung einer gerichtetenKante / das Versehen einer bisher ungerichteten Kante mit einer Richtung

P

partit: Ein Graph heißt r-partit, wenn seine Knotenmenge so in r Teilmengen zerlegt werden kann, daß jede Kante keine zwei Knoten aus der selben Teilmenge enthält.

perfekt: Ein Graph heißt perfekt, wenn für jeden seiner Subgraphen Cliquenzahl und chromatische Zahl übereinstimmen. Eine Korrespondenz heißt perfekt, wenn sie eine Überdeckung ist.
 

Pfad: (engl. Path) Ein Pfad ist eine Kantenfolge, bei der sich keine Kante wiederholt. Bei einem einfachen Pfad wiederholt sich auch kein Knoten.

planar: Eine Einbettung heißt planar, wenn sie in der Ebene gezeichnet werden kann.

plättbar: Ein Graph heißt plättbar, wenn er in die Ebene einbettbar ist. (wird auch oft ungenau als planar bezeichnet)

Potenz: Die i-te Potenz eines Graphen ist das i-fache Produkt dieses Graphen mit sich selbst.

Produkt: das Produkt zweier Graphen G₁ und G₂ ist der Graph der entsteht, wenn man die 2-Tupel (v₁,v₂), v1 aus G₁ und v₂ aus G₂ zu den Knoten des neuen Graphen erklärt und jeweils eine Kante einfügt, wenn jweils eine der beiden Komponenten des Tupels identisch ist und die jeweils andere Komponenten adjanzent sind.

Q

Quelle: (engl. source) Ausgezeichneter Knoten in einem Netzwerk, der in einem Fluß nichtnegativen Überschuss hat.

R

Radius: Der Radius eines Graphen ist der maximale Abstand eines anderen Knoten zu demjenigen Knoten für den dieser Wert minimal ist, also
das Minimum der Exzentrizität.

Rand: Der Rand einer Knotenmenge sind diejenigen Knoten in dieser Menge die einen Nachbarn außerhalb der Menge haben. Der Rand eines Graphen sind diejenigen Knoten, deren Exzentrizität dem Durchmesser entspricht.

regulär: Ein Graph heißt regulär, wenn alle Knoten den gleichen Grad haben (k-regulär, wenn alle den Grad k haben).
 

S

Schnittraum: Von den Schnitten aufgespannter Unterraum des Kantenraums

Schleife: (engl. Loop) Eine Schleife ist eine Kante, die nur einen Knoten enthält.

schlicht: Ein Graph wird als schlichter Graph bezeichnet, wenn er kein Multigraph ist. Eine Teilmenge des Kantenraums heißt schlicht, wenn jede Kante des Graphen in höchstens zwei der Mengen aus dieser Teilmenge liegt.

Schwanz: (engl. tail) Anfang einer gerichtetenKante

Sehne: Eine Kante heißt Sehne eines Kreises, wenn sie zwei Knoten verbindet, die in dem Kreis nicht direkt aufeinanderfolgen.

selbstdual: Ein Graph heißt selbstdual, wenn er isomorph zu seinem Dual ist.

selbstkomplementär: Ein Graph heißt selbstkomplementär, wenn er isomorph zu seinem Komplement ist.

selbstzentral: Ein Graph heißt selbstzentral, wenn das Zentrum des Graphen der Graph selbst ist, also alle Knoten die gleiche Exzentritität haben.

Senke: (engl. sink) Ausgezeichneter Knoten in einem Netzwerk, der in einem Fluß nichtpositiven Überschuss hat.

Sohn: Der Sohn eines Knotens in einem Wurzelbaum ist ein Nachbar, der nicht auf dem Pfad zur Wurzel liegt. Der Knoten ist dann Vater seines Sohns.

Spannbaum: Ein Spannbaum ist ein spannenderBaum.

spannend: Eine Kantenmenge heißt spannend, wenn sie eine Knotenüberdeckung ist. Ein Subgraph heißt spannend, wenn er alle Knoten des Graphen  beinhaltet.

Spektrum: Unter dem Spektrum eines Graphen versteht man die Eigenwerte seiner Adjazenzmatrix zusammen mit ihren Vielfachheiten.

stabil: Eine Knotenmenge heißt stabil, wenn ihre Elemente paarweise unabhänig sind.

Stabilitätszahl: (auch Unabhängigkeitszahl,$?$) Größe einer größtenstabilenKnotenmenge.

Subgraph: Ein Subgraph eines Graphen G ist ein Graph, dessen Knoten- und Kantenmenge Teilmengen der jeweiligen Mengen von G sind.

symmetrische Differenz: Die symmetrische Differenz zweier Mengen ist die Menge derjenige Elemente, die in genau einer der beiden enthalten sind.

T

Teilgraph: anderes Wort für Subgraph

Totalfärbung: Eine Totalfärbung ist eine gleichzeitige Färbung von Knoten und Kanten, bei der incidente Objekte verschiedene Farben erhalten.

trianguliert: Ein planarerGraph heißt trainguliert, wenn alle seine Flächen Dreiecke sind.

Transitiv: Ein Graph heist knotentransitiv, wenn seine Automorphismengruppe transitiv auf seinen Knoten operiert. Er heisst kantentransitiv, wenn die dadurch auf den Kanten induzierte Operation transitiv ist.

transitive Hülle: Unter der Transitiven Hülle eines Graphen versteht man die transitive Hülle der Zusammenhangsrelation. D.h. die kleinste Relationsmenge, die die Zusammenhangsrelation enthält und transitiv ist.

trennend: Eine Knoten- bzw. Kantenmenge heißt trennend, wenn sie einen Schnitt bildet.

U

Überschuss: (engl. excess). Die Differenz des in einen Knoten hineinfließenden und aus diesem herausfließenden Flusses. D.h. die Differenz der Summen der Flusswerte
der Kanten für die der Knoten Kopf ist minus der Summe der Flusswerte von Kanten für die der Knoten Schwanz ist.

Untergraph: anderes Wort für Subgraph

Umfang: (eines Graphen)Länge eines längsten Kreises

unabhängig: (engl. independent) Zwei Knoten heißen unabhängig, wenn sie nicht in einer gemeinsamen Kante enthalten sind. Zwei Kanten heißen unabhängig, wenn sie keinen Knoten gemeinsam haben.

Unabhängikeitszahl: Anderes Wort für Stabilitätszahl

Unterteilung: Eine Unterteilung einer Kante ist das Ersetzen dieser Kante durch zwei Kanten, deren Knotenmengen eine disjunkte Zerlegung der Knotenmengen der
ursprünglichen Kante sind und einen neuen Knoten, der in beiden Knotenmengen enthalten ist. (z.B. (a,b) -> (a,x),(x,b))

ungerichtet: (engl. undirected) Ein Graph ist ungerichtet, wenn alle seine Kanten ungerichtet sind.

V

Vater: Ein Knoten ist Vater eines anderen Knoten in einem Wurzelbaum, wenn er für diesen der nächste Knoten auf dem Pfad zur Wurzel ist.

Vergleichbarkeitsgraph: Graph dessen gerichtete Kanten einer Ordungsrelation auf seinen Knoten entsprechen

vollständig: Ein einfacher Graph heißt vollständig, wenn alle Knoten paarweise adjazent sind.

W

Weg: andere Bezeichnung für Kantenfolge

Würfelgraph: Derjenige Graph, der entsteht, wenn man die Elemente der Menge {0,1}^n (n feste natürliche Zahl) als Knoten interpretiert und je zwei von diesen genau dann durch eine Kante verbindet, wenn sie sich in genau einer Komponente unterscheiden. Dies entrspicht in der Geometrie den Ecken und Kanten eines Hyperwürfels.

Wurzel: (engl. root) Der ausgezeichnete Knoten eines Wurzelbaums.

Wurzelbaum: (engl. rooted tree) Ein Wurzelbaum ist ein Baum mit einem ausgezeichneten Knoten, der Wurzel.
 

X

Y

Z

zusammenhängend: (engl. connected) Ein ungerichteter Graph ist zusammenhängend, wenn es zwischen je zwei Knoten einen Pfad gibt.

Zusammenhangszahl ($?$): Ein Graph heisst $?$-(Knoten/Kanten)zusammenhängend, bzw. hat (Knoten/Kanten)-Zusammenhangszahl $?$, wenn es zwischen je zwei Knoten $?$ knotendisjunkte(bis auf Start- und Zielknoten) bzw. kantendisjunktePfade gibt.

Zusammenhangskomponente: Die Zusammenhangskomponenten eines ungerichteten Graphen sind seine maximalen zusammenhängendenSubgraphen. Die Knotenmengen dieser Subgraphen entsprechen den Äquivalenzklassen der Zusammenhangsrelation.  Bei gerichteten Graphen spricht man von starken Zusammenhangskomponenten diese entspechen den maximalen zweizusammenhängenden Subgraphen.

Zusammenhangsrelation: Zwischen zwei Knoten in einem Graphen besteht die Zusammenhangsrelation, wenn sie durch einen Pfad verbunden sind.

zweigerichtet: (engl. bidirected) In einem zweigerichteten Graphen gibt es zu jeder gerichteten Kante eine Kante mit der umgedrehten Orientierung. Ungerichtete Graphen werden bei Flussproblemen häufig wie zweigerichtete Graphen behandelt, indem man jede ungerichtete kante durch zwei gerichtete ersetzt. Der Flußbetrag der ungerichteten Kante instpricht dem Betrag der Differenz der beiden Flüsse  auf den gerichteten Kanten.

zweizusammenhängend: (auch stark zusammenhängend, engl. double connected) Ein gerichteter Graph heißt zweizusammenhängend, wenn es zwischen je zwei Knoten a und b sowohl einen Pfad von a nach b als auch einen von b nach a gibt.

Zyklenraum: Unterraum des Kantenraums, der von den Zyklen erzeugt wird.

zyklomatische Zahl: Dimension des Zyklenraums

Zyklus: Kreis in einem gerichtetenGraphen.

$?$ Unabhängigkeitszahl
$?$ Chromatische Zahl $$
$?$ Minimalgrad
$?$ Maximalgrad
$?$ Zusammenhangszahl
$?$ Matchingzahl
$?$ Lovasz' Theta-Funktion
$?$ Shannon-Kapazität
$?$ Knotenüberdeckungszahl
$?$ Kantenüberdeckungszahl
$?$ Cliquenzahl