14 第十四次课(图论).ppt

Hongzhi Qiao, XiDian Univ. 图论最早处理的问题是哥尼斯堡（konigsberg）城pregel河上的七桥问题。1736年，瑞士数学家 L.Eluer 在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点，从而被誉为图论之父。 问题是这样的：在公元十八世纪的东普鲁士有个哥尼斯堡城（后属于苏联立陶宛苏维埃社会主义共和国，现名为加里宁格勒；现属于立陶宛共和国）。哥尼斯堡城位于pregel河畔，河中有两个岛，城市中的各个部分由七座桥相连。当时，城中的居民热衷于这样一个问题，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，但当地的居民和游人做了不少的尝试，却都没有取得成功。 后来，在1736年，瑞士的数学家L.Euler解决了这个问题。他将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条线，这样图1就转化为图2了。此时，哥尼斯堡七桥问题归结为：在图2 所示的图中，从 A, B, C, D 任一点出发，通过每条边一次且仅一次而返回出发点的回路是否存在？ 欧拉断言这样的回路是不存在的。理由是：从图2中的任一点出发，为了要回到原来的出发点，要求与每个点相关联的边数均为偶数。这样才能保证从一条边进入某点后，再从另一条边出去，从一个点的不同的两条边一进一出才能回到出发点，而图2中的A, B, C, D全是与奇数条边相连，由此可知所要求的回路是不可能存在的。 Leonhard Euler （1707-1783） 瑞士数学家 8.6 最短道路问题 Shortest Path Problem 定义1： 简单图的着色/coloring 定理 四色定理/four color theorem [定义]连通性/connectivity： 设Ｇ＝（Ｖ，Ｅ）， （Ｖ0，Ｖ1，…，Ｖk） 是G中的一条道路，则称Ｖ0到Ｖk连通/connective或可达/。 说明：对无向图而言，若Ｖ0到Ｖk可达，则Ｖk到Ｖ0也可达。对有向图而言则未必。 第八章 --- 图论 [定理1] 任意一个连通无向图的任两个不同顶点都存在一条简单道路。 [定义]无向图的连通性： 若Ｇ＝（Ｖ，Ｅ）中任两个不同顶点都连通，则称此无向图是连通的/connected。 第八章 --- 图论 [定义]连通分图/connected components： 图Ｇ可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为Ｇ的连通分图。 [定义]无向图的连通性： 若Ｇ＝（Ｖ，Ｅ）中任两个顶点都连通，则称此无向图是连通的/connected。 第八章 --- 图论 [定义]有向图的连通性： (1)弱连通： 若Ｇ＝（Ｖ，Ｅ）对应的无向图是连通图，则称Ｇ为弱连通/weakly connected。 (2）强连通： 若Ｇ＝（Ｖ，Ｅ）中任两点间都有路，即对ａ与ｂ，ａ到ｂ可达，ｂ到ａ可达，称Ｇ为强连通/strongly connected。 第八章 --- 图论 第八章 --- 图论 第八章 --- 图论 例：用图描述一台自动售货机，只用５分，１０分二种硬币，满１５分后压按钮，选择一块巧克力，钱多了不找还。 第八章 --- 图论 顶点：ａ：０ 分边： ５：投５分 ｂ：５分 １０：投１０分 ｃ：１０分 ｐ：压按扭动作 ｄ：≥１５分 表示已投入钱的状态 表示一种动作 自动售货机：有向加权图描绘得很清楚 （1）钱数不够，压按扭，不起作用 （2）钱数够了，压按扭，给过糖果回到０分状态 （3）钱超过１５分，再加钱白加 第八章 --- 图论 [定义]欧拉道路（回路）： Ｇ＝（Ｖ，Ｅ），称包含Ｅ中所有边的简单道路为欧拉道路/Euler Path/E道路。 包含Ｅ中所有边的简单回路为欧拉回路/Euler Circuit/E回路 。 第八章 --- 图论 [定理1]（欧拉定理）： 没有次为０的孤立顶点的无向图存在欧拉道路的充要条件是： (1)图是连通的； (2)图中奇次顶点个数是０个或2个。 第八章 --- 图论 说明： 哥尼斯堡七桥问题，由于四个顶点都是奇次的，不可能有欧拉道路。 应用与推广： （1） 一笔画问题； （