图论基础ppt课件

图论的基础在信息学奥林匹克中占有很大的比重，它可以用来解决许多实际问题。(1)图的描述(2)图的表示(3)引用：如果任何六个人在一起，必须有三个互相认识的人或三个互不认识的人。1.理解模式结构。该图是图案结构的缩写。它是一种复杂的非线性数据结构。图的二元组定义为G=(V，E)，其中V是一组非空顶点，E是V上的一组二元关系。图的分类：无向图，有向图，加权图，无向图：边集中的无向边。有向图：边集中的有向边。加权图：边上有权重的图。也被称为网。(有向加权图，无向加权图)注意：没有加权的图也可以被认为在所有边上都有1的权重。上面的哪些图是无向图，哪些是有向图，哪些是加权图？(1): V (G1)=V1、V2、V3、V4、V5、V6 ；E (G1)=(v1，v2)、(v1，v3)、(v1，v4)、(v1，V5)、(v2，V5)、(v3，V5)、(v3，V6)、(v4，V6)、(V5，V6)，练习(2): v (G2)=va，VB，VC，VD，ve ；E (G2)=，7，2，顶点度，进入度，退出度，顶点度：与顶点相关的边数，分为奇点和偶点。对于有向图：关联度和退出度的划分，关联度：顶点的关联边数。结果：顶点的输出边数。注意：顶点v的度数等于它的进入度和退出度之和。问题2:有向图中所有顶点的度数之和是所有顶点的度数之和(大于、等于、小于)；问题3:任何无向图都必须有(偶数和奇数)奇点。以上是关于图的度的三个定理，9，完全图：在无向图中，每两个顶点之间有一条边；如果是有向图，每两个顶点之间有两条对边。完全图、稠密图、稀疏图、稠密图：当图的边数接近完全图时。稀疏图：当一个图的边数远远少于一个完整图的边数时。n*(n-1)/2，n*(n-1)，10，路径：对于图G=(V，e)，对于顶点a，b，如果有一些顶点序列x1=a，x2，xk=b (k1)，和(xi，xi 1)E，I=1，2.k-1，那么顶点序列x1，x2，xk是从顶点a到顶点b的路径，路径上方的数字(即k-1)称为路径长度。顶点集x1，x2，xk也称为连通集。简单路径：如果路径上的顶点不同，但起点和终点可以相同，则路径称为简单路径。具有相同起点和终点的简单路径称为循环(或环)。4，子图，图G，图G，设置两个图G=(V，E)和G=(V，E)，如果V是V的子集，E是E的子集，那么G是G的子图，5，路径和循环，11，路径和简单路径的例子：左边的1-2-3是长度为2的简单路径，而1-3-4-1-3不是简单路径；右图1-2-1是一个循环。连通图：如果任意两个顶点相连，无向图就称为连通图。否则，它被称为未连通图。左边是连接图。连通分支：无向图的连通分支被定义为图的最大连通子图，左边的连通分支是它自己。连通性：在一个图中，如果从顶点U到顶点V有一条路径，那么U和V就是连通的；6.已连接和已连接的组件。注意：任何连通图只有一个连通分量，即连通分量本身，而非连通图有多个连通分量。强连通分量：有向图的强连通分量被定义为图的最大强连通子图。右图包含两个强连通分量，一个是由1和2组成的子图，另一个是由3独立组成的子图。强连通图：在有向图中，对于任意两个顶点U和V，都有一条从U到V的有向路径，也有一条从V到U的有向路径，那么有向图称为强连通图。右图不是强连通图。7，强连通图和强连通分支，注意：强连通图只有一个强连通分支，即本身，非强连通图有多个强连通分支。与奇数编号的人握手的人数是偶数。在一场国际象棋比赛中，任何两个玩家最多只能玩一盘，每个玩家至少只能玩一盘。试着证明：总是可以找到两个玩家，而且他们玩了完全相同数量的游戏。如果每个玩家都与所有其他玩家竞争，并且玩家数量为n，则计算竞争中的总集数。n个运动队已经为n 1场比赛安排了一场比赛。测试证明有一支球队至少参加了3场比赛。15，2，模式结构存储，模式结构存储分为静态存储和动态存储。静态存储主要包括邻接矩阵和边集数组，而动态存储主要包括邻接表。1.邻接矩阵，邻接矩阵：它是表示顶点之间邻接关系的矩阵。设G(V，e)是一个有n个顶点的图，顶点数是1，2，那么g的邻接矩阵是如下定义的n阶方阵。16，有向图的邻接矩阵表示，无向图的邻接矩阵表示，17，有向加权图的邻接矩阵表示，无向加权图的邻接矩阵表示，18，图的邻接矩阵表示算法描述(以无向加权图为例)，过程创建1(GA)；图由邻接矩阵存储 BegInfori :=1 Tondo for J :=1 Tondo Ga1，J:=Maxint；Fork:=1toedo 建立邻接矩阵 Beginrad(I，j，w)；读取边缘两端的序列号(Vi，Vj)和边缘上的重量GAi，j:=w；大会j，I:=w；结束。结束。邻接表：一种图形表示方法，它为图形中的每个顶点建立一个相邻的链表，并用向量存储它们的标题指针。注意：邻接矩阵是按顺序存储的，而前导表是图的链式存储方式。对于边节点：邻点域，链域，对于边节点：邻点域，权域，链域，20，图是无向图，其邻接表是：21，图是有向图，其邻接表是：邻接表，逆邻接表，22，输入样式：421332，23，图的邻接表构造算法描述(以有向图为例)，程序创建2(总账)；该图存储在邻接表中比利时信息：=1顿多贝格里德(一世)。数据)；1。结束；Fork:=1toedo 建立邻接列表 Begin rard(I，j)；读入一条边的两个端点的序列号新的；s.adjvex:=j；s.next:=GLi.链接；1。结束。结束。24，3，边集数组，边集数组：使用一维数组存储图形中所有边的图形表示。无向加权图的起点、终点、权重、边集数组表示，25、图的边集数组表示算法描述(以无向加权图为例)，过程创建3(ge)；该图由边集数组存储 BeginFork :=1至doBeginRead (I，J，W)；读入一条边的两个端点的序号和权重(Vi，Vj)通用电气k。重量：=温；结束。26，4，图的三种存储结构的比较(N阶E边):27，例1:加权无向图的邻接矩阵的建立，程序图(输入，输出)；constmax=1E5。n=10typegraph=数组1.n，1.nof ral；varI，j，k，e :整数。g :图表；w:realBeginfori:=东多弗j :=1东多i，j:=最大值；改为(e)；fork :=1 todeobeginread(I，j，w)；gi，j:=w；gj，I:=w；结束；输入样式：52513741223248，28，for I :=1 tondobeginforj :=1 tondorwrite(gI，j)；writeln结束；结束。29，fork :=1 todeobeginread(I，j)；新的；s.adjv:=j；s.next:=gi.链接；一世。结束；结束。procedurecreatelist(varg : adj 1)；begin rad(n，e)；13360=1东多贝金里德(一世)。gi。结束；例2:建立有向图链表，输入样式：71224323534654，30，1，图的深度优先遍历，分别对下面两个图进行深度优先遍历，写出遍历结果。注：分别从A和V1开始。在左边，从顶点A开始，深度优先遍历的结果是：A，B，C，D，E，G，f。在右边，从V1开始的深度优先遍历的结果是：V1，V2，V4，V8，V5，V3，V6，V7。图的遍历分为深度优先遍历和宽度优先遍历。对于连通图，深度优先遍历的递归过程如下：用邻接矩阵存储图形开始访问顶点1；拜访I:=真；对于j :=1东(未访问j)和(ai，j=1)然后是(j)；结束。上述dfs(i)的时间复杂度为0(n * n)。对于非连通图，dfs(i)被调用一次，即顶点I所在的(强)连通分支按照深度优先顺序被依次访问，只要：fori:=当深度优先搜索每个未被访问的顶点如果未被访问的顶点(I)被添加到主程序中；如果图存储在邻接表中，那么深度优先遍历的递归过程呢？Procedure fs(I :整数)；带邻居表的图形存储开始访问顶点1；参观I:=真；p:=gi。链接；whilepnildobeginj:=p.adjvex；如果没有访问j然后dfs(j );p:=p.next；结束。结束。邻居表33，分别从a和V1对下面两个图进行广度优先遍历，并写出遍历结果。2。图的广度优先遍历。从左边的顶点A开始的广度优先遍历的结果是：A，B，D，E，F，C，G。从右边的V1开始的广度优先遍历的结果是：V1，V2，V3，V4，V5，V6，V7，V8，34，深度优先遍历和广度优先遍历的比较：深度优先遍历实际上是尽量取“顶点表”；然而，广度优先遍历是沿着顶点的“边表”尽可能多地访问，然后访问与边表的顶点相对应的边表。因此，需要保存边表的顶点(排队，先进先出)，以便进一步执行广度优先遍历。以下是广度优先遍历的过程：35，时间：o (n * n)，程序bfs (i:整数)；广度优先遍历，图用邻接矩阵表示开始访问顶点1；拜访I:=真；Apex i进入q团队；当队列q不为空时，dobeginhead :=head 1；v :=q磁头；对于j :=1时延(未访问j)和(v，j=1时，开始访问顶点j；拜访:=真；Apex j进入q团队；结束；结束；结束；结束。定义：欧拉路径穿过图的每一边一次，并且只穿过一次，并且穿过每个顶点。欧拉路径在图中穿过每条边一次并且只穿过一次，并且穿过每个顶点的环。欧拉图带有欧拉路径。定理1:欧拉路径的条件：图是连通的，并且有0或2个奇点。如果有两个奇点，欧拉路径必须从一个奇点开始，以另一个奇点结束。定理2:欧拉路径的条件：图是连通的，没有奇点。下列数字能一笔画出吗？练习：练习2，“两只蚂蚁竞赛问题”。两个蚂蚁分别在图G中的顶点A和B，并且图中每条边的长度相等。甲提议与乙竞争：从他们的顶点开始，遍历图中的所有边，最后到达顶点丙。如果他们的速度相同，谁先到达目的地？39，3)有许多算法可以找到欧拉路径和欧拉路径。以下是基于递归的经典算法框架：查找电路(节点一)；当节点I有邻居时，选择任何邻居J；删除边缘；查找电路(节点j)；电路电路 :=节点I；电路：=电路1；如果您正在寻找欧拉路径，请执行find _ circuit在任何一点上；如果搜索到欧拉路径，则查找电路；对奇点执行；该算法的时间复杂度为0(m n)。定义：哈密尔顿路径在图中穿过每个顶点一次并且只穿过一次。汉密尔顿循环通过该循环一次，并且对于图中的每个顶点仅通过一次。哈密尔顿图带有哈密尔顿环的图。(2)判断：不幸的是，还没有找到区分哈密顿回路和路径的充分必要条件。42、确定下图中是否有汉密尔顿电路、路径。到目前为止，还没有有效的算法来寻找哈密尔顿环，只能通过搜索来解决。(顶点集不能为空，关键是把什么抽象成顶点，什么抽象成边。)2。决定使用哪种算法。写一个程序。举出应用45的例子。1.中风问题。)问题描述对于给定的图形，程序判断是否可以画出一个笔画。如果可以，请输出一个笔画的顺序，否则，输出“无解决方案！”。输入格式输入文件由n 1行组成，第一个行为图的顶点数n，接下来的n行(每行n个数据)是图的邻接矩阵，Gi，j=1表示顶点1和顶点J与边相连，Gi，j=0表示顶点1和顶点J没有边相连。输出格式如果可以绘制一个笔划，则输出由一个笔划绘制的顶点的顺序，否则输出“无解决方案”。样本输入601001101101010100110110010110样本输出 5-1-2-3-4-2-6-4-5-6-1，46，程序1；con