1、 运筹学 任课教师：饶卫振邮 箱： 手 机： 13791849391Q Q： 8316203011 图与网络优化p 引言 -图论的起源p 哥尼斯堡七桥问题11 图与网络优化p 引言 -图论的起源莱昂哈德 欧拉（ Leonhard Euler ，1707年 4月 15日 1783年 9月 18日），瑞士数学家、自然科学家。 1707年 4月15日出生于瑞士的巴塞 尔 ， 1783年 9月18日于俄国圣彼得堡去世。欧拉出生于牧 师 家庭，自幼受父 亲 的影响。 13岁时 入 读 巴塞 尔 大学， 15岁 大学 毕业 ，16岁获 得 硕 士学位。欧拉是 18世 纪 数学界最杰出的人物之一，他不但 为
2、 数学界作出 贡 献，更把整个数学推至物理的领 域11 图与网络优化p 引言 -图论的起源p 欧拉的解决思路ABCDACBD11 图与网络优化p 引言 -图论的起源p 一笔画问题：任意 1个能够 1笔画 出的点线图，所具有的特征：p 如果单线图，每个点连接的边数为偶数（欧拉圈），或者仅有两个点连接的边为奇数（欧拉链），那么这个图可以 1笔画出。11 图与网络优化p 引言 -图论的起源p 欧拉解决哥尼斯堡七桥问题结论p 由于该图既不是欧拉圈，也不是欧拉链，因此不能 1笔画出。即哥尼斯堡 7桥问题无解。ACBD11 图与网络优化p11.1 图的基本概念p 在实际生活中，点线图可以表示非常多的对象，
3、如实际的交通网络、电力光缆网络、管道网络等，虚拟网络如人际关系网络、信息传播网络等。p 概念 （ 1） 有向图、无向图；（ 2）点、弧、边；（ 3）关联边、次；p （ 4）端点、相邻点、环、多重边、简单图、多重图；（ 5）奇点、偶点、悬挂点、孤立点。p 定理：任何 1个图中奇点的个数必定为偶数个。p 初等 链（圈）、简单链（圈）的概念，例 P297图 11-9.p 连通图和不连通图，支撑子图11 图与网络优化p11.2 树的基本概念p 一个没有圈的连通图为树；p 包含 n个节点的树，一定包括 n-1条边11 图与网络优化p11.3 最小支撑树及求解方法p 任何 1个连通加权图，均可能有 1个或多个支撑子图为树，其中权重和最小的为最小支撑数，如下图去掉 任何 1条边，均为该图支撑数 ，其最小 支撑 数权重和为 9.5324 32411 图与网络优化p11.3 最小支撑树及求解方法p 破圈法p 步骤概述：找到加权连通图中任何 1个圈，去掉权重最大的边，不断找到当前图中的圈，重复该步骤，直到图中没有圈为止。53243212最小支撑 树 的 总权 重 为 ：3+2+2+2+1=10 练习题 ： P326-图 11-39
