图与网络分析 Graph Theory and Network Analysis 图与网络分析 引言 十八世纪的哥尼斯堡城中流过一条河(普雷格尔河),河上有 7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于 这样一个游戏:一个游者怎样才能一次连续走过这7座桥,回到原 出发点,而每座桥只允许走一次。没有人想出走法,又无法说明走 法不存在,这就是著名的“哥尼斯堡7桥”难题
1 图与网络分析 Graph Theory and Network Analysis 图与网络分析 引言 十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于 这样一个游戏：一个游者怎样才能一次连续走过这 7 座桥，回到原 出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走 法不存在，这就是著名的“哥尼斯堡 7 桥”难题
图与网络分析 Graph Theory and Network Analysis 图与网络分析 引言 “哥尼斯堡7桥”难题最终在1736年由数学家 Euler的一篇 论文给予了完满的解决,这是图论的第一篇论文。在后来的两百年 间图论的发展是缓慢的,直到1936年匈牙利数学家OK6nig写出 了图论的第一本专著《有限图与无限图的理论》。 在图论的发展过程中还有两位著名科学家值得一提,他们是克 希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出 了重要的贡献,而化学家凯莱在对碳氢化合物的同分异构体的数量 进行计数时推动了图论中树的计数问题的研究
2 图与网络分析 Graph Theory and Network Analysis 图与网络分析 引言 “哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇 论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年 间图论的发展是缓慢的，直到 1936 年匈牙利数学家 O.König写出 了图论的第一本专著《有限图与无限图的理论》。 在图论的发展过程中还有两位著名科学家值得一提，他们是克 希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出 了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量 进行计数时推动了图论中树的计数问题的研究
图与网络分析 Graph Theory and Network Analysis 图与网络分析 引言 图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜 想”了—历史上许许多多数学猜想之一。它描述对一张地图着色 的问题,曾经有一位数学家这样说:“对于这个问题,一位数学家 可以用不到五分钟的时间向马路上任何一位行人讲述清楚它,然后, 两人都明白这一问题,但是,两人都无能为力。”幸运的是在 1970s终于由美国的两位数学家借助大型计算机将其证明了
3 图与网络分析 Graph Theory and Network Analysis 图与网络分析 引言 图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜 想”了——历史上许许多多数学猜想之一。它描述对一张地图着色 的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家 可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后， 两人都明白这一问题，但是，两人都无能为力。”幸运的是在 1970’s 终于由美国的两位数学家借助大型计算机将其证明了
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图论与网络分析理论所研究的问题十分广泛,内容极其丰富 正如一位数学家所说:“可以说,图论为任何一个包含了某种二元 关系的系统提供了一种分析和描述的模型 下面我们来看一个案例 国庆大假期间旅游非常火爆,机票早已订购一空。成都一家旅 行社由于信誉好、服务好,所策划的国庆首都游的行情看好,要求 参加的游客众多,游客甚至不惜多花机票钱暂转取道它地也愿参加 此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此 问题。很快,各办事处将其已订购机票的情况传到了总社。根据此 资料,总社要作出计划,最多能将多少游客从成都送往北京以及如 何取道转机。下面是各办事处已订购机票的详细情况表
4 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图论与网络分析理论所研究的问题十分广泛，内容极其丰富。 正如一位数学家所说：“可以说，图论为任何一个包含了某种二元 关系的系统提供了一种分析和描述的模型。” 下面我们来看一个案例—— 国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅 行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求 参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加 此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此 问题。很快，各办事处将其已订购机票的情况传到了总社。根据此 资料，总社要作出计划，最多能将多少游客从成都送往北京以及如 何取道转机。下面是各办事处已订购机票的详细情况表：
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 各办事处已订购机票情况表: 成都重庆武汉上海西安郑州沈阳「昆明「广州北京 成都 10 5 15 8 12 10 30 重庆 5 6 15 25 武汉 10 上海 15 西安 8 6 郑州 14 沈阳 18 昆明 8 10 州 8 2 6 10
5 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 各办事处已订购机票情况表： 成都 重庆 武汉 上海 西安 郑州 沈阳 昆明 广州 北京 成都 10 5 15 8 12 10 30 重庆 5 6 15 25 武汉 10 上海 15 8 西安 8 6 郑州 14 8 沈阳 18 昆明 8 10 广州 8 2 6 10