Editorial/Data Protection
Glossary

Adjacency List: list of vertices a given vertex is connected to by edges (German: Adjazenzliste)

Adjacency Matrix: Matrix, in which an entry in Row R and Column C denotes the number of edges that connect vertex R with vertex C (German: Adjazenzmatrix)

Arc: directed edge (synonym: directed edge, German: Bogen)

Bipartite Graph: graph with two disjoint vertex sets and edges between the two sets, but not within a single set (German: bipartiter Graph)

Block: connected subgraph without cut-vertex (German: Block)

Bridge: edge that, if deleted, cuts a connected subgraph into at least two components (synonym: cut-edge, German: Brücke)

Capacity: maximum quantity that can flow through an edge or the quantity that emerges from a vertex (source with positive capacity) or goes into a vertex (sink with negative capacity) (German: Kapazität)

Chinese Postman: postman who traverses the graph in an Euler tour while minimizing the total length, which is the sum of the weights of all edges used in the tour (German: chinesischer Postbote)

Chromatic Index: minimum number of colors necessary to give all edges of any vertex distinct colors (German: chromatischer Index)

Chromatic Number: minimum number of colors necessary to give all vertices colors such that every edge ends at vertices with different colors (German: chromatische Zahl)

Closed Walk: walk with identical start and end vertex (German: geschlossener Kantenzug)

Complementary Graph: graph with the same vertex set as the original graph and the edge set that is missing in the original graph to be complete (German: komplementärer Graph)

Complete Bipartite Graph: bipartite graph that has every vertex of one vertex set connected to all vertices of the other vertex set (German: vollständiger bipartiter Graph)

Complete Graph: graph that has every vertex is connected to every other vertex by an edge (German: vollständiger Graph)

Component: connected subgraph that covers all vertices and edges that can be reached from a given vertex by means of a (directed) walk (German: Komponente)

Cut-Edge: edge that, if deleted, cuts a connected subgraph into at least two components (synonym: bridge, German: Brücke)

Cut-Vertex: vertex that, if deleted, cuts a connected subgraph into at least two components (German: Schnittecke)

Cycle: walk that has identical start and end vertices (German: Kreis)

Degree: number of edges a vertex is connected to (German: Grad)

Deletion of a Vertex: removal of a vertex and all edges it is connected to (German: Löschung eines Knotens)

Digraph: graph in which all edges are directed (German: Digraph)

Directed Edge: Edge that connects the vertex at its start point with the vertex at its endpoint, but not vice versa (synonym: arc, German: gerichtete Kante)

Directed Walk: walk composed of directed edges (German: gerichteter Kantenzug)

Edge: atomic part of a graph that connects exactly two vertices that need not to be distinct (German: Kante)

Euler Tour: closed walk that covers all edges of the graph (German: eulersche Tour)

Euler Graph: graph that allows an Euler tour (German: eulerscher Graph)

Flow: quantity that flows along an edge or emerges from a vertex (source with positive flow) or goes into a vertex (sink with negative flow) and that is usually limited by a capacity (German: Fluß)

Forest: cycle-free graph that are one or several trees (German: Wald)

Graph: set of vertices that may be arbitrarily connected by means of edges (German: Graph)

Hamiltonian Cycle: cycle that covers all vertives of the graph (German: hamiltonscher Kreis)

Editorial/Data Protection • page checked on Sep. 27th 2005

In-Degree: the number of edges pointing to a vertex (German: Eingangsgrad)

Induced Subgraph: subgraph with all or some vertices of the graph and all edges of the graph that are only connected to a vertex of this vertex set (German: induzierter Teilgraph)

Isolated Vertex: vertex that is not connected to any edge (German: isolierte Ecke)

Isomorphic Graph: graph with the same vertex and edge set, which is differently drawn (German: isomorpher Graph)

Matching: Edge set in which no two edges have a common vertex (German: Matching)

Minimum Cost Flow: maximum flow emerging from the source of a graph at minimum cost that is the sum of all flows along edges multiplied with the corresponding edge weights (German: Minimalkostenfluß)

Multi-Edge: set of parallel edges that connect the same two vertices (German: Mehrfachkante)

Neighbor Vertex: vertex that can be reached directly by an edge from a given vertex (German: Nachbarknoten)

Out-Degree: the number of edges emerging from a vertex (German: Ausgangsgrad)

Parallel Edge: Edge that connects two vertices in supplement to at least one other edge (German: parallele Kante)

Path: trail in which no internal vertex is repeated (German: Weg)

Planar Graph: graph that can be drawn in a plane with no crossing edges (German: ebener Graph)

Regular Graph: graph with the same degree for all vertices (German: regulärer Graph)

Root: vertex with in-degree 0 (German: Wurzel)

Self-Loop: edge that connects a vertex with itself (German: Schlinge)

Simple Graph: graph without self-loops and without parallel edges (German: einfacher Graph)

Sink: every Vertex in a digraph with out-degree 0 (German: Senke)

Source: every Vertex in a digraph with in-degree 0 (German: Quelle)

Spanning Subgraph: subgraph that has the same vertex set as the graph itself (German: spannender Teilgraph)

Spanning Tree: tree that covers all vertices of a graph (German: spannender Baum)

Strongly Connected Subgraph: subgraph in which every vertex is connected to every other vertex by means of a directed walk (German: stark zusammenhängender Teilgraph)

Subgraph: graph that contains all or some of the vertices and edges of the graph such that all edges must be connected to vertices of the subgraph (may have been created by deleting edges and/or vertices) (German: Teilgraph)

Topological Order: arrangement of the vertices of a graph such that the start of every arc references a vertex in the arrangement that is before the vertex that denotes the end of the arc (German: topologische Sortierung)

Tour: closed trail (German: Tour)

Trail: walk in which no edge occurs more than once (German: Kantenzug)

Traveling Salesman: salesman who visits all vertices of a weighted graph (in a round trip) while minimizing the total length, which is the sum of the weights of all edges used in the journey (corresponding problem is called TSP) (German: Handelsreisender)

Tree: connected cycle-free graph (German: Baum)

Vertex: atomic part of a graph that can be connected to other vertices by means of edges (German: Ecke)

Walk: list of edges such that each edge is connected to its neighbors in the list (German: Kantenfolge)

(Weakly) Connected Subgraph: subgraph in which every vertex is connected to every other vertex by means of a walk (German: (schwach) zusammenhängender Teilgraph)

Weighted Graph: graph in which every edge has an associated figure (German: bewerteter Graph)