From cophywiki
Revision as of 12:04, 28 April 2011 by Bergner (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

We state here basic definitions from graph theory used in the articles. For more details we refer the interested reader to the literature.

Undirected graph

undirected graph

A graph or an undirected graph is a tuple G=(V,E) with

  • a nonempty set V whose elements are called vertices, nodes or points
  • a (possibly empty) set E 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 V and E, respectively.)

For an edge e=(v,w) \in E with v,w \in V the vertices v and w are called endpoints of edge e. Vertices v and w are adjacent if they are connected by an edge e. Furthermore we say edge e=(v,w) is incident to vertices v and w.

Two edges sharing one common endpoint are called adjacent, too.

We call an edge e=(v,w) a loop if its endpoints are identical (v=w), and edges e = f = (v,w) are called multi-edges. A graph containing no multi-edges or loops is called simple graph.

The degree, deg(v), of a vertex v is the total number of its incident edges.

The order of a graph |V|, is defined as the cardinality of the (vertex) set V. The size of a graph, denoted by |E|, is the cardinality of the (edge) set E.

Complete graph

A graph is called complete graph K_n if E=V\times V. See for example the complete graph K_5.

Error creating thumbnail: File missing

Bipartite graph

Error creating thumbnail: File missing

A graph  G=(V,E) is called bipartite if its vertex set can be partitioned into two disjoint subsets V_1, V_2 such that every edge of G joins V_1 with V_2, i.e. E=\{(v,w) | v \in V_1,\ w \in V_2 \}, and no edge connects vertices in V_1 only or V_2 only.

Directed graph

directed graph

A directed graph or digraph is a graph G=(V,A) with (edge) set A consisting of ordered pairs of vertices, called arcs, directed edges or arrows.

Let e=<v,w> \in A. We call v tail and w head of arc e. Further on, v is called (direct) predecessor of w which is a (direct) successor of v. We skip the term direct if v are connected via a path with length greater than 1.

The indegree (indeg(v)) of a vertex v is defined as the number of arcs of the form (u,v) (e.g. v is the head of the arcs), similarly the outdegree (outdeg(v)) of a vertex v is defined as the number of arcs where v is tail (e.g. arcs of the form: (v,w)).

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 G=(V,E) be a graph. A walk in G is a sequence of vertices \pi=v_1,v_2,v_3,\ldots, v_k, k\geq 1, such that (v_i,v_{i+1}) \in E, for i=1,2,3,\ldots, k-1. A walk is called closed if k>1 and v_1=v_k. 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 \pi=v_1,v_2,v_3,\ldots, v_k, k\geq 1, such that (v_i,v_{i+1}) \in A, for i=1,2,3,\ldots, k-1. Furthermore, if k>1 and v_1=v_k, then \pi 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 v,w 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 V of a graph G=(V,E) into two sets W and V \setminus W. Any edge (v,w) \in E with v \in V \setminus W and w \in W is a cut edge.
We denote the set of cut edges with \delta(W).

Eulerian graph

Let G be a connected graph. G is called Eulerian iff every vertex of G has even degree. This is equivalent to saying that the edge set of G can be partitioned into cycles

Weighted graph

Let G=(V,E) be a graph (undirected or directed). A weight function (or a cost function) for G is a mapping \scriptstyle w: E \rightarrow \mathbb{R}.

If w(e) \geq 0\ \forall\ e \in E and w satisfies the triangle inequality then we call w a distance function for G.

Let \pi=v_1,v_2,\ldots,v_r be a path in G. The weight of the path \pi is denoted by \scriptstyle w(\pi)=\sum\limits_{i=1}^{r-1} w(v_i,v_{i+1}).


A graph H=(V_H,E_H) is a subgraph of G=(V,E), if V_H \subseteq V and E_H \subseteq E. We say H=(V_H,E_H) is a vertex-induced subgraph of G, if V_H \subseteq V and E_H=(V_H\times V_H) \cap E.

Similarly we say H=(V_H,E_H) is an edge-induced subgraph of G, if E_H \subseteq E and V_H=V[E_H], i.e the vertex set of G is restricted to vertices occuring in E_H.

A graph H=(V_H,E_H) which is constructed from G by repeated edge deletion and/or contraction is called a minor of G. Contraction of an edge e=(v,w) means the replacement of v and w by a single vertex such that all edges other than e that were incident to v and w are now incident to the new vertex.

A subdivision of graph G is defined on the graph that arises from G by (repeatedly) replacing an edge of G by two edges and one new vertex.
Formally: Let G=(V,E) and e=(v,w) \in E, then H=(V \cup \{ v^* \notin V \}, E \setminus \{e \} \cup \{(v, v^*), ( v^*, w) \}) is a subdivision of G.

Clique, independent set

A clique in a graph G=(V,E) is a set of vertices K \subseteq V such that for every pair of vertices v,w \in K, there exists an edge e=(v,w) \in E. This is equivalent to saying that the subgraph induced by K 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 I \subseteq V such that no two vertices v,w \in I are adjacent, in the sense that every clique corresponds to an independent set in the complement graph.

Planar graph

Error creating thumbnail: File missing

A graph G 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 G.

Dual graph

Error creating thumbnail: File missing

A (geometric) dual graph G_D of an (embedded) connected planar graph G is a planar graph with the properties:
G_D has a node for each face of G and an edge for each edge joining two neighboring faces (including loops and multi-edges), (cf. [Harary (1989)]).

Complement graph

The complement or inverse of a graph G=(V,E) is a graph H=(V,E^*) on the same vertices such that two vertices are adjacent in H if and only if they are not adjacent in G.

More formally, given a graph G=(V, E), its complement graph H(V^*,E^*) is defined by:

  • V^* = V


Undirected graph
Error creating thumbnail: File missing
and its complement:
Error creating thumbnail: File missing

For simple graphs (without multiple edges) we note that the complement of the complement graph yields the original graph again.

Grid graph

We call a graph G planar (rectangular) grid graph, if G can be embedded in the plane such that each vertex is identified with an unique coordinate and any two vertices v,w \in V are adjacent if and only if the Manhattan distance between those two vertices equals 1, i.e. d(v,w)= \textstyle\sum_{i=1}^2 |x_i - y_i| = 1, with v=(x_1,y_1), w=(x_2,y_2), see Fig. 1.

Error creating thumbnail: File missing

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 G=(V,E) ring graph if the edge set E also includes periodic boundary edges on one side, see Fig. 2.

Error creating thumbnail: File missing

If periodic boundary edges are present on both sides we call the rectangular grid graph a toroidal grid graph or torus, cf. Fig. 3.

Error creating thumbnail: File missing

Note that toroidal grid graphs cannot be embedded in the plane without edge crossings, but can be on the torus.