图论及其在数学建模中的应用.pptVIP

旅行推销员问题 一个推销员要去一些城市访问他的客户然后返回出发城市，问如何选择旅行路线可以使得总路程最短？ 以城市为点，以两个城市之间的旅行距离为权，构造一个赋权完全图 G = (V , E , w) 。 推销员的旅行路线应是 G 的一条经过每个点至少一次的回路，且回路的长度尽可能短。 若由城市 x 经过城市 y 到城市 z 不会比由 x 直接到 z 更划算，则 G 的权满足三角形不等式： 当完全图 G 的权满足三角形不等式时，它的最优旅行路线将只经过每个点一次，即是一个Hamilton回路。 注：若假设两个城市之间的旅行距离为它们之间的最 短路长也可以保证 G 的权满足三角形不等式。 鞋带问题 假设 和 是穿鞋带的孔，它们分布在两条平行线上，问怎样穿鞋带需要的鞋带长度最短？ X1 X2 Xn Y1 Y2 Yn 一般地，鞋带应从 X1 穿入，交替地选择 Xi 、Yj ，经过每个孔一次，然后从 Y1 穿出。 以 和 为点构造赋权完全二分图 Kn, n ，边的权为对应两点之间的欧氏距离，则每一种穿鞋带的方法对应 Kn,n 的一条从 X1 至 Y1 的 Hamilton 路。 同一边的相邻两孔的距离； Xi 与 Yi 之间的距离。 33.30、36.93、35.44、66.26 第 1 种方法要求的鞋带长度最短，这也是日常生活中最常见的穿鞋带方法。 八、有向图 无向图反映的对象之间的关系具有对称性，即如果甲与乙有这种关系，则乙与甲也有这种关系。 但是许多关系不具有这种对称性，例如 比赛中的胜负关系，甲胜乙和乙胜甲是不同的； 自来水管道中的水、煤气管道中的气都只能朝一个 方向输送； …… 要反映上述非对称关系可以用带箭头的连线，称为弧（也可仍称为边）。把相应的图 G 称为有向图，仍记为 G = (V , E ) 。 v1 v2 v3 v4 v5 在一个有向图中忽略各条边的方向后得到的无向图称为该有向图的基图。 在一个无向图中规定各条边的方向后得到的有向图称为该无向图的定向图。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 称有向图 G 是(弱)连通的，如果 G 的基图是连通的。 称 G 是强连通的，如果 G 中任意两点之间存在有向路。 命题：强连通有向图有一条包含所有边的有向回路。 有向图上的路、回路和圈的定义类似于无向图，但指的是有向路、有向回路和有向圈。 v1 v2 v3 v4 v5 强连通 为了改善城市交通，市政部门提出把双向行驶街道改为单行道，问在改为单行道后能否保证任意两个街口能沿单行道互相到达？ 例. 该问题相当于问原来的道路图是否有定向图是强连通的，下面的命题回答了这个问题。 命题：无向图 G 有定向图强连通当且仅当 G 连通且 无割边。 在一个有向图中，以 v 为起点的边的数目称为 v 的出度，记作 ； 以 v 为终点的边的数目称为 v 的入度，记作 。 如果有向图的基图是一棵树，称为树形图。 如果树形图恰有一个点的入度为 0，其余点的入度为 1，称为出树或根树。 前缀码 通讯中常用 0 和 1 组成的字符串来表达信息，由于长度不超过 k 的 0-1 字符串有 个，表示 26 个英文字母用长度不超过 4 的 0-1字符串即可。但是各个字母使用的频率不同，为了减少信息的传输量，人们希望用较短的字符串表示使用频率高的字母。 当使用长度不同的字符串传输信息的时候，面临的一个问题是如何对接收到的信息进行译码，比如用 1 表示 e ，11 表示 d ，当接收到字符串 11 时就不知道是 ee 还是 d 。 给定一个字符串的集合，若其中任何一个字符串不是另一个字符串的前缀，则称该字符串集合为前缀码。 {1, 11} 不是前缀码，因为 1 是 11 的前缀； {00, 01, 100, 111} 是前缀码。 使用前缀码进行信息传输不会发生译码问题。 前缀码可以由二叉树产生。 若出树上每个分叉点的出度为 2，则称为二叉树。 若左侧边表示 0，右侧边表示 1，则每片树叶对应一个0-1 字符串，它由根到这片树叶的有向路上的边对应的字符组成。 0