Basic graph definitions

Directed and undirected graphs

1. A directed graph consists of a finite set of nodes (a.k.a. vertices) of and a multiset of ordered pairs of nodes. The elements of are the arcs of .
2. An undirected graph consists of a finite set of nodes (a.k.a. vertices) and a multiset of unordered pairs of nodes, the edges.
3. A directed or undirected graph is simple, if no node is paired with itself in and , respectively, and

the multisets and , respectively, are sets.

1. A directed graph is

symmetric if implies , for all , and anti-symmetric if implies .

= Adjacency and incidence

1. Two nodes of a directed or undirected graph are called adjacent if they share at least one arc/edge.
2. A node and an arc/edge are called incident if the node belongs to the arc/edge.
3. For a node, the number of incident arcs/edges is the degree of this node.
4. Consider a directed graph and a node :
5. An arc is an outgoing arc of , and an arc is an incoming arc of .
6. The outdegree of is the number of its outgoing arcs, the indegree of is the number of its incoming arcs.

Representations of graphs

We focus on directed graphs because an undirected graph is usually represented as a symmetric directed graph as introduced above. Let and . We denote and .

1. Adjacency matrix: an -matrix such that, for ,

if , and
if .

1. Incidence matrix: an -matrix such that, for and , it is

if  for some ,
if  for some ,

, otherwise.

1. Incidence list: a sequence of length . For , is a sequence of arcs and contains all outgoing arcs of .

Connectedness

An undirected graph is said to be connected if, for each pair of nodes, there is a path connecting this pair. A directed graph is said to be weakly connected if, for each pair of nodes, there is a generalized path connecting this pair. A directed graph is said to be strongly connected if, for each pair of nodes, there is a path connecting this pair.