图论及其应用(29)复习

旅行推销员问题
问题提出: 一个推销员从公司出发, 访问 若干指定城市, 最后返回公司,要求设计
最优旅行路线。(费用最小)
数学抽象: 城市作为点, 两点间有边相连, 如果对应的城市间有直飞航班。机票价作 为每条边的权。
旅行推销员问题
求解 : 在图中求一个圈过每点恰好一次 ,
且边的权之和最小。(最优哈密顿问题；比
在一个计算机光纤网络中，给传输信道 分配波长，两信道若有公共部分，必须得到 不同的波长。要求使用尽可能少的波长。
波长分配问题转化为图论问题
每条信道看作图的一个点。两点间有边
相连当且仅当它们对应的信道有公共部
分。波长问题等价于所构造图的点着色
问题：
给图的每个点着色，有边相连的点
须着不同的颜色。所用颜色尽可能少。
1735年, 欧拉(Euler) 证明哥尼斯堡七桥问题无 解, 由此开创了数学的一个新分支---图论. 欧拉将哥尼斯堡七桥问题转化为图论问题 : 求 图中一条迹 (walk), 过每条边一次且仅一次 . 后人将具有这种性质的迹称为欧拉迹,闭的欧拉 迹也称为欧拉回路.
欧拉定理 : 连通图存在欧拉迹当且仅当图中奇 度数的点的个数至多为 2( 若为 0, 则存在欧拉回 路,这种图称为欧拉图,也称为偶图)
图的例子
交通网
互联网
计算机处理器连接方式
集成电路板
分子结构图
分子间相互作用及信息传递
具体应用
大型高速计算机：处理器的连接方式
互联网：信息传输及控制管理
大规模集成电路：布局、布线 数据库技术：数据的存储、检索 理论计算机科学： 子图理论对计算机算法研究的应用
具体应用
DNA序列分析：图的欧拉回路问题 机器智能与模式识别：图的同构 通讯网络：连通性，可靠性 印刷电路板检测: 12万5千次降为4次(《美国科学》 Scientific American, 9 (1997), 92-94 )

Prim算法及思想
• • • • • 首先我们将V分成两部分U,S U∩S=∅ U∪S=V 一开始S中只有任意以个节点 每次我们枚举每条U，S之间的边权最小的边S中 这条边的端点 删除并加入U • 我们可以每次更新S中点的这个值不需要每次枚 举边复杂度O(n^2) • 如果使用堆优化可以做到O(nlogn+nlogm)
tarjan算法
tarjan算法
拓扑排序
• 每次选择一个入度为0的点加入队列，然后 删掉这个点的所有出度
小试身手
• APIO2009 atm • 有一个城市有若干条有向道路 • 一个小偷从一个点出发想偷这个城ATM机， 他从一个点出发，最后偷完之后需要到一 个酒吧庆祝，给定道路情况，每个路口atm 的钱数和有没有酒吧，求最多能偷多少钱。 • n<=100000
小试身手
对于n<=1000我们依然可以直接暴力建出图 来进行Dijsktra算法但是对于n<=10000的测 试点，所有边一共有10^10条，我们无法存下 来但是我们发现，只有x坐标相邻和y坐标相 邻的边才有意义(为什么？)，然后就可以建出 图来用堆优化的Dij或者spfa过掉
小试身手
• 给你一个n个点的图，小Q有q个询问，每次 询问任意两点之间的最短路 • n<=200,q<=4000000
Байду номын сангаас
最短路算法
• 如果我们需要知道所有的点对之间的最短 路，可以使用floyed的传递闭包方法。 • floyed算法思想： • 我们每次选择一个中间点，然后枚举起点 和终点，用通过中间点的最短路径更新起 点和终点之间的最短路径时间复杂度O(n^3)
floyed代码实现
• 代码非常简单 • 注意枚举顺序

图论的基本概念和应用图论是数学中的一个分支，研究的是图的性质和图之间的关系。

图由节点和边组成，节点表示对象，边表示对象之间的关系。

图论的基本概念包括图的类型、图的表示方法、图的遍历算法等。

图论在计算机科学、网络分析、社交网络等领域有着广泛的应用。

一、图的类型图可以分为有向图和无向图两种类型。

有向图中的边有方向，表示从一个节点到另一个节点的关系；无向图中的边没有方向，表示两个节点之间的关系是相互的。

有向图和无向图都可以有权重，表示边的权值。

二、图的表示方法图可以用邻接矩阵和邻接表两种方式来表示。

邻接矩阵是一个二维数组，数组的行和列分别表示图中的节点，数组中的元素表示节点之间的边；邻接表是一个链表数组，数组的每个元素表示一个节点，链表中的每个节点表示与该节点相连的边。

三、图的遍历算法图的遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索从一个节点开始，沿着一条路径一直遍历到最后一个节点，然后回溯到上一个节点，再继续遍历其他路径；广度优先搜索从一个节点开始，先遍历与该节点相邻的所有节点，然后再遍历与这些节点相邻的节点，依次类推。

四、图论的应用1. 计算机科学：图论在计算机科学中有着广泛的应用。

例如，图可以用来表示计算机网络中的节点和连接关系，通过图的遍历算法可以实现网络路由和路径规划；图可以用来表示程序中的依赖关系，通过图的遍历算法可以实现代码的分析和优化。

2. 网络分析：图论在网络分析中有着重要的应用。

例如，社交网络可以用图来表示，节点表示用户，边表示用户之间的关系，通过图的遍历算法可以实现社交网络的分析和预测；互联网中的网页可以用图来表示，节点表示网页，边表示网页之间的链接关系，通过图的遍历算法可以实现搜索引擎的排名和推荐算法。

3. 运筹学：图论在运筹学中有着重要的应用。

例如，图可以用来表示物流网络中的节点和路径，通过图的遍历算法可以实现最短路径和最小生成树的计算；图可以用来表示任务调度中的依赖关系，通过图的遍历算法可以实现任务的优化和调度。

一个最小边割集。
连通度
定义：如果0<k≤λ(G),则称G是k-边连通图。
定理：图G是k-边连通图当且仅当对E(G)的任 意一个子集E1，若|E1|≤k-1，则G\E1仍是连通 图。
连通度
定理：对p 简单图G,有
(1) (G) (G),(G) (G); (2) (G) p 1,等号成立当且仅当G Kp; (3)(G) p 1,等号成立当且仅当G Kp; (4)对G的任意一个顶点u， (G) 1 (G u); (5)对G的任意一条边e，(G) 1 (G e) (G).
（v0-vk）路P，且E(P) E(W ) 。
若P是一条路，x与y为顶点，用
表示这条路。
当G为简单图时，W=v0e1v1e2v2···vk-1ekvk，可简写为 W=v0v1v2···vk-1vk。
路和圈
对于图G中两个给定的顶点u和v,若存在（u-v）路，则 必存在长度最短的（u-v）路P0，称P0的长度为u，v的 距离，记为dG(u,v)或d(u,v)。
Байду номын сангаас
连通图
定理：设D是连通的有向图，则D是强连通的当 且仅当D的每一条弧都含在某一有向圈中。
连通度
定义：设连通图G=(V,E)不是完全图,V1是V(G)的一个
非空真子集,若G\V1非连通,则称V1是G的点割集。若点 割集V1含有k个顶点,也称V1是G的k-点割集。
定义：图G是p 阶连通图，令
（G）
表示n个点的回路。
有向图D的有向途径是指交替地出现点和弧的一个有限非空序列
W=v0a1v1a2v2···akvk ，对于i=1,2,···,k,弧ai的起点是vi1,终点是vi，简称W是一条（v0-vk）有向途径。在严格有向图中， 可用v0v1···vk表示有向途径。