Graph concepts
Next, we will briefly revisit the concepts from graph theory and some of the definitions that we will use in this chapter.
Graph structure and properties
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 = {X1, X2,….Xk} where X1, X2,….Xk 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 Xi is called the parent node and the node Xj is called the child node.
In the case of an undirected graph, if there is an edge Xi – Xj, the nodes Xi and Xj 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.
Subgraphs and cliques
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.
Path, trail, and cycles
If there are variables X1, X2, …. Xk in the graph K = (X, E), it forms a path if, for every i = 1, 2 ... k – 1, we have either 
or Xi –Xj; that is, there is either a directed edge or an undirected edge between the variables—recall this can be depicted as Xi ? Xj. A directed path has at least one directed edge: .
If there are variables X1, X2, …. Xk 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 Xi, ….Xj there is a trail between Xi and Xj.
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 X1, X2, …. Xk where X1 ? Xk, the path is called a cycle. Conversely, a graph with no cycles is called an acyclic graph.
