A graph is defined as a data structure containing nodes and edges connecting these nodes. In the context of this chapter, the random variables are represented as nodes, and edges show connections between the random variables.

Formally, if X = {X₁, X₂,….X_k} where X₁, X₂,….X_k are random variables representing the nodes, then there can either be a directed edge belonging to the set e, for example, between the nodes given by or an undirected edge , and the graph is defined as a data structure . A graph is said to be a directed graph when every edge in the set e between nodes from set X is directed and similarly an undirected graph is one where every edge between the nodes is undirected as shown in Figure 1. Also, if there is a graph that has both directed and undirected edges, the notation of represents an edge that may be directed or undirected.

Figure 1. Directed, undirected, and partially-directed graphs

If a directed edge exists in the graph, the node X_i is called the parent node and the node X_j is called the child node.

In the case of an undirected graph, if there is an edge X_i – X_j, the nodes X_i and X_j are said to be neighbors.

The set of parents of node X in a directed graph is called the boundary of the node X and similarly, adjacent nodes in an undirected graph form each other's boundary. The degree of the node X is the number of edges it participates in. The indegree of the node X is the number of edges in the directed graph that have a relationship to node X such that the edge is between node Y and node X and X → Y. The degree of the graph is the maximal degree of the node in that graph.

A subgraph is part of the graph that represents some of the nodes from the entire set. A clique is a subset of vertices in an undirected graph such that every two distinct vertices are adjacent.

If there are variables X₁, X₂, …. X_k in the graph K = (X, E), it forms a path if, for every i = 1, 2 ... k – 1, we have either or X_i –X_j; that is, there is either a directed edge or an undirected edge between the variables—recall this can be depicted as X_i ? X_j. A directed path has at least one directed edge: .

If there are variables X₁, X₂, …. X_k in the graph K = (X, E) it forms a trail if for every i = 1, 2 ... k – 1, we have either .

A graph is called a connected graph, if for every X_i, ….X_j there is a trail between X_i and X_j.

In a graph K = (X, e), if there is a directed path between nodes X and Y, X is called the ancestor of Y and Y is called the descendant of X.

If a graph K has a directed path X₁, X₂, …. X_k where X₁ ? X_k, the path is called a cycle. Conversely, a graph with no cycles is called an acyclic graph.