杭州响应式网站建设链接买卖平台

在数学上，​“图”(graph)是顶点（vertex，也可以称为节点）和边(edge)的集合，表示为图G=(V,E)，其中V是节点的集合，E是边的集合，图中的节点之间通过边相连（也可以不相连）​。

在图2.3a中，节点的集合是V={A,B,C,D,E}，边的集合是E={AB,BC,CD,BD,DE,AE}，边用其两端的节点来表示。如果两个节点之间有边，我们称两个节点相互邻接。在图2.3a中，A和B、E相互邻接，B和C、D、A相互邻接，C和B、D相互邻接，D和B、C、E相互邻接，E和A、D相互邻接。如果图中的每一对节点之间都有一条边相连，则称这个图为 “完全图”​，假设完全图中节点数量为n，则相应其边的数量为C^2 n，显然图2.3a不是完全图。

两个节点X和Y之间的路径是从X开始以Y结束的一个节点序列，在这个节点序列中，前一个节点和相邻后一个节点之间通过一条边相连。比如，在图2.3a中，节点A和节点E之间有3条路径，分别是{A,B,C,D,E}、{A,B,D,E}和{A,E}；在图2.3b中，节点A到节点E也有3条路径{A,B,C,D,E}、{A,B,D,E}和{A,E}。

图中的边分为有向边和无向边两种边。有向边在图中标明了边“入”和“出”的节点，它从一个节点出来、进入另一个节点，用带箭头的线表示，箭头的头表示边进入的节点，箭头的尾表示边出来的节点，用字母来表示，则是出的节点在前、入的节点在后，比如图2.3b中节点A和节点B之间的边表示为BA，而不能表示为AB。无向边在图中没有标明“入”和“出”的节点，用没有箭头的线表示。无向边用代表两端节点变量的字母来表示时，不区分前后顺序，比如，图2.3a中节点A和节点B之间的边，既可以表示为BA，也可以表示为AB。如果图中的所有边都是有向边，那么该图称为有向图；如果图中所有的边都是无向边，则该图称为无向图；如果图中有的边为有向边，有的边为无向边，则该图称为部分有向图。图2.3a中所有的边都是无向边，该图是无向图；图2.3b中所有的边都用带箭头的线表示，都是有向边，该图是有向图；2.3c中有的边是有向边，有的边是无向边，该图为部分有向图。

为表示有向图路径中边的方向，图2.3b中节点A到节点E的3条路径通常表示为{A←B←C→D→E}、{A←B→D→E}和{A←E}。值得注意的是，识别两个节点之间的路径数量时，不需要考虑将相邻两个节点相连的边的方向，只要有边相连即可，只有在考虑路径的“连通”或“阻断”时才考虑边的方向，相关内容将在第3章做详细介绍。

在图中，一条有向边的起点节点称为该有向边的终点节点的父节点，反之，终点节点为起点节点的子节点。在图2.3b中，节点C是节点B和D的父节点，相应地，节点B和节点D是节点C的子节点。若一条路径一直顺着箭头延伸，则称该路径为有向路径，比如图2.3b中的路径{C→D→E}。在有向路径上的所有节点中，没有一个节点在该路径中有两条边都进入该节点，或者两条边都从该节点出来。如果两个节点通过有向路径相连，则该有向路径上的第一个节点是该路径上其他所有节点的祖先，其他所有节点是第一个节点的后代。下面用父节点和子节点来说明：父节点是其子节点的祖先，是其子节点的子节点的祖先，也是其子节点的子节点的子节点的祖先，以此类推。若一个节点只有子节点没有父节点，则称该节点为根节点。在图2.3b中，节点C是节点E和节点A的祖先，节点E和节点A是节点C的后代，节点C是根节点。

如果一条有向路径从一个节点出发再回到它自身，则该路径称为环。有向图中没有环，则称为无环图。比如，图2.4a中，没有任何一个节点能够通过一条有向路径回到它自身，因此它是无环图；图2.4b中，节点X存在有向路径{X→Y→Z→X}回到自身，即图中有环，则它是有环图。

我们用图来表示变量之间的因果关系，该图则称为图模型。在图模型中，图中的一个节点对应于因果关系中的一个变量，因此，图模型中的节点也称为节点变量，节点变量的一个取值对应于一个事件。在图模型中，若节点变量X是节点变量Y的祖先，则称节点变量X（准确地说，应该是节点变量的一个取值，一般简称为节点变量）是节点变量Y的因，节点变量Y是节点变量X的果。若存在从节点变量X到节点变量Y的有向边，即节点X是节点Y的父节点，则节点变量X是节点变量Y的直接因。由于因果关系的非反身性，一个事件不能是自己的因，因此，用于表达因果关系的图通常为有向无环图，该图也称为因果图。以图2.5为例，节点C是节点F的祖先，节点C也是节点F的因。因为存在从节点C和节点Y到节点Z的有向边，所以节点C和节点Y都是节点Z的直接因。