大师兄的贝叶斯网络学习笔记（十五）：图分割与变量独立（二）
大师兄的贝叶斯网络学习笔记（十七）：图分割与变量独立（三）
三、有向分割与无向分割
- 判断有向无环图中的d-分隔与无向图中的无向分隔之间的关系，有助于判定d-分隔。
- 设G为一有向无环图，如果将G中每个节点的不同父节点结合，即在它们之间加一条边，然后去掉所有边的方向，所得到的无向图称为G的端正图(moral graph)，记为
。
- 从G到
- 考虑到a所示的有向无环图，要端正化，首先要将图中节点R的两个父节点T好L结合，把D的两个父节点R和B结合，然后去掉所有边的方向，结果如b。
- 设Y是有向无环图G中的一个节点集合。
- G在Y上的限制，记为
，是从G中除去所有不属于Y的节点及其相连的边而得到的图。
1.定理：有向分割与无向分割
- 在一个无向图G中，节点X和Y之间的一条通路指的是从X开始到Y结束的一个节点序列，其中节点各异且在序列中相邻的节点在G中也相邻。
- 设X、 Y、Z是G中的3个两两交空的节点集合。
- 如果从G中除去Z中的节点后，X和Y之间没有通路存在，负称Z无向分隔(undirected separate)X和Y，简称Z u-分隔X和Y。
- 图b中，
u-分隔A和D，但
则不u-分隔A和D.
- 容易看到，Z在G中 u-分隔X和Y当且仅当X和Y之间的任何通路都经过Z。
- 定理（有向分割与无向分隔）：设X、Y、Z是有向无环图G中3个两两相交的节点集合。用
表示先把G限制在
上，再将其结果端正化而得到的无向图。那么，集合Z在G中d-分隔X和Y的充分必要条件是它在
