图的路连通问题

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。     

关于“k——序哈密尔顿图”一文的一点注记

本注记改正文［１］中一个引理的一点错误及引理证明中的失误。重新证明了若ｎ阶图Ｇ的任二不相邻顶点ｕ、ｖ有ｄ（ｕ）＋ｄ（ｖ）≥ｎ＋２ｋ－７，４≤ｋ≤ｎ，则对于Ｇ的任意不同的ｋ个顶点ｖ１，ｖ２，…，ｖｋ，有ｖ１（ｘ１）ｖ２（ｘ２）…ｖｋ－１（ｘｋ－１）ｖｋ型ｖ１—ｖｋ路（我们用ｖｉ（ｘｉ）ｖｉ＋１表示ｖｉｖｉ＋１或ｖｉｘｉｖｉ＋１。）或ｖｋｖ１（ｘ１）…（ｘｋ－２）ｖｋ－１型ｖｋ—ｖｋ－１路；若对任不相邻两顶点ｕ、ｖ有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则对于Ｇ中任三点ｖ１，ｖ２，ｖ３存在ｖ１（ｘ１）ｖ２（ｘ２）ｖ３型ｖ１—ｖ３路。最后对文［１］中的公开问题１提出自己的看法。     

点泛圈偶图

设Ｇ是连通偶图，（Ｘ１，Ｘ２）是其顶点的二分类，｜Ｘ１｜＝｜Ｘ２｜＝ｎ，δ（Ｇ）≥ｔ≥３，且对于Ｘｉ中的任意两点ｕ和ｖ，均有｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｎ－（ｔ－２），ｉ＝１，２，文中对ｔ≤６的情况，证明Ｇ是点泛圈偶图。     

Hamilton偶图的局部度数条件

设Ｇ是具有二分类（Ｘ，Ｙ）的２连通等部偶图。如果对Ｇ中每一个顶点ｖ，Ｈ是Ｇ中与ｖ距离为２和３的所有顶点导出的子图，并且对于ｇ中每一个与ｖ距离为３的顶点ｕ，ｕ在Ｈ中的度数ｄ＿Ｈ（ｕ）不小于距离ｖ为２的顶点的数目减去（ｄＧ（ｖ）－２），则Ｇ是Ｈａｍｉｌｔｏｎ图。其中ｄ＿Ｈ（ｕ）的下界不能改进。     

点剖分与图谱半径的不等式

Ｇ是简单图，ｖ∈Ｖ（Ｇ）．用两个新顶点去代替顶点ｖ，原来Ｇ中与ｖ相邻的顶点现在与ｕ或者ｗ相邻，且ｄ（ｕ）＋ｄ（Ｗ）＝ｄ（ｖ），这时称顶点ｖ被剖分。记ρ（Ｇ）为Ｇ的谱半径，Ｇ’为Ｇ中顶点ｖ被剖分后的新图，则ρ（Ｇ’）≤ρ（Ｇ），等式成立当且仅当ｄ（ｕ）＝０或ｄ（ｗ）＝０．如果Ｇ是连通的且ｖ是Ｇ的割点，对ｖ做适当的剖分，使得新图Ｃ’由两个分枝Ｈ＿１，Ｈ＿２组成，则ρ（Ｇ）≤等号成立当且仅当Ｇ是星图。     

关于无爪图中（u,v）—5路存在性的两个定理

证明了下列结果：（１）设Ｇ是３连通无爪图,│Ｖ（Ｇ）│≥６且Ｇ的每个导出图Ａ都满足φ（ａ１,ａ２）那么对任意ｕ,ｖ∈Ｖ（Ｇ）,若２≤ｄ（ｕ,ｖ）≤５,则对满足ｄ（ｕ,ｖ）≤ｋ≤５的整数ｋ,Ｇ中存在（ｕ,ｖ）－ｋ路（２）设Ｇ是３连通无爪图,│Ｖ（Ｇ）│≥６,且Ｇ的每个导出子图Ａ都满足φ（ａ１,ａ２）而Ｐ＝ｖ１,ｖ２,．．．ｖ５（ｖ１＝ｕ,ｖ５＝ｖ）是Ｇ的（ｕ,ｖ）－４路Ｇ（Ｖ（Ｐ）＝Ｋ│ｖ（ｐ）│则     

