运营研究与图形分析.pptVIP

第 八 章图 与 网 络 分 析;几个图论问题;;中国邮路问题 我国数学家管梅谷教授1962年首次提出，并给出了它的解法(奇偶点图上作业法)。 邮递员在送报刊信件时，从邮局出发，一般地每次都要走遍所负责的全部街道，任务完成后返回邮局。那么邮递员应该选择哪一条路线才能以尽可能少的路程走完所有的街道呢？;有A、B、C、D、E五支球队，他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次，B队和A、C队比赛过，D队和E、C队比赛过，E队和A、D队比赛过。;如果在比赛中： A胜E， B胜C， A胜D， C胜A， E胜D， A胜B，;图的基本概念;相邻点：两点之间的边属于E 相邻边：如果两条边有一个公共端点 环：边的两个端点相同 多重边(平行边)：两个点之间有多于一条边(弧) 多重图: 无环但允许有多重边的图 简单图：无环且无多重边的图 注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边 ;端点的次d(v)：点 v 作为端点的边的个数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边， 孤立点：d(v)=0；空图：E = ?，无边图。 ;图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列。如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , … , vn-1 , en , vn v0 , vn分别为链的起点和终点 简单链：链中所含的边均不相同。 初等链：链中所含的点均不相同，也称通路。 圈：起点和终点相同的链。;;通路：由两两相邻的点及其相关联的弧构成的点弧交错序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , … , vn-1 , en , vn v0 , vn分别为链的起点和终点 回路：通路的起点和终点相同 连通图：图中任意两点之间均至少有一条链相连，否则称作不连通图。 任何一个不连通的图都可以分为若干个连同子图，每一个都称为原图的一个分图;例如图中，v1和v6之间没有通路，因此它不是连通图， 而如果去掉v6，则构成一个连通图。 ;子图 设 G1 = [ V1 , E1 ] , G2 = [ V2 , E2 ] 子图定义：如果 V2 ? V1 , E2 ? E1 称 G2 是 G1 的子图； 真子图：如果 V2 ? V1 , E2 ? E1 称 G2 是 G1 的真子图； 部分图：如果 V2 = V1 , E2 ? E1 称 G2 是 G1 的部分图；;;若T是图G＝(V，E)的部分图，且T是树，则称T为G的部分树。 若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称为G的一个余树。 余树不一定是树！;网络 点和边带有某种数量指标的图称为网络，或称为赋权图。;最小树问题：选取网络中的部分图，使得网络连通，且使总权数最小。 在实际应用中，经常碰到需要求一个赋权连通图的最小树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。 求最小树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为取边避圈法。 ;取边避圈法 方法步骤：依次在图中取一个权值最小的边，或者是相对最短的边，并且在每次取边时都不能与已取的边构成圈。 首先在图中选最短的边，并且将与之关联的两个点标记△， 然后每次都在标记点和未标记点间可能的边中取一个最短的边，并将新选的边标记， 重复上述过程，直到所有的点均被标记了。;;; 破圈法;课堂练习： P224 2.a） ;问题定义：在一个赋权图上求一个圈，经过图中每一条边至少一次，使圈中各边权值的总和为最小。; 欧拉链与欧拉圈 经过且仅经过图中每一条边一次的链称为欧拉链，经过且仅经过图中每一条边一次的圈称为欧拉圈 ;;;奇偶点表上作业法 (1)找出奇点(一定为偶数个)，在每两个奇点之间找一条链，在这些链经过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是不一定是路线最短的，所以需要检验和调整。 (2)检验增加的边的权值是否是最小的。 定理3 假设M是使得图G中不含奇点的所有增加边，则M是权值总和为最小的增加边的充分必要条件是： 1)图G中每条边上最多增加一条边； 2)在图G的每个圈上，增加的边的总权值不超过该圈总权值的一半。 如果上述两个条件都满足则已经找到权值最小的欧拉圈 否则转入3)