论文研究-不包含六边形的图的构造算法 .pdf

所需积分/C币:21 2019-08-28 14:52:03 524KB .PDF

不包含六边形的图的构造算法,张涵硕,田春子,给定一个图簇ψ={H1, H2, ..., Hm},不包含图簇ψ的边数最多的图称为极图,极图集合和其中极图的边数分别用EX(n; ψ)和ex(n; ψ)表示。对于只��
国武技论文在线 性要好,所以也研究基于八边形来扩展构造图。因此本文主要基于三种母图来扩展构造 不含的图,分别为星图、和,简记为,和,如图所小。 图种母图 下面先给出最简单的一种扩展方式,即基于母图构造不含的图。有如下引坦: 引理如果基于母图扩展不含的图,则得到个顶点的图的边数为: 1-1y4k×10当(y-1) 1-1y/4」×10+1当1-1 时; (-1)/4」×1+3当(y-1) 时; (1-14」k×10+6 时 证明:按星图结构的扩展方式如下:取个点作为星图的中心点;将剩余的个顶 点每个分成组,每组顶点与这个中心点构成个,则总共构成」个;余下 的 L-」-个顶点与中心点构成一个。由j这种扩展所得的图包含 块,每个块的顶点数不超过个顶点,所以它一定不包含 基于母图和的构造过程则比较复杂,下面先给出几个引理 引理对于母图和及其他结构类似的图来说,如果按照下面的方式对 ,,中的所有边进行如下扩展: ()将条边扩展成为个。如图所示,在边上添加三个点(新添加的点用 实心点表示)与和相连,这个点构成一个(新添加的边用虚线表示); ()将条边扩展成为个-。如图所示,在相邻的两条边上添加两个点 和相连,构成个 令表示扩展后得到的新图,则通过上述两种方式扩展后的得到的图中都一定不会 包含 图基丁母图扩展边的两和方法 山国武技论文在线 证明:如果按照上述两种方式对母图的边进行扩展,可以看出:无论是将条边扩展成 个,还是将相邻的两条边扩展成一个一,扩展完成的块(其两个割点为和)的 顶点数均为,所以一定不包含。另一方面,由于这两种扩展都没有缩短和之间的 路径长度,所以也不会在图的其他部分产生新的。 从图中可以看出,在扩展母图边的过程中,会新添加一些点。在本文中,对于将一条 边扩展成一个的情况,需要在母图上添加个新的顶点。将其中的一个点作为可以继续 扩展的顶点,这种顶点称作可用点,用表示。对于将相邻的两条边护展成一个-的情 形,则将这两条边的关联点(即的中间点)作为可用点。在图中,可用点用红色实心 点表示。 图两种情况中的可用点 在引理构造出的新图的基础上,利用可用点还可以对其进一步扩展。有如下引理 引理利用可用点,按照如下方式对新的母图进行扩展: ()在图中找与可用点距离为的点(即到该点有一条最短路径),如果 找到,不妨设为点。则添加一个新顶点,并添加两条边和,如图所示 ()在图中找与可用点距离为的点(目到该点有一条最短路径),如果 找到,不妨设为点。则添加一个新顶点和,并添加三条边 和,如图 所 令表小扩展后得到的新图,则通过上述两种方式扩展后得到的图中都一定不会包 图利用可用点添加点和边 证明:由于从可用点开始,寻找到的路径或都是这两个点间的最短路径,所以无 论是对于路径添加一个点和两条边,还是对于路径添加两个点和三条边的情形,它们 所构成的圈的长度均为。因此,新图中一定不会包含。 山国武技记文在线 通过对顶点数为6≤≤28不含的极图结构的研究发现,这些极图的对称性较好, 般都可以画成左右对称的形式。基于这个观察,并且考虑到降低算法的时间复杂度,本文将 构造对称性较好的不含的图。因此,将基于引理和利用对称的方式对母图进行扩展, 分两种情形 )对基于和个可用点新添加的两条边,按如下两种方式扩展:一种是将两条边 各自护展成为一个,即相邻的两条边扩展成为两个,这种护展方式会产生两个新的可 用点和,如图所示;另一种是将相邻的两条边护展成一个-,这种方式会产生 个新的可用点,如图所示。 -c- 图基于的两种扩展方式 ()对基」和个可用点新添加的三条边,按如下两种方式扩展:一种是将新添加 的三条边均扩展成为一个,扩展后会产生三个新的可用点、和,如图所示 另一种是将新添加的第一条边和第三条边分别扩展成一个,对第二条边不扩展,这种方 式会产生两个新的可用点和,如图所示。 图基于的两种扩展方式 下面来分析一下基于和对图进行扩展的优缺点。首先给出如下目标两数来表示扩 展效率 f(e)=egenum vertex ni 其中 表示每次新添加的边的数量 表示每次新添加的顶点的个 数。越大,衣明扩展的效率越高。如果选择进行扩展,则每次消耗个点可以添加的 边数为两条,因此 ;如果选择进行扩展,则 ;如果选择进行扩展,则 如果选择或进行扩展,扩展效率会下降得史低。因此,在本文选择基于 和进行扩展。 算法描述 本节将提出一种基于母图和的新的不含的图的构造算法 。为了方便描述,令表示顶点数为且不包含的图集 国武技论文在线 且g 表示集合中边数为的图集合。 首先,根据引理和引理设计两个子算法: 算法根据引理扩展母图。输入一个母图和顶点数,根据引理将母图的一条边扩 展为一个,相关联的两条边扩展为一个一,返回值为一个结构体结构体 包含如下信息:新图、可用点、构造图后剩余的顶点个数、图当前的边数。 扩展母图的边的算法如算法所示,令表示该算法 输入:顶点个数和母图 根据对称性的原则,将母图的边扩展成或 输出:包含可用点及其他信息的结构体 算法扩展母图的边的算 由算法可知,返回值包含有可用点和新图。下一步将根据这些可用点找 路径或,然后添加点和边以扩展母图。 算法根据引理扩展母图。输入新的母图和可用点,根据引理从可用点出 发,找路径或,然后添加点和边;返回值为含有新的母图的结构体。扣展母图 的算法如算法所示,令表示该算法。 输入:可用点和新的母图 从出发,找或,然后添加点和边 输出:包含有新的母图的结构体 算法扩版母图的算法 通过上面两个算法的描述可知,在执行算法时,由于选择扩展边的不同会产生多个 ;在执行算法时,选择不同的路径会产生多个,同时不同的扩展边的方式也会生 成多个。因此,令表示顶点个数为时执行算法 或时所得到的所有 的集合。然后,利用算法和就可以设计不含的图的构造算法,其详细描述如算 法所小 在算法中, 用来存放构造过程中产生的所有结构体的队列,即中的 元素; 用来保存经过边和点扩展后得到的结果。该算法主要由如下部分组成 ()在稈序开始时,队列 中只有一个元素,包含母图及其相关信息。在 下一节的实验中,这个母图为或。从这个母图开始,执行算法并返回含有可用点 和新母图的集合,并将中的元素放入 ()从可用点出发,执行算法并返回集合,其中包含扩展得到的新母图 ()对步骤返回的集合中的每个元素,执行算法并将结果放入 ()如果 非空,就循坏执行步骤和,经过边和点扩展后得到的结果保存 在 中 ()对 中的每个图进行后处理。如果包含的图的顶点小于,则 在保证中不出现的前提下,利用穷举的方式添加边和点,直到 。由于这时剩 国武技论文在线 余的顶点数不多,所以采用穷举的方式不会花费很多时问。 ()最后,从构建的图集合中挑出边数最多的图放入集合 中返回。 输入:顶点个数和母图 输出:顶点个数为,不含且边数最多的图的集合 初始化一个结构体用来保存母图及其相关信息,同时初始化 个数组 调用子算法 将返回结果中的元素放入队列 非空 从 中取出一个结构体 中为 将 放入 中的图不能再扩展 中有可用点且能够满足扩展要求 取 的和 调用子算法 ,得到结果 中的每个 中能够满足扩展要求 中包含的新母图用表小 调用 ,结果加入 将结果放入 中的每个图 在不构成的前提卜给图添一个点和一些边 得到的图的边数大于 算法不含的图构造算法 山国武技论文在线 实验结果 本节将利用算法构造出顶点数为29≤≤50的不含的图,以验证算法的有效 性。作为对比,首先给出利用引理得到的结果,也就是以母图构造出星形图;然后再 分别以和为母图调用算法构造出相应的图。 本节实验的试验环境为:硬件环境:核 内存, 磁盘。软件环境 基于母图的图的构造 应用引理,可以计算出当29≤≤时不含的星形图的边数,如表所示。 表当29≤≤时构造的星形图的边数 29<<50 为例,构造不含的星形图的过程如下:取点作为中心点,其余的个点 每个一组可分成组,分别与中心点一起构成个,最后将剩下的个点与中心点 起构成一个。因此,构造出的图的边数为,如图所示。 图当时构造出的星形图 基于母图的图的构造 一节是基于星图进行图的构造,下血给出利用母图进行图的构造的结果。母 图为七边形,利用第节提出的算法对≤≤50不含的图进行构造。算法 的执行结果如表所示,其中 表当≤≤时基于构造的图的边数 29<<50 国武技论文在线 为例,基于构造不含的图的种构造过程如卜:根据对称性原则和引理 ,首先将由 构成的母图中的边 和分别扩展成一个,将 扩展成一个—,可得到可用点、、、、;然后假设此构造过程是从可用点开始 根据引理可找到路径(即),因此在和之间添加两个点和,连接 和;然后将和分别扩展成,并得到可用点和;最后继续从可用点和找路 径或,从找到路径(即),再根据对称性原则从找到路径(即 上述过程得到的图如图所示。其中,边 和已被扩展成个,两个和 被扩展为个 所以构造出的图的边数为 图 时基于构造出的图 基于母图的图的构造 本节给出利用母图进行图的构造得到的结果。母图为八边形,利用第节提 山的算法对29≤≤50不含的图进行构造。算法的执行结果如表所示,其中 。与表对比可以看出,表中用粗体标注部分的结果要优于基于母图 的构造结果 表当≤≤时基于构造的图的边数 29≤≤50 以 为例,基于构造不含的图的一种构造过程如下:根据对称性原则和引理 ,首先将由 构成的母图中的边和扩展成个,将 和打 展成个-,得到可用点、 和;然后假设从可用点开始继续构造,根据引理 叫找到路径,因此在和之间添加两个点和,连接、和;然后将 和 扩展成个,待到可用点、和:最后继续从、和找或,分别从找到 从找到 ,从找到 上述过程得到的图如图所示。其中, 和 被扩展成个 和被扩展为个,所以构造出的图的边数为。 国武技论文在线 时基于构造出的图 对比衣、和可以看出,利用构造算法以圈图和作为母图进行不含 的图的构造,所得到的图的边数都大于基于星图构造出的图的边数。更进步,基于母 图的构造结果大部分顶点数都要优于母图(见表中加粗字体部分)。分析其中原 因,可能因为是八边形,其对称性更好一些,在构造这些图时更具有优势。 在算法的时间复杂度方面,利用母图和构造顶点数为≤≤不含的图时 所耗费的时间如表所示。从表中可以看出,本文提出的算法的所耗费的时间要远低 于基于临界图的图构造算法。 表当29≤≤50时算法的构造时间(小时) 29<<50() 基丁的构造方法 基丁的构造方法 结论 不含偶圈的极图是图论研究中的一个悬而未决的问题,本文主要研究不含的图的构 造方法。首先给出了三种母图 和的结构,然后基于这些母图设计了不含的图 的构造算法。最后,利用该算法构造了当顶点数为 时不含的图集合。通过对 比表的结果,可以给出≤≤时极图边数 的下界。 定理当 时极图边数 的下界如表所示。 表当29≤<50时 的下界 29≤≤50

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