Graphs

A graph is specified by a set $V$ of vertices and a collection $E$ of unordered pair of vertices called edges and denoted by $G = (V, E)$. Several problems can be formulated in terms of graphs, in physics, electrical engineering and computer science. There is an entire branch devoted to the study of graph theoretic algorithms. Sometimes, graphs make problems easier to visualize (although not necessarily easier to solve, since graphs have their own complexities). We begin with some definitions:

The order of a graph is the number of its vertices, and the size is the number of edges. We concern ourselves here with directed and undirected graphs. Suppose $i, j \in V$ and that there is an edge connecting vertex $i$ to vertex $j$. If $G = (V, E)$ is a directed graph or digraph then, $(i, j) \in E$ but $(j, i) \notin E$ (or vice versa), that is, in a digraph there is a sense of direction of an edge. Therefore, we can also define the indegree and outdegree of a vertex in a digraph as the number of edges entering that vertex and the number of edges leaving that vertex, respectively. In an undirected graph all that matters is whether there is an edge connecting two vertices.

Note that if $(i, i) \in E$ then there is a self-loop, that is, an element is connected to itself via an edge (that ends up looking like a loop). A graph with no loops is called a multigraph whereas a pseudograph is a graph having at least one loop. The definition of an undirected graph prohibits undirected graphs from having self loops.

In general, $E \subseteq V \times V$, so $|E| \leq |V|^2$.

A sequence of vertices $\langle u_{1}, u_{2}, \ldots, u_{k} \rangle$ in a given graph is a path if there is no repetition of vertices in the sequence (that is $u_{i} \neq u_{k}$ $\forall i \neq k$) and for every $1\leq i \leq k-1$, $(u_{i}, u_{i+1}) \in E$. Thus, $\langle u_{1}, u_{2}, \ldots, u_{k} \rangle$ is a path from $u_{1}$ to $u_{k}$.

A sequence of vertices $\langle u_{0}, u_{1}, \ldots, u_{k} \rangle$ in a given graph is a cycle if there is no repetition of vertices in the sequence and for every $0\leq i\leq k$, we have $(u_{i \mod k}, u_{(i+1) \mod k}) \in E$. Equivalently, a cycle is sequence of vertices $\langle u_{0}, u_{2}, \ldots, u_{k} \rangle$ such that $u_{0} = u_{k}$ and there is no repetition of vertices in $\langle u_{0}, u_{1}, \ldots, u_{k-1} \rangle$ and $(u_{i}, u_{i+1}) \in E$ $\forall 0\leq i\leq k-1$.

A graph is connected if there exists a path connecting any pair of vertices. A graph is complete if there exists an edge connecting every pair of vertices in the graph. Clearly, a complete graph is connected but the converse is not true in general (e.g. consider a square with no diagonals).

A subgraph of $G = (V, E)$ is a graph $G' = (V', E')$ such that $V' \subseteq V$ and $E' \subseteq E$. By definition, it is also required that $E' \subseteq V' \times V'$. It is obvious that $E' \subseteq V \times V$. A symmetric digraph is a directed graph such that for every edge $(v, w)$ there is also the reverse edge $(w, v)$. Every undirected graph has a corresponding symmetric digraph by interpreting each undirected edge as a pair of directed edges in opposite directions.

A connected component of an undirected graph G is a maximal connected subgraph of G.

Under Construction

page revision: 7, last edited: 16 Oct 2007 08:58