acm图论学习课件介绍

1、学习图论的误区,1 模板流 只知道每种算法的模板，不深究其中的方法、定理。 这样虽然可以做很多OJ上的题，但是在比赛时则完全不懂变通。例如最大-最小原则，如果只知道最大匹配算法模板不了解他的相关定理的话，在遇到最小覆盖的问题时很可能会找不到正确的方法，实际上这两个问题是等价的。而且如果连定义都说不明白的话，会显得你很业余。 2 只学习图论的内容 只精通图论内容，不了解其他方面的知识。虽然这样能解决很多问题，但是如果一直只把眼光放在图论上的话，就无法理解一些更复杂的算法，例如最优比例生成树，他的推导中有很多数学知识，可能很多同学就会跟我一样止步于此. 3 递归算法与非递归实现算法 图论有很多算法可以用递归实现。例如匈牙利算法，递归与非递归实现都能解决最大匹配问题，而且递归可读性与条例性更强。但在顶点数量很大时，非递归算法就能体现出他的优势：无须担心栈溢出。所以希望，学有余力的同学能够了解一下你所掌握的算法的非递归实现。,学习图论的误区,4 彻底明白算法后，每次也只是直接复制代码 效果：忘的快。亲身体验。 每次敲代码都是对算法的重新复习，甚至可以重新审视自己的算法实现，从而优化自己的代码。

2、而且时不时的切切水题可以陶冶身心. 甚至某大牛建议： 第一阶段： 练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来. ,图论基础,基本概念 路径 树 匹配,图,一个图是一个三元组，这个三元组包含一个顶点集V(G),一个边集E(G)和一个关系，该关系使得每一条边和两个顶点(也可能是相同的点)相关联，并将这两个顶点称为这条边的端点。,有向图,有向图 设V是一个非空有限集，E是V上的元素有序对的集合。二元组 G=(V,E) 称为（有向）图，V 中元素称为顶点，E中元素e=称为弧（有向边）。u称为边的始点，v称为终点。称u,v与边e=关联，u,v是邻接点。,无向图,无向图设V是一个非空有限集，E是V上的元素无序对的集合，称G=(V, E)是一个无向图 图解中既有无向边，又有有向边的图，称为混合图。混合图可以化为有向图求解。 ,多重边 在表达实际问题的图解中，E可以是多重集合，即两个结点可以有多个边相连，称为多重边（平行边）。 自环 E中的自反性图解为环形，称为自环。 简单图不出现自环或多

3、重边图解形状的图称为简单图。 一般未加特别声明时，讨论的是简单图。 图的阶 |V| 称为图的阶。即点的个数。,零图 E= 或 |E|=0 时，称G为零图。 平凡图 只有一个结点的零图称为平凡图。 完全图任何两个顶点之间都有弧相连的图称为完全图。顶点集为V的完全图 GV=(V,VV)。 n阶无向完全图记作 Kn ，其边数 = n(n1)/2,子图,子图图G=(V, E) 是 图G=(V, E) 的一个子图当且仅当: （1）V V （2） E E 上述定义中，若对u, vV，E必有E，则称G 是G的一个极大子图。 G是G的子图； 若G 是G的子图，则G 的任何子图也是G的子图； 平凡图是任何图的子图,生成子图,生成子图 G=(V, E)是 G=(V, E) 的一个子图且 V = V ，则称 G 是 G 的一个生成子图或支撑子图。 导出子图 G=(V, E) ，S V 且 S ，则 G 中以 S 为顶点集的极大子图称为 G 中由 S 导出的子图。 补图 设图G=(V, E)，则 G = (V, VVE) 称为 G=(V, E) 的 补图。,顶点度,图G中顶点v的度，记为d(v),是关联到v的

