Graph Theory

Network Theory is an application of Graph Theory. We take the term network to refer to the informal concept describing an object composed of elements and interactions or connections between these elements.

For example, the Internet is a network composed of nodes (routers, hosts) and connections between these nodes (e.g. fiber cables). The natural means to model networks mathematically is provided by the notion of graphs.

A graph G = (V,E) is an abstract object formed by a set V of vertices (nodes) and a set E of edges (links) that join (connect) pairs of vertices. The vertex set and edge set of a graph G are denoted by V (G) and E(G), respectively. The cardinality of V is usually denoted by n, the cardinality of E by m. The two vertices joined by an edge are called its endvertices. If two vertices are joined by an edge, they are adjacent and we call them neighbors.

Graphs can be undirected or directed. In undirected graphs, the order of the endvertices of an edge is immaterial. An undirected edge joining vertices u, v ∈ V is denoted by {u, v}. In directed graphs, each directed edge (arc) has an origin (tail) and a destination (head). An edge with origin u ∈ V and destination v ∈ V is represented by an ordered pair (u, v). As a shorthand notation, an edge {u, v} or (u, v) can also be denoted by uv. In a directed graph, uv is short for (u, v), while in an undirected graph, uv and vu are the same and both stand for {u, v}.

For a directed graph G = (V,E), the underlying undirected graph is the undirected graph with vertex set V that has an undirected edge between two vertices u, v ∈ V if (u, v) or (v, u) is in E. Graphs that can have directed edges as well as undirected edges are called mixed graphs, but such graphs are encountered rarely and we will not discuss them explicitly in the following.