图论GraphTheory教学.ppt

1,第五章 图 论 (Graph Theory),2,Konigsberg(柯尼斯堡)七桥问题,能否从河岸或小岛出发，恰好通过每一座桥一次再回到出发地?,图论的起源,3,瑞士数学家Euler(欧拉)于1736年从理论上圆满解决这个问题。,欧拉引进了图论,A,D,B,C,抽象,4,1736年 欧拉解决柯尼斯堡七桥问题图论产生 1936 年图论第一部专著出现有界图和无界图的理论 经过近六十多年的发展，逐渐成为一门相对独立的学科。,图论发展过程,5,图论的应用,网络技术的理论基础和重要的研究工具 生物和化学：区别分子式相同但结构不同的两种化合物。 计算机和通信：用于通信网络和计算机网络的设计，交通网络的合理分布 大型工程项目的计划管理。,6,图的基本概念 1,图（graph）：由结点（顶点）(vertex)和连接结点的边所构成的图形. V(G)表示图G的结点集 E(G)表示图G的边集。 图G可记为或 有n个顶点和m条边的图记为(n,m)图或称为n阶图。,7,注意：图论中研究的图只关心图的结点之间是否有边相连，不关心结点的位置和边的长短,8,图的基本概念 2(1),边(edge) 有向边(directed edge) 无向边(indirected edge) 平行边(parallel edge ) 自回路（环）(Self-loop / Ring),9,图的基本概念 2(2),边(edge) 有向边(directed edge) 端点有始点和终点之分的边。 用有序二元组表示 无向边(indirected edge) 边的两个端点都可以作始点和终点的边 端点为v1和v2的无向边表示为 (v1, v2) 或v1v2,10,图的基本概念 2(2),边(edge) 平行边(parallel edge ) 两结点之间的多条无向边或 多条方向相同的有向边称为平行边。 两个端点a和b之间平行边的条数 称为边(a,b)（或）的重数 自回路（环）(Self-loop / Ring) 两个端点重合的无向（有向）边。,v1,a,b,11,图的基本概念 3,边与结点的关系 设边e的端点为a和b 边e关联(incident)于顶点a和b（或a和b关联边e） a、b是邻接（相邻）的(adjacent),12,根据图中边的类型可将图分为： 无向图(undirected graph) 有向图(directed graph) 混合图(mixed graph) 多重图(multiple graph) 简单图(simple graph),图的基本类型（1）,13,图的基本类型（2）,无向图(undirected graph)：所有边都是无向边的图。 有向图(directed graph)：所有边都是有向边的图。 混合图：既有有向边又有无向边的图。,(c),14,图的基本分类（2）,多重图(multiple graph)：含平行边的图 简单图(simple graph)：无环和平行边的图,a,b,c,15,图的基本分类（3）,有限图(finite graph)：顶点个数有限的图 无限图(infinite graph)：顶点个数无限的图,根据图中结点的数目可分为：,16,回顾,所有边都有方向,所有边都无方向,既有有向边又有无向边,有平行边,无平行边和环,结点数有限,结点数无限,17,练习题,判断下面给出的两个图的类型。,无向图,有向图 简单图,有向图 无向图 混合图 多重图 简单图,18,底图 定向图 逆图,图的基本分类（4）,19,图的基本类型（5）,底图：将有向图G的所有有向边换成无向边，得到的无向图称为G的底图。,20,图的基本类型（6）,定向图：将无向图G中每条无向边指定一个方向所得到的图称为G的定向图。,21,图的基本分类（7）,逆图 将有向图G的每一条边的方向颠倒所得到的图称为G的逆图，记为 。,a,b,c,a,b,c,逆图,22,结点的度（1）,结点v的度: 指结点v关联的边数， 记为deg(v)或d(v)。 注意：每个环看作两条边,d(b)=2,d(a)=4,d(c)=4,d(d)=2,23,结点的度（2）,有向图中，度可分为：出度(out-degree)和入度 (in-degree) 结点v的出度: 以v为起点的有向边的数目 记为deg+(v) 或d+(v) 结点v的入度: 以v为终点的有向边的数目， 记为deg-(v)或d-(v) 有向图中结点v的度d(v)：d(v)=d+(v)+d-(v),a,b,c,deg+(c) = 2 deg-(c) = 3 deg(c) = deg+(c) + deg-(c) = 5,24,定理 1,设图G是具有n个顶点、m条边的有向图，V(G)=v1,v2,vn，则,25,定理 2 （Hankshaking）,设图G是具有n个顶点、m条边，V(G)=v1,v2,vn，则,推论：度数为奇数的顶点个数必为偶数。,26,常用的简单图,赋权图 无向完全图 有向完全图 竞赛图 正则图,27,赋权图,赋权图是顶点或边附加了信息的图。 顶点或边中附加的信息称为权。,28,赋权图例,A,F,B,C,D,E,29,普通图和赋权图,比较 对普通图，主要研究结点和边之间的拓扑关系 度，连通，通路等性质 赋权图给普通图附加了数量关系 距离，成本，代价，规模等性质,30,无向完全图,任意两个不同的顶点间都有一条边关联的无向简单图称为无向完全图 n阶无向完全图记为：Kn,K1,K2,K3,K4,K5,31,有向完全图,任意两个不同的顶点之间都有两条方向相反的有向边相连并且每一个顶点都有一条自回路的有向图 称为有向完全图,32,完全图边数,n阶无向完全图的边数是多少？ n(n-1)/2 n阶有向完全图的边数是多少？ n2,33,竞赛图（tournament）,若有向图的底图是无向完全图，称此有向图为竞赛图。,34,竞赛图名称的由来,由于循环赛中任意两名选手都要进行比赛，而且任何一场比赛都分胜负。 用每个顶点代表一名选手，如果选手a战胜了b，那么连一条从a 指向b 的有向边，这样得到的图称之为竞赛图,35,竞赛图的性质,设图G是n阶竞赛图，V(G)=v1,v2,vn，则,由G是竞赛图可知：,证明：等价于证明,而由有向图顶点度数和定理可知：,36,竞赛图的性质证明（续）,37,正则图(regular graph),所有顶点的度均相同的简单图称为正则图。若顶点的度数k，则称作k-正则图,2-正则图,3-正则图,38,图的操作,删边 删去图G中的若干条边，但仍保留被删除边的端点 删点 删去图G中的若干个顶点以及与被删点所关联的所有边,39,图的操作-删边,删e1,40,图的操作-删点,删v1,41,子图,从图G中删除若干条边或顶点所得到的图称为G的子图。,G,G1,G2,42,主子图 生成子图 边集的导出子图 点集的导出子图,子图的类型,43,主子图,在图G中删去一个顶点后所得的子图称为图G的主子图,44,生成子图,若G 是G的子图，且G含有G的所有顶点，则称G是G的生成子图,45,边集的导出子图,设E是E(G)的非空子集，则以E为边集，以E中边的端点全体为顶点集所构成的图称为G的由边集E导出的子图。 记为GE。,46,边集的导出子图示例,边集 E=(a,b),(b,e),(a,e),(a,c) 的导出子图,G,GE,47,点集的导出子图,设V是V(G)的非空子集，则以V为顶点集，以G中两端点均在V中的边的全体为边集，所构成的子图称为G的由V导出的子图。 记为GV,48,点集的导出的子图示例,点集V=a,b,c,e导出的子图,G,GV,49,回顾,原图删除一个顶点,包含原图所有顶点,由边集E及E关联的顶点构成,由顶点集V以及端点都在V中的边构成,50,练习(1),请判断下列哪些图是图G的生成子图：,A,B,C,D,G,回答：C和D,51,练习(2),请判断下列哪个图是图G的由边集Ee1,e2,e6,e7的导出子图：,A,B,C,D,G,回答：C,e1,e2,e3,e4,e5,e6,e7,e8,52,补图,设G是n阶无向简单图 在G中添加一些边后，可使G成为n阶无向完全图 由这些添加边和G的所有顶点构成的图称为G的补图 记作 G G=G,53,补图示例,v5,v1,v2,v3,v4,G,54,图的同构（isomorphism）,设图G=(V,E)和图G=(V,E) ， 如果存在着从V到V的双射映射f，使对任意的u,vV， (u,v)E（或E） ，当且仅当 (f(u),f(v)E（或E ）， 则称图G和G同构 记为GG f称为G和G的同构映射 实质：如果两个图的点能建立一一对应关系，并且点和点的邻接也能保持一一对应关系，则这两个图是同构的。 同构的图被看作同一个图.,55,图同构示例 1,b,a,c,d,G,G,G,56,图同构举示例2,57,图同构示例3,G1,G1G2,G1G3？,58,自补图,如果G和它的补图 同构，称G为自补图,G,a,b,c,d,e,a,b,c,d,e,59,5.1.2 图的表示,1、邻接矩阵 (adjacent matrix) 2、关联矩阵（incident matrix）,60,1、邻接矩阵,设G(V,E)是n阶图，设Vv1，vn。G的邻接矩阵A(G)bij是nn阶的矩阵，其中，,v1 v2 vj vn,bij=边(vi,vj)（或边）的重数,61,无向图邻接矩阵举例和性质,关于主对角线对称:aij=aji 无向简单图的邻接矩阵每行(列)和为行(列)表头顶点的度数,G,62,有向图邻接矩阵举例与性质,每行和为出度: nj=1aij=d+(vi) 每列和为入度: ni=1aij=d-(vj),G,63,2.1 无向图的关联矩阵,设G(V,E)是有n个结点和m条边的无向图， V(G)v1，vn，E(G)e1，em。 G的关联矩阵M(G)aij是nm阶矩阵，其中,e1 e2 ej em,64,无向图的关联矩阵举例,G,65,无向图的关联矩阵性质,每列和为2 每行和为d(vi),66,2.2 有向图的关联矩阵,设G(V,E)是有n个结点和m条边的有向无环图，V(G)v1，vn，E(G)e1，em。 G的关联矩阵M(G)aij是nm阶矩阵，其中,67,有向图关联矩阵举例和性质,每列和为零 每行各元素绝对值的和为该行表头顶点的度数,G,68,同构判定算法,同构判定算法（用邻接矩阵） 1、确定两个图的邻接矩阵I和II 2、计算行度（对应于出度）和列度（对应于入度） ： 行度/列度：矩阵每行/列中的个数， 3、若两个矩阵的行度集合与列度集合不同，则必不同构，否则继续。 4、同时交换其中一个矩阵的第行和第行，第列和第列。若此矩阵能变成与另一矩阵相同，则同构。 5、对所有的行列变换都试验完毕，仍不相同，则不同构。,69,同构判定算法举例,例：A(G1)的行度集合 ， 列度集合 ， A(G2)的行度集合 1， 列度集合 ，,A(G1),A(G2),70,同构判定算法举例(续1),将矩阵A(G1)的第行与第行交换、第列与第列交换，得:,A(G1),A(G2),71,同构判定算法举例(续2),再把矩阵A(G1)的第行与第行交换，第列与第列交换，得 :,=,A(G1),A(G2),72,同