4、边的条数（v上的自环在计算度时要计算两次）。最大的顶点度记为(G)，最小顶点度(G)。 定理如果G是一个图，则d(v)=2e(G) 推论1 图中度为奇数的顶点必为偶数个。 定义 对无向图G=(V, E) ，若其任一顶点的度都为r，则称G为一个r度正则图。即(G)=(G)。 例 n 阶完全图是 n1 度正则图。 推论2 3度正则图中有偶数个顶点。,图的表示,邻接矩阵 对有向图 G=(V, R)， n=|V|，构造矩阵A=(aij)nn，其中 称A为图G的邻接矩阵。 邻接矩阵的特点 无向图邻接矩阵式对称的；节点度数是对应行1的个数。对于有向图，结点的入度是对应行的1的个数，出度是对应列上1的个数。,带权图的权矩阵,权矩阵 对带权图 G=(V, R)， n=|V|，构造矩阵A=(aij)nn，其中 称为图G的权矩阵。,邻接表表示,一个图也可以用每个结点的邻接点序列表示。例如， G = (V,E), V =1,2,3,4, E = (1,2), (2,3), (3,4), (4,1),(4,2). 可以表示为： 结点集：1，2，3，4 邻接点集: (1, 2,4), (2,1,3,4),(3,

5、2,4),(4,1,2,3). (1, 2,4)表示 结点1的邻接点序列：2，4； 实现举例：vector(add,size,clear方法),同构,图解法具有不唯一性。例： 一一对应的两个关系，具有相同的代数性质，在一定意义上可视为同一。,同构,同构 图 G=(V,E) 和 G=(V,E)，若存在一一对应映射 g : VV，使得对 v1, v2 V，v1, v2 E 当且仅当 g(v1), g(v2) E，则称 G 和 G 同构。记为: G G,自补图,自补图 图 G=(V,E)，G是G的补图。若G G，则称图G是自补的（或自补图）。,同构,如果两个图的邻接矩阵通过重新排序能得到两个相同的邻接矩阵，那么这两个图同构。 两个同构的图度序列相同，反之则不一定同构。 反例： 判断图的同构被大多数人认为是一个NP问题，至今没有好算法 。 一个NP完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP完全问题也可以在多项式时间内求解。P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。 NP问题： 什么是P问题

6、、NP问题和NPC问题：,道路与回路,有向道路 有向图G=(V, A) 中，一条有向道路指的是一个首尾相接的弧的有限非空序列。道路、回路的长度是指其中的边的数目。 P = a1 a2 ak (k1) 其中 viV ( i =0. k ), ajA ( j =1.k ) 且 aj= ( j=1. k ) 简单道路 若对任意的ij有ai aj ，称之为简单有向道路。(没有重复边的路径) 回路 若 v0 = vn ，称之为封闭的。简单封闭有向道路（闭迹）称为有向回路。 初级道路若对任意的ij有 vi vj ，称之为初级道路/基本道路。 圈若对任意的ij有vi vj 而例外地v0 = vn，称之为初级回路/圈。 无向图具有完全类似的定义。,定理 （1）基本道路是简单道路； （2）如果存在u到v的道路，则存在u到v 的基本道路； (3) n阶图的基本道路长度不超过n-1; (4) n阶图的圈的长度不超过n. （5）无向图G=(V, E)，u, v V 且 uv。若 u,v 之间存在两条不同的路，则 G 中存在一条回路。 （6）无向图G=(V, E) 中每个顶点的度均为偶数，且至少有一个顶点不是孤

7、立点，则 G 中存在一条回路。,连通性,可达性 对于有向图G=(V, A)中，若从 vi 到 vj 存在一条路，则称从 vi 到 vj 是可达的，或称 vi 可达 vj 。 对无向图 G=(V, E)，结点间的可达性是对称的。 连通性 对于无向图G=(V, E)，任意两点之间可达时，称G为连通的（连通图）。 G中的一个极大连通子图称为G的一个连通分支(连通分量)。 一个图总是由一些连通分支构成的。 G的连通分支数，记为W(G)。,有向图的连通性,强连通性对于有向图G=(V, A)，如果任意两点之间相互可达，则称G为强连通的. 弱 连通性对于有向图G=(V, A), 若不考虑弧的方向后得到的无向图是连通的，则称有向图G是弱连通的。 注意：未加特别声明时，我们讨论的都是简单图。 有向图的连通性的判定及矩阵在图论中的应用留到图论进阶中讲解。,图上的搜索,可以使用搜索的方法判断从一个顶点u到另一个顶点v是否有路径。 深度优先DFS从顶点u出发检查其后继u1是否，如果不是，则从u1开始进行深度优先搜索；如果没有后继,则回溯，直至找到或者没有可搜索的顶点。 广度优先BFS从u出发，首先检查其所有的