矩阵的一个定理和线性方程组解的结构

设Ａ∈Ｍ＿（ｍ×ｎ）（Ｆ），则存在ｍ阶可逆矩阵Ｐ和ｎ阶可逆矩阵Ｑ，使其中ｒ＝Ｒ（Ａ）；本文还讨论了一般线性方程组Ａ＿（ｍｎ）Ｘ＿（ｎ１）＝ｂ＿（ｍ１）的可解性及解的结构与矩阵Ｐ，Ｑ之间的关系。     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

顶点的凝聚度与顶点的棱──凝聚度的关系

本文在［１］和［２］的基础上，研究顶点的凝聚度与顶点的棱─凝聚度的关系． 定理１ 如，ｃ（ｖ）＜０．则ｃ（ｖ）≥ｃ＇（ｖ）． 定理２ 设ｖ是图Ｇ的负点，ｕ是其它任意点，则ｃ（ｕ）＝ｃ＇（ｕ）．     

一类复合图的niche数上界

研究证明：在一定条件下,两个有限ｎｉｃｈｅ图Ｇ１和Ｇ２的两点粘接图的ｎｉｃｈｅ数ｎ（Ｇ１：Ｇ２（ｕ１＝ｖ１,ｕ２＝ｖ２）≤ｎ（Ｇ１）＋ｎ（Ｇ２）－ｒ,其中ｒ＝０,１,２。     

Hamilton连通图的一个充分条件

设Ｇ是ｎ阶３－连通图，若对任意不相邻二点｛ｕ，ｖ｝Ｖ（Ｇ）有ｄ（ｕ）＋ｄ（ｖ）＋２｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥２ｎ＋１，则Ｇ是Ｈａｍｉｔｏｎ连通的。     

单纯Handcuffed三元系的嵌入

本文证明了对任意给定的正整数λ，当且仅当λ（ｖ－１）≡λｖ（ｖ－１）≡λ（ｕ－１）≡λｕ（ｕ－１）≡０（ｍｏｄ ４），ｕ≥２ｖ＋１且λ≤２（ｖ－２）／３时，任一单纯Ｈａｎｄｃｕｆｆｅｄ三元系ＮＨ（ｖ，３，λ）可嵌入于某个单纯Ｈａｎｄｃｕｆｆｅｄ三元系ＮＨ（ｕ，３，λ）。     

包装树和不含K3的（P,P＋1）图

给出同阶（阶数≥７）树和不含Ｋ＿３的（Ｐ，Ｐ＋１）图可包装的充要条件为｛Ｇ＿１，Ｇ＿２｝不是下述图对之一：（１）｛Ｓ＿ｎ，Ｇ＿２｝，其中Ｓｎ是ｎ阶星图，Ｇ＿２是无孤立点的（Ｐ，Ｐ＋１）图；（２）｛Ｓ＇＿ｎ，Ｇ＿２｝，其中Ｓ＇＿ｎ是由Ｓ（ｎ－１）的任一边上增加一个剖分点得到的ｎ阶树，Ｇ＿２是最小度大于１的（Ｐ，Ｐ＋１）图。     

一类强非线性双曲方程组解的存在性和唯一性

本文研究了一类强非线性双曲方程组ｕ＿（ｔｔ）－ｕ＿（ｘｘ）＝ｆ（ｕ，ｖ），ｖ＿（ｔｔ）－ｖ＿（ｘｘ）＝ｇ（ｕ，ｖ）解的存在和唯一性，还证明了解的Ｈｏｌｄｅｒ连续性。     

复合图Ga（u）⊙UV⊙G2（V）的niche数

复合图Ｇ１（ｕ）⊙ｕｖ⊙Ｇ２（ｖ）是将简单图Ｇ１的顶点ｕ与简单图Ｇ２的顶点ｖ用边ｕｖ连接成的图。本文证明，若Ｇ１和Ｇ２都是有限ｎｉｃｈｅ图，则当连接点ｕ，ｖ满足一定的条件时，复合图Ｇ１（ｕ）⊙ｕｖ⊙Ｇ２（ｖ）也是有限ｎｉｃｈｅ图，且ｎ（Ｇ１（ｕ）⊙ｕｖ⊙Ｇ２（ｖ）０≤ｎ９Ｇ１）＋ｎ（Ｇ２）－ｒ其中，ｒ＝０，１，２。     

