1、运运 筹筹 学学新疆农业大学数理学院主讲 黄华第六章图与网络分析近代图论的历史可追溯到 18世纪的七桥问题 穿过哥尼斯堡城的七座桥，要求每座桥通过一次且仅通过一次。 这就是 著名的 “ 哥尼斯堡七桥 ” 难题。Euler1736年证明了不可能存在这样的路线。BACD ABCD图论与网络分析理论所研究的问题十分广泛，内容极其丰富。正如一位数学家所说： “可以说，图论为任何一个 包含了某种二元关系 的系统提供了一种分析和描述的模型。 ”一个案例 :国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱暂
2、转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快， 各办事处将其已订购机票的情况传到了总社。 根据此资料， 总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。各办事处已订购机票情况表成都重庆武汉上海西安郑州沈阳昆明广州北京成都 重庆 武汉 上海 西安 郑州 沈阳 昆明 广州 北京10 5 15 8 12 10 3010 6 15 25 10 15 88 6 14 8 18 8 10 8 2 6 10 将此问题通过图的模型描述： 点 各城市，带箭头 连线 从箭尾城市到箭头城市已订购有机票，带箭头连线旁的数字 机票数量 。成重武昆上广西 郑沈京8
3、郑州办事处已订有的到北京的机票数量。6.1 图 的基本概念与模型图论中 图是由点和边构成， 可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。图 的定 义 ：若用 点 表示研究的 对 象，用 边 表示 这 些 对 象之 间的 联 系， 则 图 G可以定 义为 点和 边 的集合， 记 作：其中 : V 点集 E 边 集 图 G区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。(v1)赵 (v2)钱 孙 (v3)李(v4)周(v5) 吴 (v6) 陈 (v7)e2e1 e3 e4 e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1 e3e4e5可 见图论 中的 图 与几何 图 、工程 图 是不一 样 的。例如： 在一个人群中， 对 相互 认识 这 个关系我 们 可以用 图 来表示。
