图的最小顶点覆盖问题的面上DNA解法

1994年 ,Adlem an提出一种解决 NP完全问题的新方法— DNA计算 .之后又出现了许多关于 DNA计算的改进操作并增加了其可靠性 ,其中面上操作是一种很有效的方法 .本文利用 DNA计算的固态处理 (面上计算 )解决了图论中又一 NP完全问题—图的最小顶点覆盖问题 .构造了含有 6个顶点 10条边的图的顶点集子集对应的数据池之后 ,进行了一系列的合成、杂交、清洗、变性等生物操作 ,得到所有覆盖对应的 DNA序列 ,然后通过编址过程得到所要求的最小覆盖 .

3-连通无爪图的度和与泛圈性

若图G中不含同构于K1,3的导出子图，则称G为无爪图．笔者讨论了3-连通爪图中三个顶点的度和与泛圈性之间的关系，给出了图是泛圈的一个充分条件，得到了如下结果：设图G是n阶3-连通无爪图，如果σ3（G）≥n＋1，则G是泛圈的．

图的度和与圈可扩性

讨论了两个点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶n≥3,如果G中任意一对不同的顶点u,v满足d(u)+d(v)≥n+1,则G是完全圈可扩的。

图的度和与扩圈

本文讨论了两顶点的度和与圈可扩之间的关系,得到了如下结果:设图G的阶 ,如果G中任意一对不相邻的顶点u,v满足 ,则G中任意一个满足 的圈C是可扩的。这里圈C的下界是最好可能的。由此进一步得到,如果G中任意一对不相邻的顶点u,v满足 ,则G是完全圈可扩的。

改进的最小顶点覆盖问题的贪婪算法

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程.该算法在最坏情况下的时间复杂度为O(|V|2).

图的最小度与路可扩性

讨论了图的最小度与路可扩之间的关系,得到当δ(G)≥2/G+1,则图G是路可扩的。这里δ(G)的下界是最好可能的。

路和与路可扩

讨论了两个点的度和与路可扩之间的关系,得到了如下结果:设图G的阶n≥3,如果G中任意一对不同的顶点u,v满足d(u)+d(v)≥n+2,则G是路可扩的.

求图的约束最小割集的一个有效算法及其应用

本文提出确定把无向连通图G(V,E)切割为两个子图G_1(V_1,E_1)和G_2(V_2,E_2)且满足顶点集V_1和V_2的顶点数|V_1|和|V_2|为给定值的约束最小割集的一种有效算法。该算法理论比较简单,步骤简捷有效,并能保证在多项式时间内获得最优解;此外,本文举例说明该算法具体步骤过程并介绍该算法在计算机辅助电路分析和设计中的某些实际应用。

8阶非同构3正则图的构造

通过逐步扩张图的顶点的度的方法,运用分类讨论的思想,系统研究了8阶3正则图的构造问题,得到了8阶非同构3正则图共有8个结论,构造了全部的8阶3正则图,判断了它们之间是否同构,最后筛选出全部的8阶非同构3正则图,发现它们的数量竟然与其阶数相同。

第33届IMO越南国家队选拔试题

第一天（4小时） 1.给定两个自然数m和n,其中n】1,且nm,试求最小的整数k,使得任意k个满足条件:“对一切1≤i【j≤k,n（ai-aj）”的整数a1,a2,…,ak中,都存在两个整数as和at（s≠t）,使得m+as-at可被n整除。 2.给定一个次数≥1的实系数多项式f（x）,证明,对每个c】0,存在一个正整数n0满足如下条件:对每个次数≥n0

两类特殊图论问题

给定自然数n,r,探求在什么情况下,n阶简单图G中必存在r阶完全图kr,是图论中一个极为有趣的问题。下面介绍这一问题的某些结果。 例1.设n（n】1）阶简单图G中不含k3,则其边数的最大值为[n2/4]。

近几年与概率方法有关的组合竞赛题

文[1]介绍了概率方法在解决组合竞赛问题中的运用,本文将在此基础上,展现出概率方法更进一步的使用.1利用随机变量的线性可加性将一个随机变量分解为若干个示性随机变量。

关于超图自同构群的若干结论

利用超图在新的公理体系下同构的定义,给出超图自同构群的定义,这与特殊的情形——图的自同构群的定义是相容的,并将图的自同构群的一些结论在超图中进行推广。

路可扩图的一个充分条件

通过讨论图中任意一对不相邻顶点的度和,对路可扩图的充分条件进行研究,得到了如下结果:设图G的阶是n,如果G中任意一对不相邻顶点的度和至少为3/2n-1,则图G是路可扩的.并且说明了这里两不相邻顶点的度和的下界3/2n-1是最好可能的.

图PnΥSm的优美标号

图G的标号是指G的顶点集到一个整数集的映射g,且对e=uv∈E(G)由g(u)和g(v)诱导出边e的标号。本文给出了图PnE¨Sm的优美性。即证明了图PnE¨Sm是优美图。进而推广了原有的一些结果。

对Posa定理的讨论

文章通过对Posa定理进行讨论,给出了判断非哈密顿图的一些办法,并且给出了二部图是哈密顿图的一个充分条件.

欧拉路径或欧拉回路的一种算法

本文主要是,给出求欧拉路径或欧拉回路的一种算法,该算法能够找出从某顶点出发的所有欧拉路径或欧拉回路,通过图的邻接矩阵存储方式和C++语言实现。

混合Euler图的特征性质

本文对任意混合图M建立相伴运输网络N_M的概念,并以此给出M是混合Euler图的充要条件。这结果与文献中同类结果相比,具有更大的实用性。

第60届IMO试题解答

1.用Z表示全体整数构成的集合.求所有的函数f:Z→Z,满足对任意的整数a、b,均有f（2a）+2f（b）=f（f（a+b））.2.在△ABC中,点A1、B1分别在边BC、AC上,点P、Q分别在线段AA1、BB1上,且满足PQ//AB.在直线PB1上取点P1,使得点B1严格位于点P与P1之间,并且∠PP1C=∠BAC.类似地,在直线QA1上取点Q1,使得点A1严格位于点Q与Q1之间,并且∠CQ1Q=∠CBA.证明:P、P1、Q1、Q四点共圆.