最长路原理与图中的路和图

设Ｐ＝ｖ０ｖ１…ｖｋ（其中ｖｋ＝ｙ为图Ｇ中一条最长ｙ－路，即以ｙ为络点的路中最长者，那私Ｎ（ｖ０）包函于Ｖ（Ｐ），且对ｖｊ∷Ｎ（ｖ０），ｖｊ－１ｖｊ－２…ｖ０ｖｖｊ＋１…ｖｋ也是最长ｙ－路，利用该简单原理证明：对于２－连通非Ｈａｍｉｌｔｏｎ图Ｇ的任一顶点ｙ，存在某最长ｙ－路Ｐ（ｘ，ｙ）使ｄ（ｘ）较大。据此直接推出关于周长的范更华定理等重要结果。     

一个确定凸多边形可碰撞区域的新算法

设Ｐ＝（Ｐ＿０，Ｐ＿１，…，Ｐ＿（ｍ－１））与Ｑ（ｑ＿０，ｑ＿１，…，ｑ＿（ｎ－１））为平面内互不相交的两个凸多边形，本文研究如何快速确定它们的可碰撞区域和可移动区域的问题。本文研究了凸多边形支撑线的性质，把支撑线进行分类，据此得出一种求斜支撑线的新算法，其时间复杂度为Ｏ（ｌｏｇｍ·ｌｏｇｎ）．在此基础上构造出确定凸多边形可碰撞区域的时间复杂度为Ｏ（ｌｏｇｍ·ｌｏｇｎ）的快速算法。     

复合图G1(u)⊙uv⊙G2(v)的niche数

复合图Ｇ１（ｕ）⊙ｕｖ⊙Ｇ２（ｖ）是将简单图Ｇ１的顶点ｕ与简单图Ｇ２的顶点ｖ用边ｕｖ连接成的图．本文证明：若Ｇ１和Ｇ２都是有限ｎｉｃｈｅ图，则当连接点ｕ，ｖ满足一定的条件时，复合图Ｇ１（ｕ）⊙ｕｖ⊙Ｇ２（ｖ）也是有限ｎｉｃｈｅ图，且ｎ（Ｇ１（ｕ）⊙ｕｖ⊙Ｇ２（ｖ））≤ｎ（Ｇ１）＋ｎ（Ｇ２）－ｒ其中，ｒ＝０，１，２．     

单纯二重有向三元系的相交数

解决了单纯二重有向三元系的相交数问题，即证明了对于任一正整数ｕ≥３，ｖ≡０，１（ｍｏｄ ３），存在两个单纯二重有向三元系相交于ｓ个公共区组的充要条件是：当ｖ≥４时，ｓ∈（０，１，２，．．．，２ｖ（ｖ－１）／３），ｓ≠（２ｖ（ｖ－１）／３）－１当ｖ＝３时，ｓ∈（０，２，４）。     

一类约束极小问题的几个结果

研究了与等周不等式有关的约束极小问题：Ｉｔ＝ｉｎｆＱ（ｕ＋ｔψ）＝１,ｕ∈Ｈ１０（Ω,Ｒ３）∫Ω｜ｕ｜２ｄｘｄｙ,其中,Ω为Ｒ２中的有界区域,Ｑ（ｖ）＝∫Ωｖ（ｖｘ∧ｖｙ）ｄｘｄｙ．证明了如下结论：１）对于ψ∈Ｈ１０（Ω,Ｒ３）,若ψｘ∧ψｙ０,且ψ∈Ｃ１,１０（Ω,Ｒ３）,则Ｉｔ→Ｓ（当ｔ→０时）;２）设ｕｔ是Ｉｔ的极小可达函数,则存在某一ｘ０∈Ω,使得｜ｕｔ｜２Ｓδｘ０（当ｔ→０时）（在测度意义下）,这里Ｓ＝ｉｎｆ∫Ｒ２｜ｕ｜２ｄｘｄｙｕ∈Ｈ１０（Ｒ２,Ｒ３）,Ｑ（ｕ）＝１｛｝