Graphs

A graph consists of vertices (nodes) connected by edges (arcs).

The two main categories of graphs are undirected graphs, in which edges don't have any particular direction, and directed graphs, where edges have direction - for example, there may be an edge from node A to node B, but no edge from node B to node A.

Generally, we use the following notation for a graph $G$: $n$ is the number of vertices, i.e. $|V|$, $m$ is the number of edges, i.e. $|E|$.

Within undirected graphs there are other distinctions:

• a simple graph is a graph in which there are no loops and only single edges are allowed
• a regular graph is one in which each vertex has the same number of neighbors (i.e. the same degree)
• a complete graph is a simple graph where every pair of vertices is connected by an edge
• a connected graph is a graph where there exists a path between every pair of vertices

For a connected graph with no parallel edges (i.e. each pair of vertices has only zero or one edge between it), $m$ is somewhere between $\Omega(n)$ and $O(n^2)$.

Generally, a graph is said to be sparse if $m$ is $O(n)$ or close to it (that is, it has the lower end of number of edges). If $m$ is closer to $O(n^2)$, this is generally said to be a dense graph.

An adjacency matrix requires $\Theta(n^2)$ space. If the graph is sparse, this is a waste of space, and an adjacency list is more appropriate - you have an array of vertices and an array of edges. Each edge points to its endpoints, and each vertex points to edges incident on it. This requires $\Theta(m+n)$ space (because the array of vertices takes $\Theta(n)$ space and the arrays of edges, edge-to-endpoints, and vertex-to-edges each take $\Theta(m)$, for $\Theta(n+3m) = \Theta(m+n)$), so it is better for sparse graphs.

Consider the accompanying example graph.

A path $A \to B$ is the sequence of nodes connecting $A$ to $B$, including $A$ and $B$.

Here the path $A \to B$ is $A,C,E,B$.

$A,C,E$ are the ancestors of $B$.
$C,E,B$ are the descendants of $A$.

A cycle is a directed path which ends where it starts. Here, $A,D,C,B$ form a cycle.

A loop is any path (directed or not) which ends where it starts.

A graph with no cycles is said to be acyclic.

A chord is any edge which connects two non-adjacent nodes in a loop.

Directed acyclic graphs (DAGs) are used often. In a DAG, parents are the nodes which point to a given node; the nodes that a given node points to are its children. A family of a node is the node and its parents.

The Markov blanket of a node is its parents, children, and the parents of its children (including itself).

For an undirected graph, a node's neighbors are noes directly connected to it.

In an undirected graph, a clique is a fully-connected subset of nodes. All members of a clique are neighbors.

A maximal clique is a clique which is not a subset of another clique.

In this graph:

• $\{A,B,C,D\}$ is a maximal clique
• $\{B,C,E\}$ is a maximal clique
• $\{A,B,C\}$ is a non-maximal clique, contained in $\{A,B,C,D\}$

An undirected graph is connected if there is a path between every pair of nodes. That is, there is no isolated subgraph.

For a non-connected graph, its connected components are its subgraphs which are connected.

A singly connected graph is the connected graph (directed or not) where there is only one path between each pair of nodes. This is equivalent to a tree.

A non-singly connected graph is said to be multiply connected.

A spanning tree of an undirected graph is one where the sum of all edge weights is at least as large as any other spanning trees'.

Graphs can be represented as an adjacency matrix:

$$ A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix} $$

Where a non-zero value at $A_{ij}$ indicates that node $i$ is connected to node $j$.

A clique matrix represents the maximal cliques in a graph.

For example, this clique matrix describes the following maximal clique:

$$ C = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} $$

A clique matrix containing only 2-node cliques is an incidence matrix:

$$ C = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} $$

References

• Algorithms: Design and Analysis, Part 1. Tim Roughgarden. Stanford/Coursera.
• Bayesian Reasoning and Machine Learning. David Barber.
• Probabilistic Graphical Models. Daphne Koller. Stanford University/Coursera.