大连理工chapter7(图论)学习.pptVIP

离散数学（图论） Discrete Mathematics 第八章 几类重要的图 图是一类非常广泛的数学模型,在现实中的许多问题, 如电网络问题,交通网络问题,运输的优化问题,社会 学中某类关系的研究,都可以用这类数学模型研究和 处理。在计算机科学的许多领域,如开关理论与逻辑 设计, 人工智能, 形式语言, 计算机图形,操作系统, 编译程序, 信息检索等方面图和图的理论也有很多 重要的应用。 8.1欧拉图与哈密尔顿图 在图8.1.1画出了哥尼斯堡城图，城的四块陆地部分 以A，B，C和D标记。欧拉巧妙地把哥尼斯堡城图 化为图8.1.2所示图G，他把陆地设为图G中的结点， 把桥画成相应地联结陆地即结点的边。 显然最小连通图不可能有圈。因为删去圈中的一条 边后仍使图连通。于是最小连通图是树。反之如果 一个连通图G不是最小连通的, 则必存在G中一条边 ei，使G-ei连通。所以ei位于一圈中,这意味着G不是 树。故可得到下面定理： 定理8.3.6 图G是树 iff G是最小连通的。 8.3 树 给定图G=V，E，G是树的等价定义是： ① G是连通且无圈; ② G是连通且|E|=|V|-1; ③ G是无圈且|E|=|V|-1; ④ G中每对结点间恰有一条链; ⑤ G是最小连通图. 8.3 树 定理8.3.7 给定树 T=V, E，若|V|≥2，则T中至少 存在两个悬挂结点。 8.3 树 对于一些图，它本身未必是树，但它的子图是树。 一个图可能有多个子图是树，其中很重要的一类树 是生成树。 定义8.3.3 给定图G=V，E。若G的生成子图T是树, 则称T是G的生成树。T中的边称为枝，是G中的边但 不为T中的边称为弦。 8.3 树 图8.3.4所示的图G=V，E，T1和T2是它的生成树。 8.3 树 定理8.3.8 图 G=V，E 有生成树T = VT，ET iff G是连通的。 8.3 树 下面讨论利用生成树来讨论加权图的最小连接问题。 设G=V，E，W是加权的连通图，对任意边 e∈E， 其权w(e)≥0。令T=VT，ET，WT是 G的一棵加权 生成树，其所有枝上的权的总和，称为树T的权， 记为w(T)。 一般说来，对于G的不同生成树T，w(T)也是不同的。 可以知道，其中必有一个最小者，而这正是人们最 为感兴趣的。 8.3 树 定义8.3.4 给定连通加权图 G = V，E，W， T0=V, ET0 ,WT0是G的加权生成树, w(T0)为 T0 的权。若对 G 的任意加权生成树 T 均有 w(T0)≤w(T)，则称T0是G的最小生成树。 8.3 树 下面给出一种求最小生成树的方法——Kruskal算法 (1956)，它的本质是树生成过程，因此得名避圈法。 定理8.3.11 设G是有n个结点的连通图,下面算法产生 的是最小生成树。 (1) 选取具有尽可能小的权的边e1；假定i＜n-1和已选 取边为e1，e2，…，ei。 (2) 在G中选取不同于e1,e2,…,ei的边ei+1,使{e1,e2,…,ei+1} 的诱导子图无圈且ei+1是满足此条件的权尽可能小 的边。重复作下去直至选出边e1,e2,…,en-1为止。 8.3 树 例8.3.4 给出世界上六大城市伦敦、莫斯科、纽约、 巴黎、北京和东京之间的航空距离(以哩为单位)如下: Lo Me Ny Pa Pe To Lo 0 5558 3469 214 5074 5959 Me 0 2090 5725 7753 7035 Ny 0 3636 6844 6757 Pa 0 5120 6053 Pe 0 1307 To 0 8.3 树 定义8.3.5 给定加权连通图 G=V, E,W, 对任意 e∈E 均有w(e)≥0，及u，v∈V。连接 u和v的链 C0：u=x1，x2，…，xk= v,