We state here basic definitions from graph theory used in the articles. For more details we refer the interested reader to the literature.
A graph or an undirected graph is a tuple with
- a nonempty set whose elements are called vertices, nodes or points
- a (possibly empty) set of unordered pairs of elements of V called links or edges
(Here we restrict ourselves to the terms vertex and edge to refer to elements of and , respectively.)
For an edge with the vertices and are called endpoints of edge . Vertices and are adjacent if they are connected by an edge . Furthermore we say edge is incident to vertices v and w.
Two edges sharing one common endpoint are called adjacent, too.
We call an edge a loop if its endpoints are identical (), and edges are called multi-edges. A graph containing no multi-edges or loops is called simple graph.
The degree, , of a vertex is the total number of its incident edges.
The order of a graph , is defined as the cardinality of the (vertex) set . The size of a graph, denoted by , is the cardinality of the (edge) set .
A graph is called complete graph if . See for example the complete graph .
A graph is called bipartite if its vertex set can be partitioned into two disjoint subsets such that every edge of joins with , i.e. , and no edge connects vertices in only or only.
A directed graph or digraph is a graph with (edge) set consisting of ordered pairs of vertices, called arcs, directed edges or arrows.
Let . We call tail and head of arc . Further on, is called (direct) predecessor of which is a (direct) successor of . We skip the term direct if are connected via a path with length greater than 1.
The indegree () of a vertex is defined as the number of arcs of the form (e.g. is the head of the arcs), similarly the outdegree () of a vertex is defined as the number of arcs where is tail (e.g. arcs of the form: ).
A directed graph having no multi-edges or loops is called a simple directed graph. A complete graph in which each edge is bidirected is called a complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of nodes is joined by a single edge having a unique direction) is called a tournament.
Walk, path, and cycle
Let be a graph. A walk in is a sequence of vertices , , such that , for . A walk is called closed if and . A walk without any repeated vertex is called path. A closed path is called circuit or cycle. The length of a walk is the number of edges of the walk.
Similiarly, a directed walk is a sequence of , , such that , for . Furthermore, if and , then is closed. A directed path is a directed walk without repetitions. A directed cycle (or circuit) is a closed directed path.
Tree and forest
A connected simple graph without cycles is called a tree. If the graph is simple but disconnected, i.e there are more than one component, and there exists no cycle then we call the graph a forest.
Acyclic graph (DAG)
A directed graph is called directed acyclic graph if it contains no directed cycle.
Two nodes are connected if the graph contains at least one path from v to w.
A graph is connected if every pair of its nodes is connected.
A graph is strongly connected if each two nodes are adjacent.
A Cut is a partition of the vertices of a graph into two sets and . Any edge with and is a cut edge.
We denote the set of cut edges with .
Let be a connected graph. is called Eulerian iff every vertex of has even degree. This is equivalent to saying that the edge set of can be partitioned into cycles
Let be a graph (undirected or directed). A weight function (or a cost function) for is a mapping .
If and satisfies the triangle inequality then we call a distance function for .
Let be a path in . The weight of the path is denoted by .
A graph is a subgraph of , if and . We say is a vertex-induced subgraph of , if and .
Similarly we say is an edge-induced subgraph of , if and , i.e the vertex set of is restricted to vertices occuring in .
A graph which is constructed from by repeated edge deletion and/or contraction is called a minor of . Contraction of an edge means the replacement of and by a single vertex such that all edges other than that were incident to and are now incident to the new vertex.
A subdivision of graph is defined on the graph that arises from by (repeatedly) replacing an edge of by two edges and one new vertex.
Formally: Let and , then is a subdivision of .
Clique, independent set
A clique in a graph is a set of vertices such that for every pair of vertices , there exists an edge . This is equivalent to saying that the subgraph induced by is a complete graph. The size of a clique is the number of vertices it contains.
The "opposite" of a clique is an independent set, i.e. a set of vertices such that no two vertices are adjacent, in the sense that every clique corresponds to an independent set in the complement graph.
A graph is planar if it can be drawn in the plane in such
a way that no two edges meet each other except at a vertex to which they are
both incident. Any such drawing is called a planar drawing of .
A (geometric) dual graph of an (embedded) connected planar graph is a planar graph with the properties:
has a node for each face of and an edge for each edge joining two neighboring faces (including loops and multi-edges), (cf. [Harary (1989)]).
The complement or inverse of a graph is a graph on the same vertices such that two vertices are adjacent in if and only if they are not adjacent in .
More formally, given a graph , its complement graph is defined by:
- for a clique of vertices, .
For simple graphs (without multiple edges) we note that the complement of the complement graph yields the original graph again.
We call a graph planar (rectangular) grid graph, if can be embedded in the plane such that each vertex is identified with an unique coordinate and any two vertices are adjacent if and only if the Manhattan distance between those two vertices equals 1, i.e. , with , , see Fig. 1.
In other words, any finite subgraph of the 2 dimensional rectangular grid is called a grid graph. Grid graphs form a class of planar graphs that arise in many applications, such as ground state calculations of Ising spin glasses or design of VLSI circuits. Rectangular grid graphs are those grid graphs whose outer boundary is a rectangle and whose bounded faces all are unit squares.
We call a rectangular grid graph ring graph if the edge set also includes periodic boundary edges on one side, see Fig. 2.
If periodic boundary edges are present on both sides we call the rectangular grid graph a toroidal grid graph or torus, cf. Fig. 3.
Note that toroidal grid graphs cannot be embedded in the plane without edge crossings, but can be on the torus.