Impressum/Datenschutz
Glossar

Adjazenzliste: Liste von Knoten mit der ein gegebener Knoten durch eine Kante verbunden ist (englisch: adjacency list)

Adjazenzmatrix: Matrix, in der ein Eintrag in Zeile Z und Spalte S die Anzahl an Kanten angibt, die Knoten Z mit Knoten S verbindet (englisch: adjacency matrix)

Ausgangsgrad: Anzahl der Kanten, die von einem Knoten wegführen (englisch: out-degree)

Baum: zusammenhängender kreisfreier Graph (englisch: tree)

bewerteter Graph: Graph, bei dem jeder Kante eine Zahl zugeordnet ist (englisch: weighted graph)

bipartiter Graph: Graph mit zwei disjunkten Knotenmengen und Kanten zwischen Knoten den Mengen, aber ohne Kanten innerhalb einer Menge (englisch: bipartite graph)

Block: zusammenhängender Teilgraph ohne Schnittecke (englisch: block)

Bogen: gerichtete Kante (Synonym: gerichtete Kante, englisch: arc)

Brücke: Kante, die, wenn man sie entfernt, einen zusammenhängenden Teilgraph in mindestens zwei Komponenten teilt (englisch: bridge)

chromatischer Index: Minimalzahl an Farben, um alle Kanten eines beliebigen Knotens verschieden einzufärben (englisch: chromatic index)

chinesischer Postbote: Postbote, der einen bewerteten Graphen in einer eulerschen Tour durchquert unter Minimierung der Gesamtlänge, die sich als Summe aller Gewichte der Kanten der Tour ergibt (englisch: chinese postman)

chromatische Zahl: Minimalzahl an Farben, um alle Knoten so zu färben, daß jede Kante an Knoten verschiedener Farben endet (englisch: chromatic number)

Digraph: Graph, in dem alle Kanten gerichtet sind (englisch: digraph)

ebener Graph: Graph, der in einer Ebene ohne Kantenüberkreuzungen gezeichnet werden kann (englisch: planar graph)

Ecke: atomarer Teil eines Graphen, der mit anderen Ecken durch Kanten verbunden sein kann (Synonym: Knoten, englisch: vertex)

einfacher Graph: Graph ohne Schlingen und ohne parallele Kanten (englisch: simple graph)

Eingangsgrad: Anzahl der Kanten, die zu einem Knoten hinführen (englisch: in-degree)

eulersche Tour: geschlossener Kantenzug, der jede Kante des Graphen enthält (englisch: Euler tour)

eulerscher Graph: Graph, der eine eulersche Tour erlaubt (englisch: Euler graph)

Fluß: Menge, die eine Kante entlang fließt oder aus einem Knoten heraus (Quelle mit positivem Fluß) oder hinein (Senke mit negativem Fluß) und die meistens durch eine Kapazität der Kante beschränkt ist (englisch: flow)

gerichtete Kante: Kante, die den Knoten an ihrem Startpunkt mit dem Knoten an ihrem Endpunkt verbindet, aber nicht umgekehrt (Synonym: Bogen, englisch: directed Edge)

gerichteter Kantenzug: Kantenzug aus gerichteten Kanten (englisch: directed walk)

geschlossener Kantenzug: Kantenzug, in dem Anfangs- und Endecke übereinstimmen (englisch: closed walk)

Gerüst: zusammenhängender kreisfreier Graph (Synonym: spannender Baum)

Grad: Anzahl der Kanten, mit denen ein Knoten verbunden ist (englisch: degree)

Graph: Menge von Knoten, die über Kanten beliebig miteinander verbunden sein können (englisch: graph)

Handelsreisender: Reisender, der alle Knoten eines Graphen (in einer Rundreise) besucht unter Minimierung der Gesamtlänge, die sich als Summe aller Gewichte der Kanten der Reise ergibt (englisch: traveling salesman)

induzierter Teilgraph: Teilgraph aus allen oder einem Teil der Knoten des Graphen und allen Kanten des Graphen, die nur mit Knoten dieser Knotenmenge verbunden sind (englisch: induced subgraph)

isolierte Ecke: Ecke, die mit keiner Kante verbunden ist (englisch: isolated vertex)

isomorpher Graph: Graph mit der gleichen Knotenß und Kantenmenge, der nur anders gezeichnet ist (englisch: isomorphic graph)

hamiltonscher Kreis: Kreis, der alle Ecken des Graphen enthält (englisch: hamiltonian cycle)

Kante: atomarer Teil eines Graphen, der genau zwei Ecken miteinander verbindet, die nicht unterschiedlich sein müssen (englisch: edge)

