文档介绍：第六章图论方法【【引例引例 1 1】】K K? ?nigsberg nigsberg 七桥问题七桥问题在K? nigsberg 城郊的 Pregerl 河上有两个小岛,小岛和河两岸的陆地由 7座桥相连(如图 a),问题是如何从河岸或岛上的某一个位置出发,能否经过 7座桥正好各一次,最后回到出发地。将图抽象,用 4个点代表 4个被河隔开的陆地(两岸和岛屿),把桥表示为连接两个陆地之间的边,则得到图 b所示的图, 从而问题变为如何从图中的某个点出发,经过所有的边正好一次,最后回到这个点。【【引例引例 2 2】】某河流中有几个岛屿,从两岸至各岛屿及岛屿之间的桥梁如图。在一次军事行动中,问至少炸断几座桥,才能完全切断 A与F的交通联系? AD B CD EF AF DE C B 213 1 21 21 1 § § 图的基本概念与模型 图的基本概念与模型 图是反映研究对象之间相互关系的一种工具。是在纸上用点和线画出的各种各样的示意图。太原石家庄保定灵丘原平天津塘沽通县秦皇岛密云承德北京张家口怀柔甲乙丙丁戊图的最基本的要素是点以及点与点之间的一些连线, 点表示我们要研究的对象,线表示对象之间的某种特定关系。如图中点和线赋与具体的含义和权重,称为网络图。图的名词和基本概念边:若点与点之间的连线没有方向,称为边。如 e 1 =[ v 1, v 2 ], v 1, v 2称为 e 1的端点,e 1称为 v 1,v 2的关联边, v 1,v 2称为点相邻,e 1,e 2称为边相邻 v 1e 1v 2v 3v 4v 5v 6e 2e 3e 4e 5e 6e 7e 8e 9e 10 环:如果边的两个端点相重,称该边为环,如 e 10;如果两个端点之间的边多于一条,称为具有多重边,如[ v 2, v 4 ] ,无环,无多重边的图为简单图。甲乙丙丁戊弧:若点与点之间的连线有方向,称为弧,由此构成的图为有向图。图的名词和基本概念圈:若起始点和终点是同一个点的链称为圈。例如(v1 ,e1 ,v2 , e2 ,v4 ,e3 ,v3 ,e4 ,v1 ) 。 v 1e 1v 2v 3v 4v 5v 6e 2e 3e 4e 5e 6e 7e 8e 9e 10 链:是一个点、边交错序列, 如(v 1 ,e 1 ,v 2 ,e 2 ,v 4 ) 路:如果链中每个项点都不相同,则称为路,如(v 1 ,e 1 ,v 2 ,e 2 ,v 4 ) 回路:若起始点和终点是同一个点的路称为回路。连通图:一个图中,任意两个顶点至少存在一条链,则称这样的图为连通图。否则称为不连通的。 v 1v 2v 3v 4v 5v 6e 2e 4e 5e 6e 7e 8e 1e 3v 7v 8e 9e 10 图的名词和基本概念 v 1v 2v 3v 4v 5v 6e 2e 4e 5e 6e 7e 1e 3悬挂节点:次为 1的点称为悬挂节点: 次: 与一个点相关联的边的数目称为次,如v 1的次为 2,v 5的次为3,次为奇数的点称为奇点,次为偶数的点称为偶点,次为 0 的点称为孤立点,如 v 6利用图可以对象之间的关系利用图可以对象之间的关系 例:有甲、乙、丙、丁、戊、己六名运动员参加 A、B、 C、D、E、F六个项目的比赛。打对号的是各运动员参加比赛的项目,问六个项目的比赛顺序应如何安排,做到每名运动员都不连续地参加两项比赛。 A BC DE F A B C D E F 甲√√√乙√√√丙√√丁√√戊√√√己 √√√ACBFED § § 树树图和图的最小部分树图和图的最小部分树一、树的性质一、树的性质例如性质 1:任何树至少有一个悬挂节点性质 2:具有 n个顶点的树的边恰好为(n-1) 条性质 3:任何具有 n个顶点、(n-1) 条边的连通图是树图。 树图的任意两个点之间有一条且仅有一条唯一的通路,是最脆弱的连通图树:一个无圈的连通图称为树。例:树的形成例:树的形成 已知在五个城市间架设电话线,要求任何两个城市都可以通话(允许通过其它城市),并且电话线的条数最少。方案一不连通方案三方案二有圈树问题:如何构建才能是最短路径的树问题:如何构建才能是最短路径的树——最小枝权树问题最小枝权树问题 v 1v 2v 3v 4v 5 v 1v 2v 3v 4v 5v 1v 2v 3v 4v 5v 1v 2v 3v 4v 5 接上节、求最小树杈问题接上节、求最小树杈问题最小树杈问题最小树杈问题是关于在一个网络中,从一个起点出发到所有点,找出一条或几条路线,以使在这样一些路线中所采用的全部支线的总长度是最小的,或铺设费用最少。 求图的最小树杈问题最小树杈问题的方法有““破圈法破圈法””和““避圈法避圈法””。破圈法 v 1v 2v 3v 5e 2e 3e 5e