第1章图上的随机场和条件独立性
1.1图的定义和基本概念
一个图是由顶点的集合和边的集合组成的，通常表示为，其中是节点(也称顶点）的集合，是边的集合，在本书中我们在多数场合考虑简单无向图，即两点间不存在多重边，也不存在一点到自身的环，并且边都是无方向性的.如果两点，间有一条边相连接，将这条边记为，称和相邻.
设是节点集的子集，由它导出的子图化，其中边的集合是从图中保留了那些两个节点都在A中的边得到的.称一个图是完备的，如果它的所有节点之间都有由边组成的路是连通的.一个子集称为完备的，如果它导出的子图是完备的.一个完备子集在包含意义下是最大的则称为单纯形(simplex).换言之，一个单纯形上所有的点都是两两有边相连接的.图1.1.1分别是由1，2，3，4，5个节点组成的单纯形的图.
邻域
记为一个邻域系统，N是节点集F的一个满足以下性质的非空子集族.
(i)对任何不属于
(ii)当且仅当对任何，成立，
其中队称为的邻域.对于不同的图，它们的邻域结构也不同.
图1.1.1有1，2，3，4，5个节点的单纯形图
节点集的子集A的边界况是由中的那些是A中点的邻点全体组成的.由节点到节点的长为的一条路是由一列不同的节点，组成之点列，且相继的两点有边相连，即.一个长为的环是首尾相接的路，其节点.称一个图为树(tree)，如果它是一个连通的没有环的图，树上任两点间有且只有一条路.一个有根的树(rooted tree)是一个有向的无环图，它是在一个树图上选择一个节点作为根点，所有的边都是从根点向外指向的.图1.1.2可以是无根树，这个树上每个节点的邻点数都相同，称为齐次树或Bethe树，记每个节点有k个邻点的树为Tk.图1.1.2也可以是有根树，取任何一点作为根点，如图中所示的O点.图1.1.3是二叉有根树，有一个根点，分出两个分支，每个节点向外有两个分支，称为Cayley树.一个森林(forest)是一个有向图，它的所有连通的子集都是树.我们将在后面讨论树上的随机场.
树图是另一类更广泛的称为格(lattice)中的一种，格还包括，当d=1时即是直线上由整数点构成的图，相邻两点间距离为1.和分别是平面上和3维空间中由整数坐标的点全体构成，两点间欧氏距离为1时有1条边相连，图1.1.4是1，2，3维整数格的示意图，图1.1.5是2维蜂窝格，图1.1.6是2维三角格.在第9章中我们还将遇到其他3维格，如3维面心格和体心格.
对于记它的有限子集，其边界为，用表示集合B中的节点数，易验证
1.1图的定义和基本概念
即在某种意义下，边界点可以忽略，上的移位算子群是可控群(amenable group).但对树图，这并不成立.事实上，对于每个节点有k个邻点的Bethe树来说，第n层上的节点数与从根点到第n层构成的子树上节点比值如图1.1.2的Bethe树，该比值趋于说明边界的影响不可忽略.
[78]给出另一个指标可以区别格办和树.令为从图上给定一点出发在n步内能到达的节点集合中的点数，那么对于Zd有.
其中d正好是Zd的维数，但对于每个节点有k个邻点的Bethe树来说，那么上述比值，这说明Bethe树是无穷维的.
再来看它们的邻域结构，对平面三角格，每个顶点有6个邻点，其中原点0=(0，0)的邻域为
(图1.1.7(d)).
对直线，每个节点只有2个邻点(图1.1.7⑷).
对平面矩形格，每个顶点有4个邻点.原点的邻域为
(图1.1.7(c)).另一种邻域结构，每个节点有8个邻点(图1.1.7(e))，称为Moore Neumann邻域.
对于2维蜂窝格，每个顶点有3个邻点.其原点的邻域
1.2条件独立和马氏性
1.条件独立
设随机变量服从联合分布用表示和互相独立.而随机变量的条件独立性含义是：设随机变，服从联合分布，用表示在给定z条件下和互相独立，当是取值于离散有集时，意味着
(2-1)
对任何满足的z成立.
如果是连续随机变量并有联合分布密度，则
(2-2)
对任何满足的z成立.
条件(2-2)可以重写为如果是连续随机变量并有联合分布密度则
(2-3)
条件独立的三元关系有以下性质：设h(x)表示样本空间Z上的可测函数，则有
(cl)
(c2)
(c3)
(c4)
(c5)
(c6)如果是连续随机变量并有联合分布密度，则有
(2-4)
(2-5)
(2-6)
(2-7)
(2-8)
以上右边的关系对所有非零的都成立.
2.马尔可夫性
本节我们考虑以图的节点集为下标集、在概率空间上定义的随机场，设是y的一个子集，中的元素记为，类似地，记我们用一个简化的记号
表示
以下我们来定义几种马尔可夫性(简称马氏性).
(P)点对点马氏性：对任两个不相邻的点对(i，j)，如果
则称i和j满足相对于图g的点对点马氏性.
(L)局部马氏性：如果对任何点i6F有