8、直接后继是否等于；然后依次检查这些后继的直接后继，直到找到或者没有可遍历顶点。 由于大家都应该具有一定的经验了，所以具体搜索方法就不进行详细的描述了。,Euler 回路,Euler回路 若连通图 G=(V, E) 中存在一条简单回路（无重复边）经过G的所有边，则称该回路为G中的一条Euler回路。存在Euler回路的图称为Euler图。 定理 设有连通图G=(V, E)，则下述命题等价： (1) G是一个Euler图； (2) G的每一个顶点的度是偶数；,注意定理中对图的连通性的假定； Euler回路经过图的所有边一次且仅仅一次。 定理对非简单图也成立； 定理 设连通图G=(V, E)中恰有2个顶点度为奇数，则G存在Euler道路。,有向图的Euler回路,有向图的Euler回路 若有向连通图 G=(V, A) 中存在一条简单有向回路经过G的所有弧，则称该回路为G中的一条Euler回路，称该图为Euler有向图。 定理 设连通有向图G=(V, A)，则下述命题等价： (1) G是一个Euler有向图； (2) G的每一个顶点的入度等于出度；,Hamilton 道路,Hamilton路

9、若连通图 G=(V, E) 中存在一条初级道路（无重复顶点）经过G中每个顶点一次，则称该道路为G中的一条Hamilton路。存在Hamilton回路（圈）的图称 为Hamilton图。 Hamilton路经过图的所有顶点一次且仅仅一次。 引入记号：G =(V, E)，SV。从G中去除S中的顶点及其关联边得到的G的子图记为GS。,定理 若G=(V, E)是一个Hamilton图，SV且S，则 G的子图GS的连通分支数 W(GS) |S|,定理 简单图 G=(V, E)，n=|V|，若对任一对不相邻顶点 u, vV, uv,有d (u) + d (v) n1，则G中存在一条Hamilton路。 推论上述有 deg(u) + deg(v) n 时，G为Hamilton图。,Hamilton 图,定理及其推论 给出了Hamilton图成立的充分条件，可用于对Hamilton图的肯定性判定。 Hamilton图成立的充要条件尚未得到解决，是图论求解的课题之一。 Hamilton图成立的充要条件是NP完全问题,最短路径,网络 有向图 G=(V, A) 中，给每条边 a= 赋予一个非负实数权 wij ，得到一个有向网络。 距离矩阵 对上述网络，定义 D=(dij)nn，n=|V| wij 当 A dij = 其它 带权路径长度 对上述网络，路径 v1, v2 , ,vk 的带权路径长度定义为,两点间的最短距离 对上述网络，结点vi到vj可达时， vi到vj的所有路径中具有最小带权路径长度者称为vi到vj的最短路径，其带权路径长度称为vi到vj的最短距离。 引理 在有向网络中，若路径 v1, v2 , ,vk-1 ,vk是v1到vk的最短路，则路径 v1, v2 , ,vk-1 是v1到vk-1的最短路。,Dijkstra 算法,Dijkstra算法基本思想: 如果v0至u的最短路经经过v1,那么v0到v1的路径也是v0至v1的最短路经。 按路径长度的递增次序，逐步产生最短路径. 设源点为v0 首先求出v0为源点长度最短的一条最短路径， 即具有最小权的边; 求出源点到各个顶点下一个最短路径：设其终点是u，则v0到u的最短路径或者是边，或者由一条已求得的最短路径（v0v

《acm图论学习课件介绍》由会员卡****v分享，可在线阅读，更多相关《acm图论学习课件介绍》请在金锄头文库上搜索。