图与网络分析 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
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 将此问题通过图的模型描述: 下图中,点—各城市,带箭头连线—从箭尾城市到箭头城市已 订购有机票,带箭头连线旁的数字机票数量。 郑州办事处已订有的到 北京的机票数量。 6
6 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 将此问题通过图的模型描述： 下图中，点——各城市，带箭头连线——从箭尾城市到箭头城市已 订购有机票，带箭头连线旁的数字——机票数量。 成 重 武 昆 上 广 西 郑 沈 京 8 郑州办事处已订有的到 北京的机票数量
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 图论中所研究的图并非几何学中的图,也不是绘画中的图。在 这里我们所关心的仅仅是图中有多少个点,点与点之间有无线来连 接,也就是说我们研究的是某个系统中的元素—点,以及这些元 素之间的某种关系—连线。 定义:图 个图G是一个有序二元组(V,E),记为G =(V,E)其中(1)V是一个有限非空的集合,其元素称为G的 点或顶点,而称V为G的点集V=v1,V2,…,vn};(2)E是Ⅴ 中元素的无序对(vp,v所构成的一个集合,其元素称为G的边, 般表示为e=(v,v),而称E是G的边集
7 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 图论中所研究的图并非几何学中的图，也不是绘画中的图。在 这里我们所关心的仅仅是图中有多少个点，点与点之间有无线来连 接，也就是说我们研究的是某个系统中的元素——点，以及这些元 素之间的某种关系——连线。 定义：图——一个图G 是一个有序二元组（V，E），记为 G =（V，E）其中（1） V 是一个有限非空的集合，其元素称为G 的 点或顶点，而称V为G 的点集 V ={v1，v2，···，vn}；（2）E 是V 中元素的无序对(vi，vj ) 所构成的一个集合，其元素称为G 的边， 一般表示为 e =(vi，vj )，而称E 是G 的边集
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 边(无向边)没有方向的连线 弧(有向边)—带有方向的连线 无向图 有向图 简单图 多重图 完全图 二部图(偶图,双图) 子图 真子图 生成子图 点生成子图 边生成子图点的次 奇次点 偶次点 链 圈 路 回路 赋权图
8 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 边（无向边）—— 没有方向的连线 弧（有向边）—— 带有方向的连线 无向图 有向图 简单图 多重图 完全图 二部图（偶图，双图） 子图 真子图 生成子图 点生成子图 边生成子图 点的次 奇次点 偶次点 链 圈 路 回路 赋权图
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 连通图 在众多各类图中有一类在实际应用中占有重要地位的图 连通图—在图中,任意两点间至少存在着一条链。 连通图 不连通图
9 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图及其分类和术语 连通图 在众多各类图中有一类在实际应用中占有重要地位的图 连通图——在图中，任意两点间至少存在着一条链。 连通图 不连通图
图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 在图与网络分析的应用中,将面临一个问题—如何分析、 计算一个较大型的网络,这当然需借助快速的计算工具—计算机。 那么,如何将一个图表示在计算机中,或者,如何在计算机中存储 个图呢?现在已有很多存储的方法,但最基本的方法就是采用矩 阵来表示一个图,图的矩阵表示也根据所关心的问题不同而有 邻接矩阵、关联矩阵、权矩阵等。 10
10 图与网络分析 Graph Theory and Network Analysis 图与网络的基本概念 图与矩阵 在图与网络分析的应用中，将面临一个问题——如何分析、 计算一个较大型的网络，这当然需借助快速的计算工具——计算机。 那么，如何将一个图表示在计算机中，或者，如何在计算机中存储 一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩 阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有—— 邻接矩阵、关联矩阵、权矩阵等