第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有