运筹学基础图论方法(1).ppt
《运筹学基础图论方法(1).ppt》由会员分享,可在线阅读,更多相关《运筹学基础图论方法(1).ppt(34页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第六章第六章 图论方法图论方法【引例引例引例引例1 1 1 1】K K K K nigsbergnigsbergnigsbergnigsberg七桥问题七桥问题七桥问题七桥问题 在Knigsberg城郊的Pregerl河上有两个小岛,小岛和河两岸的陆地由7座桥相连(如图a),问题是如何从河岸或岛上的某一个位置出发,能否经过7座桥正好各一次,最后回到出发地。将图抽象,用4个点代表4个被河隔开的陆地(两岸和岛屿),把桥表示为连接两个陆地之间的边,则得到图b所示的图,从而问题变为如何从图中的某个点出发,经过所有的边正好一次,最后回到这个点。【引例引例2】某河流中有几个岛屿,从两岸至各岛屿及岛屿之间的
2、桥梁如图。在一次军事行动中,问至少炸断几座桥,才能完全切断A与F的交通联系?ADBCDEFAFDECB2131212116.1图的基本概念与模型图的基本概念与模型 图是反映研究对象之间相互关系的一种工具。是在纸上用点和线画出的各种各样的示意图。太原石家庄保定灵丘原平天津塘沽通县秦皇岛密云承德北京张家口怀柔甲乙丙丁戊 图的最基本的要素是点以及点与点之间的一些连线,点表示我们要研究的对象,线表示对象之间的某种特定关系。如图中点和线赋与具体的含义和权重,称为网络图。图的名词和基本概念图的名词和基本概念边:若点与点之间的连线没有方向,称为边。如e1=v1,v2,v1,v2称为e1的端点,e1称为v1,
3、v2的关联边,v1,v2称为点相邻,e1,e2称为边相邻v1e1v2v3v4v5v6e2e3e4e5e6e7e8e9e10环:如果边的两个端点相重,称该边为环,如e10;如果两个端点之间的边多于一条,称为具有多重边,如v2,v4,无环,无多重边的图为简单图。甲乙丙丁戊弧:若点与点之间的连线有方向,称为弧,由此构成的图为有向图。图的名词和基本概念图的名词和基本概念圈:若起始点和终点是同一个点的链称为圈。例如(v1,e1,v2,e2,v4,e3,v3,e4,v1)。v1e1v2v3v4v5v6e2e3e4e5e6e7e8e9e10链:是一个点、边交错序列,如(v1,e1,v2,e2,v4)路:如果
4、链中每个项点都不相同,则称为路,如(v1,e1,v2,e2,v4)回路:若起始点和终点是同一个点的路称为回路。连通图:一个图中,任意两个顶点至少存在一条链,则称这样的图为连通图。否则称为不连通的。v1v2v3v4v5v6e2e4e5e6e7e8e1e3v7v8e9e10图的名词和基本概念图的名词和基本概念v1v2v3v4v5v6e2e4e5e6e7e1e3悬挂节点:次为1的点称为悬挂节点:次:与一个点相关联的边的数目称为次,如v1 的次为2,v5的次为3,次为奇数的点称为奇点,次为偶数的点称为偶点,次为0的点称为孤立点,如v6利用图可以对象之间的关系利用图可以对象之间的关系例:有甲、乙、丙、丁
5、、戊、己六名运动员参加A、B、C、D、E、F六个项目的比赛。打对号的是各运动员参加比赛的项目,问六个项目的比赛顺序应如何安排,做到每名运动员都不连续地参加两项比赛。ABCDEFACBFED6.2 树图和图的最小部分树一、树的性质一、树的性质一、树的性质一、树的性质例如例如性质1:任何树至少有一个悬挂节点性质2:具有n个顶点的树的边恰好为(n-1)条性质3:任何具有n个顶点、(n-1)条边的连通图是树图。树图的任意两个点之间有一条且仅有一条唯一的通路,是最脆弱树图的任意两个点之间有一条且仅有一条唯一的通路,是最脆弱的连通图的连通图树:一个无圈的连通图称为树。例:树的形成已知在五个城市间架设电话线
6、,要求任何两个城市都可以通话(允许通过其它城市),并且电话线的条数最少。方案一不连通方案三方案二有圈树问题:如何构建才能是最短路径的树问题:如何构建才能是最短路径的树问题:如何构建才能是最短路径的树问题:如何构建才能是最短路径的树最小枝权树问题最小枝权树问题最小枝权树问题最小枝权树问题v1v2v3v4v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4v5接上节、求最小树杈问题最小树杈问题最小树杈问题最小树杈问题最小树杈问题是关于在一个网络中,从一个起点出发到所有点,找出一条或几条路线,以使在这样一些路线中所采用的全部支线的总长度是最小的,或铺设费用最少。求图的最小树杈问题最小树杈问题
7、最小树杈问题最小树杈问题的方法有“破圈法破圈法破圈法破圈法”和“避圈法避圈法避圈法避圈法”。破圈法破圈法v1v2v3v5e2e3e5e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6避圈法避圈法破圈法(克鲁斯喀尔法)例:已知连接五个城市的公交线路图,在要在五个城市间架设电话线,为了便于维修要求电话线必须沿公路架设,并且电话线总长度最小。此为最小树杈此为最小树杈此为最小树杈此为最小树杈v1v2v3v4v52520109151230破圈法:破圈法:破圈法:破圈法:任选一个圈,从圈中去掉杈最大的一条边。在余下的图中重复这个步骤,直到得到一连通的不含圈的图为止。最小线路长度为:最小线路长度为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础 方法
限制150内