####本节书摘来自华章出版社《深度学习导论及案例分析》一书中的第2章，第2.4节，作者李玉鑑 张婷，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4概率图模型的基本概念

图是一种数据结构，由顶点集V和边集E构成，记作G=（V，E）。
在概率图模型中，每一个随机变量对应一个顶点（或称节点），反之亦然。也就是说，随机变量和顶点是一对一的关系。图的边定义了这些变量之间的特定关系。边分为无向边（undirected edge）和有向边（directed edge）。假定顶点Xi，Xj∈V，用Xi-Xj表示Xi和Xj之间的无向边，用Xi→Xj表示从Xi到Xj的有向边。对于无向边，Xi-Xj与Xj-Xi是等价的。而对于有向边，Xi→Xj与Xj→Xi是不等价的，但与Xj←Xi是等价的。需要注意的是，对于任意两个顶点Xi和Xj，i≠j，要么没有边连接它们，要么只有一条无向边连接它们，要么只有一条有向边Xi→Xj或Xj→Xi连接它们。此外，用XiXj来表示Xi和Xj经由某种边连接的情形，这条边要么是有向的（任意方向），要么是无向的。

如果一个图G=（V，E）的所有边都是无向的，那么称其为无向图（undirected graph）。

图2.1有向图的拓扑序举例

如果G的所有边都是有向的，那么称其为有向图（directed graph）。如果G既包含无向边，又包含有向边，那么称其为混合图（mixed graph）。当Xi→Xj∈E时，称Xi在图G中是Xj的父节点（parent），Xj是Xi的子节点（child）。当Xi-Xj∈E时，称Xi是的Xj邻节点（neighbor）。如果对有向图的顶点集进行排序X1，…，Xn，只要Xi→Xj∈E，就有i

对图G的任意顶点X∈V，用PaG（X）表示X的所有父节点，用ChG（X）表示X的所有子节点，用NbG（X）表示X的所有邻节点。X的边界集定义为
BoundaryG（X）=PaG（X）∪NbG（X）（2.54）
在不引起歧义时使用有关记号可以省略图下标G。显然，在图2.1中，Pa（X5）=Pa（X7）={X6}，Ch（X2）={X3，X4}，Boundary（X1）=Nb（X1）=。

如果一个图的顶点集V′V，且该图的边集由G中所有与V的两个节点相连的边组成，那么称其为G的导出子图，记作G［V′］。如果G［V′］的任意两个节点均由一条边连接，那么称其为完全子图（complete subgraph），且此时V′称为团（clique）。如果对任意超集V′′V′，V′′都不是团，那么V′称为极大团（maximal clique，或译成最大团）。

设{X1，…，Xn}V。如果i∈{1，…，n-1}，XiXi+1，则称X1，…，Xn是一条从X1到Xn的迹（trail），当Xn=X1时，这条迹又称为环（loop）。连接一个环中两个不相邻顶点的边，称为弦（chord）。如果i∈{1，…，n-1}，Xi→Xi+1∈E或Xi-Xi+1∈E，则称其为一条从X1到Xn的路径（path），当Xn=X1时，这条路径又称为圈（cycle）。如果在这条路径上至少存在一条有向边，则称其为有向路径，当Xn=X1时，又称为有向圈（directed cycle）。如果一个圈不存在有向边，则称为无向圈（undirected cycle）。

如果在有向图中，Xi，Xj∈V（i≠j）且存在一条从Xi到Xj的有向路径，则称Xi是Xj的祖先（ancestor），Xj是Xi的后代（descendant）。用AncG（X）表示X的所有祖先，用DescG（X）表示X的所有后代，用NonDescG（X）=V-DescG（X）表示X的所有非后代集合。

如果一个图不包含任何环，那么称这个图是单连通的（singly connected）。在单连通图中，如果一个节点只有一个相邻节点，则称为叶（leaf）节点。一个单连通的有向图也称为一棵多重树（polytree）。一个单连通的无向图则称为一个森林（forest）。如果一个森林是连通的，则称为树（tree）。如果一个有向图的每个节点至多只有一个父节点，那么这个有向图也称为森林，并且在连通时称为树。

如果一个图不包含圈，则称其为无圈图（acyclic graph）。一个无圈图是有向的，则称其为有向无圈图（directed acyclic graph，DAG）。一个包含有向边和无向边的无圈图称为部分有向无圈图（partially directed acyclic graph，PDAG）。部分有向无圈图又称为链图（chain graph），因为可以被分解为一些不相交的有序链分支，其中每个链分支都是无向子图，有向边只能从编号较小的链分支指向编号较大的链分支。

如果一个无向图中任意长度大于等于4的环都包含一条弦，那么这个无向图称为弦图（chordal graph）。弦图通常也称为三角剖分图（triangulated graph）。

概率图模型的基本思想是把随机变量之间的条件依赖和独立性质映射到图结构上来描述概率分布［103］。概率图模型主要分为概率有向图模型（probabilistic directed acyclic graphical model）、概率无向无圈图模型（probabilistic undirected acyclic graphical model）和部分有向无圈图模型（partially directed acyclic graphical model），将在2.5节、2.6节和2.7节分别讨论。