Graph

From Cophy
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.

Contents

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) E with v,w 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 Kn if E = V×V. See for example the complete graph K5.

K5

Bipartite graph


bipartite Graph

A graph G = (V,E) is called bipartite if its vertex set can be partitioned into two disjoint subsets V1,V2 such that every edge of G joins V1 with V2, i.e. E = {(v,w) | vV1wV2}, and no edge connects vertices in V1 only or V2 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 > ∈ 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 π = v1,v2,v3,...,vk, k≥1, such that (vi,vi + 1) E, for i = 1,2,3,...,k − 1. A walk is called closed if k > 1 and v1 = vk. 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 π = v1,v2,v3,...,vk, k≥1, such that (vi,vi + 1) A, for i = 1,2,3,...,k − 1. Furthermore, if k > 1 and v1 = vk, 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.


Connectivity


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.


Cut


A Cut is a partition of the vertices V of a graph G = (V,E) into two sets W and V\W. Any edge (v,w) E with v V\W and w W is a cut edge.
We denote the set of cut edges with δ(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)≥0 ∀ e E and w satisfies the triangle inequality then we call w a distance function for G.

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


Subgraph


A graph H = (VH,EH) is a subgraph of G = (V,E), if VH V and EH E. We say H = (VH,EH) is a vertex-induced subgraph of G, if VH V and EH = (VH×VH) E.

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

A graph H = (VH,EH) 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) E, then H = (V ∪{ v * V},E \ {e} {(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 V such that for every pair of vertices v,w K, there exists an edge e = (v,w) 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 V such that no two vertices v,w I are adjacent, in the sense that every clique corresponds to an independent set in the complement graph.

Planar graph


planar graph


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


planar graph with dual graph

A (geometric) dual graph GD of an (embedded) connected planar graph G is a planar graph with the properties:
GD 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

and

  • for a clique Kn(Vc,Ec) of n = | Vc | vertices, E * = Ec\E.

Undirected graph undirected graph and its complement: inverse graph


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 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 | xiyi | = 1, with v = (x1,y1), w = (x2,y2), see Fig. 1.

Figure 1: 4x4 grid graph

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.

Figure 2: 4x4 ring graph

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

Figure 3: toroidal grid graph (torus)

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

Personal tools