 Table
of contents |
 Next |
A directed graph G is a pair (V,
E), where V is a finite set and E is a binary relation on V. The set V
is called the vertex set of G, and its elements are called
vertices
.
The set E is called the edge
set of G, and its elements are
called edges .
Note that self-loops--edges from a vertex to itelf - are possible.
In an undirected graph G = (V, E), the edge set E consists of unordered pairs of vertices , rather than ordered pairs. That is, an edge is a set {u,v} where u ,v belong to V and u != v. In an undirected graph, self-loops are forbidden, and so every edge consists of exactly two distinct vertices.
If (u, v) is an edge in a directed graph G = (V, E), we say that (u, v) is incident from or leaves vertex u and is incident on or enters vertex v.
If (u, v) is an edge in a graph G = (V, E), we say that vertex v is adjacent to vertex u. When the graph is undirected, the adjacency relation is symmetric. When the graph is directed, the adjacency relation is not necessarily symmetric.
The degree of a vertex in an undirected graph is the number of edges incident on it.
A path of length k from a vertex u to a vertex v in a graph G=(V,E) is a sequence <w0,w1,w2,...,wk> of vertices such that u=w0, v=wk, and (wi-1, wi) belongs to E for i=1, 2,..., k. The length of the path is the number of edges in the path. The path contains the vertices w0, w1,..., wk and the edges (w0, w1), (w1, w2),..., (wk-1,wk). If there is a path p from u to v, we say that v is reachable from u via p. A path is simple if all vertices in the path are distinct.
In a directed graph, a path <w0, w1,..., wk> forms a cycle if w0=wk and the path contains at least one edge. The cycle is simple if, in addition, w1, w2,..., wk are distinct. A self-loop is a cycle of length 1. A graph with no cycles is acyclic.
An undirected graph is connected if every pair of vertices is connected by a path. The connected components of a graph are the equivalence classes of vertices under the "is reachable from" relation. A directed graph is strongly connected if every two vertices are reachable from each other. The strongly connected components of a graph are the equivalnce classes of vertices under the "are mutually reacheable" realtion.