《通路和回路》由会员分享，可在线阅读，更多相关《通路和回路（4页珍藏版）》请在金锄头文库上搜索。
1、通路和回路1. 图的矩阵表示 矩阵表示便于我们把图存入计算机中，也便于对图进行代数运算。 定义 1.1邻接矩阵(adjacent matrix)以各顶点为行标和列标的方阵A,其中项人旷连接顶点i和j的边的个数。关联矩阵( incidence matrix)以各顶点为行标和以各边为列标的矩阵M,其中若顶点i与边j相关联，则Mij=1, 否则 Mij=0。ij例 1.2e1邻接矩阵： 关联矩阵：2. 通路与可达关系定义 2.1通路(walk)：在无向图中，通路是相邻的边顺次组成的序列。在有向图中，通 路中相邻的边还必须满足,前一条边的终点是下一条边的起点。位于通路最左端 的顶点称为该通路的起点(i
2、nitial vertex, start vertex)，位于最右端的顶点称为该 通路的终点(final vertex)。若a,b分别是某通路的起、终点，则称从顶点a可达 顶点b，记为ab。通路的长度：非加权图中，一条通路的长度是指其中边出现的次数。在加权图中， 一条通路的长度是指其中出现的所有边(包括重复出现的边)的权重之和。路径(trail：所含边互不相同的通路称为路径。简单路径(path,复数为paths)：所含顶点互不相同的通路称为简单路径。课本第289 页定理 14.11.定理2.2在图G的邻接矩阵A的k次幕Ak中，A厂表示从顶点i到j的所有长度 为 k 的通路的总数。推论 2.3
3、A + A2 + Ak定义2.4可达矩阵。3. 最短路径问题最短路径：距离：d(u,v)=从u到v的最短路径的长度。约定：d(u,u)=O；若u不可达v, 贝 d(u,v)=+x问题描述：给定一个加权无向图G=(V,E,W)，其中每条边e的权重W(e)为非 负实数，找出从某顶点 s 到另外一个顶点之间的最短路径。Dijkstra算法：由E. W. Dijkstra与1959年给出。1972年从ACM获得图灵奖。输入：(1)加权图G=(V,E,W)，其中IVI=n且对于任何e e E , W(e)0；(2) seV输出：从顶点 s 到 G 中每个顶点的最短路径及其长度。算法描述：(1) 在计算过
4、程中，迪克斯屈拉算法给每个顶点v赋予一个二元组(u,l), 称为顶点 v 的标记，其中 u 是一个顶点，从 s 到该顶点的最短路径已 被确定，而l等于d(s,u)+W(u,v)，它是从s出发经过顶点u而到达v 的最短路径的长度。若 l 是从 s 到 v 的最短路径长度，贝在该二元组 上添加星号*，变为(u,l)*，称为永久标记。下面为表达方便，v的标记 记为l(v)，其中的顶点和长度分别记为l1(v)和l2(v)。(2) 首先可以被赋予永久标记的是起点s，因为从s到s的最短路径就是一 个顶点s，其长度=0，显然是最短路径。因此，s的永久标记为(s,0)*。 其余各顶点的标记暂时为(s,+x).
5、(3) 用 u 表示当前被赋予永久标记的顶点。对于所有从 u 一步可达的顶点 V，若v的标记还不是永久的，并且l2(u)+W(u,v) l2(v)，则将v的标记 更新为(u, l2(u)+W (u, v)。(4) 在更新后的临时标记中，确定一个为永久标记，条件是其第 2 项最小。 重复上述(3)和(4)两步，直到所有顶点都有永久标记时为止。算法步骤：见课本第 304 页。略例 3.1 课本第 304 页。定理 3.2 Dijkstra 算法是正确的。证毕证明： 略。4. 图的连通性定义 4.1（1） 无向图：在无向图中，若从某顶点出发可达其它任何顶点，则称该无向图 是连通的（connected
6、）。在无向图中，每个极大的连通子图称为（连通） 分支（ component）。（2） 有向图：弱连通：基图是连通的。单向连通：强连通：5. 欧拉回路问题定义5.1回路（circuit）:从某个顶点出发又回到该顶点的路径称为回路。 简单回路（cycle）：不含重复顶点的回路称为简单回路或者圈。定义 5.2欧拉路径：包含所有顶点并且恰好包含每条边的路径称为欧拉路径。 欧拉回路：在一个图中，包含所有顶点并且恰好包含每条边一次的回路称为欧拉回路。注：欧拉路径即通常所谓的“一笔画”。例 5.3 试找出下列图中的一笔画。例5.4七桥问题：在Konigsberg中的一条河上有七座桥（如下图所示）。试问： 能
7、否从某一点出发，穿过所有的七座桥一次后恰好回到出发点？ 画图：欧拉在 1736 年证明，七桥问题的回答是否定的。为了理解他的理论。我们引入 关联和关联度等概念。定理 5.5（欧拉回路）在一个非平凡的无向连通图中，存在欧拉回路的充要条件 是每个顶点的关联度都是偶数。证明：（必要）（充分）证毕定理 5.6（欧拉路径）证明：留作练习。证毕中国邮递员问题：邮递员要走遍其辖区内的所有街道，其中一定存在一条最短的 遍历所有街道的回路（允许边重复），问题是如何有效地找出这条最短回路。此 问题由中国数学家管梅谷于I960年首先研究并给出算法。 属于NP难问题。6. 汉密尔顿回路和旅行商问题例6.1汉密尔顿难题
8、：1859年爱尔兰数学家汉密尔顿（Hamilton）提出了一个周 游世界的问题：有20个城市，城市之间的道路如下图所示。问能否从某个城市 出发，经过每个城市恰好一次，最后回到出发点？画图： Richard Johnsonbaugh 著，石纯一，金涬等译离散数学第 5 版第 271 页。汉密尔顿回路：包含所有顶点的简单回路。例6.2 Johnsonbaugh离散数学第273页。两个小图，一个要找出其中的汉密尔顿回路，一个要证明没有汉密尔顿回路。美国图论数学家奥勒在I960年给出了一个图存在汉密尔顿回路的充分条件：如 果图中任意两点的关联度之和大于或等于顶点个数，那么个图一定存在汉密尔顿 回路。旅
9、行商问题：Traveling SalesmanProblem,简称TSP。给定一个加权图，寻找其 中长度最小的汉密尔顿回路。例 6.3 找出下图中长度最小的汉密尔顿回路。旅行商问题的计算复杂度：目前已有的算法计算效率都比较低，其时间复杂度都 是指数级的，甚至是阶乘级别的。还没有人能设计出快速的多项式时间的算法。 多数学者相信这个问题并没有快速算法，即属于NP难问题。要证明这个猜测也 是很困难的。因为，它将解决一个世界公认的长期未解决的难题：P类问题是否 等于NP类问题？7. 二部图定义7.1二部图（bipartite）。完全二部图K 。m,n定理7.2设G是非平凡的简单无向图，则G是二部图当且仅当G没有奇圈。
