衡水移动网站建设,服装网站建设项目实施报告范文,投资理财培训网站建设,wordpress怎么设置title在数学上#xff0c;“图”(graph)是顶点#xff08;vertex#xff0c;也可以称为节点#xff09;和边(edge)的集合#xff0c;表示为图G(V,E)#xff0c;其中V是节点的集合#xff0c;E是边的集合#xff0c;图中的节点之间通过边相连#xff08;也可以不相连…在数学上“图”(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的直接因。
