An **undirected graph** is defined by \((V, E)\) where \(V\) is
a set of nodes and \(E\) is a set of edges (each edge is an
*unordered* set of two nodes taken from \(V\)). It is referred to as
a **graph** for short.

A **directed graph** is like an undirected graph, except that the edges
point from one node to the other. As such, each edge is a tuple of nodes
\((N_{1},N_{2})\) such that the edge is from \(N_{1}\) to
\(N_{2}\). It is often referred to as a **digraph** for short.

For convenience, we’ll exclude self edges as well as multiple edges between the same nodes.

## Properties & Definitions

### Degree

The **degree** of a node in a graph is the number of edges connected to
it. For a **digraph**, the **indegree** is the number of edges that are
pointing to the node, and the **outdegree** is the number of edges that are
pointing away from the node.

Let \(p_{k}\) be the fraction of nodes in the graph that have degree
\(k\). The **degree distribution** of a graph can be visualized by
making a histogram of the \(p_{k}\) values. In English, it is simply
the number of nodes in a graph with a given degree, but then normalized
to represent a probability. A byproduct of this is that it does form a
probability mass function.

### Paths & Distance

There exists a **path** of length \(k\) between two nodes
\(a,b\) if there are \(k-1\) nodes you can insert between
\(a,b\) such that there is an edge starting from \(a\) that
goes through all the nodes to \(b\).

A path is **simple** if a node appears only once.

A path can be represented by the sequence of nodes the path traverses. Note that if the path is not simple, then the representation is not unique.

The **distance** between two nodes is the smallest \(k\) such that a
path of length \(k\) exists between them. Note that there may be
multiple paths of this distance in a graph - they need not be unique.

A **cycle** is a *simple* path that begins and ends at the same node.

A **circuit** also begins and ends at the same node, but it need not be simple.

An **Eulerian tour** is a cycle that traverses all the edges in the
connected component exactly once. It can be shown that an Eulerian tour
exists if and only if a graph is connected and the degree of each node
is even.

Question: Describe an algorithm that gives an Eulerian tour?

### Connectivity

A graph is **connected** if there is a path between every pair of
distinct nodes. Note that this does *not* imply the graph is complete!

A **connected component** of a graph is a connected subgraph that is not
a proper subgraph of another connected subgraph. In English: It is the
largest possible subgraph containing a given node that is connected. The
graph can be partitioned into connected components.

A digraph is **strongly connected** if there is a path between every
pair of nodes (in both directions).

A digraph is **weakly connected** if its underlying undirected graph is connected.

Digraphs have the concept of **strongly connected components**: They are
strongly connected but are not proper subgraphs of strongly connected
subgraphs of the original digraph.

### Bipartite Graphs

A graph is **bipartite** if its nodes can be partitioned into two
disjoint and nonempty sets \(V_{1},V_{2}\) such that every edge
connects a node from \(V_{1}\) to \(V_{2}\). There are no edges
connecting nodes within these two sets.

The classical homework problem of connecting items from the first column to the second is an example.

Note that this does not mean every node has an edge.

### Directed Acyclic Graph

A **directed acyclic graph** is a digraph with no cycles (although the
underlying graph may have some).

## Graph Representations

### Adjacency List

An **adjacency list** for a graph consists of two columns. Each entry in
the first column contains a node. Each entry in the 2nd column is a set
of all the nodes connected to the node in the first column. If the graph
is a digraph, then the first column only represents the node the edge
begins from.

An example of an adjacency list of a digraph:

Beginning Node | Ending Nodes |
---|---|

\(N_{1}\) | \(\{N_{2},N_{4}\}\) |

\(N_{3}\) | \(\{N_{1}\}\) |

\(N_{2}\) | \(\{N_{1},N_{3}\}\) |

This representation is useful if the graph is sparse.

This corresponds to the following graph:

### Adjacency Matrix

An **adjacency matrix** \(A\) has \(A_{ij}=1\) if and only if
the nodes \(i\) and \(j\) are connected by an edge. Otherwise
the value is 0.

In a digraph, it is 1 if and only if the edge goes from node \(i\) to \(j\).

The matrix for an undirected graph is symmetric.

This representation is useful if the graph is dense.