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

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),

Generally, a graph is said to be **sparse** if **dense** graph.

An adjacency matrix requires

Consider the accompanying example graph.

A **path**

Here the path

**ancestors** of

**descendants** of

A **cycle** is a directed path which ends where it starts. Here,

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**:

Where a non-zero value at

A **clique matrix** represents the maximal cliques in a graph.

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

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

- 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.