Kantenfolge: Folge von Kanten, in der jede Kante mit ihren Nachbarn in der Liste verbunden ist (englisch: walk)

Kantenzug: Kantenfolge, in der alle Kanten verschieden sind (englisch: trail)

Kapazität: maximale Menge, die durch eine Kante fließen kann oder die Menge, die ein Knoten verlassen kann (Quelle mit positiver Kapazität) oder die in den Knoten fließen kann (Senke mit negativer Kapazität) (englisch: capacity)

Knoten: atomarer Teil eines Graphen, der mit anderen Ecken durch Kanten verbunden sein kann (Synonym: Ecke, englisch: vertex)

komplementärer Graph: Graph mit der gleichen Knotenmenge wie der Ausgangsgraph und der Kantenmenge, die dem Ausgangsgraph fehlt, damit er vollständig ist (englisch: complenentary graph)

Komponente: zusammenhängender Subgraph, der alle Knoten und Kanten enthält, die über einen (gerichteten) Kantenzug von einem gegebenen Knoten erreichbar sind (englisch: component)

Kreis: Weg, in dem Anfangs- und Endknoten identisch sind (englisch: cycle)

Löschung eines Knotens: Entfernung eines Knotens und aller mit ihm verbundenen Kanten (englisch: deletion of a vertex)

Matching: Kantenmenge, in der keine zwei Kanten einen gemeinsamen Knoten haben (englisch: matching)

Mehrfachkante: Menge von parallelen Kanten, die die gleichen zwei Knoten verbindet (englisch: multi-edge)

Minimalkostenfluß: maximaler Fluß aus der Quelle eines Graphen bei minimalen Kosten, die sich ergeben durch die Summe aus allen Flüssen entlang der Kanten multipliziert mit dem jeweiligen Kantengewicht (englisch: minimum cost flow)

Nachbarknoten: Knoten, der von einem gegebenen Knoten über eine Kante direkt erreichbar ist (englisch: neighbor vertex)

parallele Kante: Kante, die zusätzlich zu mindestens einer anderen zwei Knoten verbindet (englisch: parallel edge)

Quelle: jeder Knoten in einem Digraph mit Eingangsgrad 0 (englisch: source)

regulärer Graph: Graph, in dem jeder Knoten den gleichen Grad hat (englisch: regular graph)

Schlinge: Kante, die einen Knoten mit sich selbst verbindet (englisch: self-loop)

Schnittecke: Knoten, der, wenn man ihn entfernt, einen zusammenhängenden Teilgraph in mindestens zwei Komponenten teilt (englisch: cut-vertex)

(schwach) zusammenhängender Teilgraph: Teilgraph, in dem jeder Knoten mit jedem anderen Knoten über einen Kantenzug verbunden ist (englisch: (weakly connected subgraph))

Senke: jeder Knoten in einem Digraph mit Ausgangsgrad 0 (englisch: sink)

spannender Baum: Baum, der alle Ecken des Graphen enthält (Synonym: Gerüst, englisch: spanning tree)

spannender Teilgraph: Teilgraph, der die gleiche Knotenmenge hat wie der Graph selbst (englisch: spanning subgraph)

stark zusammenhängender Teilgraph: Teilgraph, in dem jeder Knoten mit jedem anderen Knoten über einen gerichteten Kantenzug verbunden ist (englisch: strongly connected subgraph)

Teilgraph: Graph, der alle oder einen Teil der Knoten und Kanten des Graphen enthält, wobei alle Kanten mit Knoten des Teilgraphen verbunden sein müssen (kann durch Löschung von Kanten und/oder Knoten entstehen) (englisch: subgraph)

topologische Sortierung: Anordnung der Knoten eines Digraphen, bei der der Anfang jedes Bogens einen Knoten in der Anordnung referenziert, der vor dem Knoten liegt der das Ende des Bogens bezeichnet (englisch: topological order)

Tour: geschlossener Kantenzug (englisch: tour)

vollständiger bipartiter Graph: bipartiter Graph, in dem jeder Knoten der einen Knotenmenge mit allen Knoten der anderen Knotenmenge verbunden ist (englisch: complete bipartite graph)

vollständiger Graph: Graph, in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist (englisch: complete graph)

Wald: kreisfreier Graph, also ein oder mehrere Bäume (englisch: forest)

Weg: Kantenzug, in dem alle inneren Knoten verschieden sind (englisch: path)

Wurzel: Knoten mit Eingangsgrad 0 (englisch: root)

Impressum/Datenschutz • Seite geprüft am 27. Sep. 2005