无向简单图顶点度数的一个性质

证明了在无向简单图中删除顶点后连通分支数与被删除顶点度数之间的一个不等式关系。

基于顶点度数的图数据分区域重排序

图计算在机器学习、数据挖掘、网络安全等领域都有着重要应用。而图数据结构不规则且规模巨大,导致访存成为图应用运行时的瓶颈。由于图数据的顶点度数服从幂律分布,许多研究通过重排序图数据使高度数顶点连续储存在相邻位置,从而提升图数据被访问时的时间与空间局部性。然而重排序会破坏原始图数据中存在的群落结构,导致目前基于顶点度数信息的重排序算法在高结构性图数据集上无法产生性能提升。本文针对上述问题提出了一种新的保护图数据结构性的重排序算法,通过对自然图数据集中存在的群落结构进行研究,结合处理器访存结构特性,将图数据集合理划分成不同区域后进行重排序,保护其群落存储顺序以提高重排序后访存时的局部性。本文在通用处理器平台上,对6个不同结构性图数据集和3种图计算应用共18个测试点进行了验证,实验结果表明,该重排序方法相对于原始图数据集实现了平均18.86%的性能提升,相对于目前最优的基于顶点度数信息的轻量级重排序算法实现了平均11.3%的性能提升。

度数法求解最大团问题

由于最大团问题(maximum clique problem,MCP)的复杂性、挑战性,以及在数据挖掘等领域的广泛应用,使得求解MCP问题具有非常重要的意义。根据最大团顶点度数较大的特点,提出了从图中第一个度数最大的顶点出发递归求解最大团的算法(简称度数法)。为了进一步提高算法的效率,根据图的特点和最大团的特点提出了三个改进的剪枝策略。从理论上证明了算法的正确性和完整性,其时间复杂度为O(1.442n),空间为O(n2)。通过实验验证了度数法及其改进剪枝策略的效果和效率。

单群L_3(9)的OD-刻画(英文)

利用有限群的群阶和度数型对射影特殊线性单群L3(9)进行了刻画,得到了如下定理:设G是一有限群,若D(G)=D(L3(9))且|G|=|L3(9)|,则G L3(9).

L_7(3)与GL_7(3)的OD-刻画

对于任意一个有限群G,令π(G)表示由它的阶的所有素因子构成的集合.构建一种与之相关的简单图,称之为素图,记作Γ(G).该图的顶点集合是π(G),图中两顶点p,g相连(记作p～q)的充要条件是群G恰有pq阶元.设π(G)={P_1,p2,…,p_x}.对于任意给定的p∈π(G),令deg(p):=|{q∈π(G)|在素图Γ(G)中,p～q}|,并称之为顶点p的度数.同时,定义D(G):=(deg(p_1),deg(p_2),…,deg(p_s)),其中p_1<p_2<…<p-s,并称之为群G的素图度数序列.若存在k个互不同构的群与群G具有相同的群阶和素图度数序列,则称群G是可k-重OD-刻画的.特别地,可1-重OD-刻画的群也称为可OD-刻画的群.引入了一个新的引理并证明了特殊射影线性群L7(3)是可OD-刻画的;一般线性群GL7(3)是可3-重OD-刻画的.作为一个推论,得到L7(3)是可OG-刻画的.

基于隐马尔可夫随机场的社区结构发现算法

针对社区结构发现问题,提出了一种基于隐马尔可夫随机场社区发现算法。该方法将网络中的顶点度数映射为顶点信息值,用马尔可夫随机场模型描述网络中上下文信息并构造系统能量函数,使用迭代条件模式算法对能量方程进行优化。该方法在Zachary空手道俱乐部网络、海豚关系网络以及美国大学足球联赛网络上进行验证,实验结果表明,该算法的准确率较高。

与Chevalley群F_4(2)有关的几乎单群的OD-刻画(英文)

利用有限群的群阶和度数型,对与Chevalley群F4(2)有关的几乎单群进行了刻画.得到了:Aut(F4(2))为OD-刻画;2.F4(2)为2-重OD-刻画.

L15(2)的新刻画

对于任意一个有限群G,令π(G)表示由它的阶的所有素因子所构成的集合.该文构建一种与之相关的简单图,称之为素图,记作Γ(G).该图的顶点集合是π(G),图中两顶点p,q相连(记作p^q)的充要条件是群G恰有pq阶元^([7,15]).令π(G)={p_1,p_2,…,p_s}.对于任意p∈π(G),令deg(p):=|{q∈π(G)|在素图Γ(G)中,p^q}|,并称之为顶点p的度数.同时,我们定义D(G):=(deg(p_1),deg(p_2),…,deg(p_s)),其中p_1<p_2<…<p_s,并称之为群G的素图度数序列.若存在k个互不同构的群与群G具有相同的群阶和素图度数序列,则称群G是可k-重OD-刻画的.特别地,可1-重OD-刻画的群也称为可OD-刻画的群^([11]).在该文中,引入一个新的引理并证明了特殊射影线性群L_(15)(2)是可OD-刻画的.作为一个推论,得到L_(15)(2)是可OG-刻画的.该方法也可适用于其它一些具体的有限单群.

满足某些条件的有限单群的分类

进一步探讨了有限非交换单群的素图,考虑了顶点度数对其结构的影响,利用数论知识,素图完全图的分类,以及有限非交换单群的素图连接标准,得到了群阶不超过1010的素图每个分支为完全图且7∈π(G),dG(7)=1的有限非交换单群的分类.该分类问题进一步完善了有限单群的素图信息,借助此方法,还可以解决群阶包含其他素数的有限非交换单群的分类.

关于图G的χ′(G)=(n+4)/2的升分解

证明了下面的结论 :设简单图 G,满足 |E( G) |=C2n+1,若χ′( G) =n+42 ,则 G可以升分解为 G1,G2 …Gn- 1,Gn- 2 ,Gn,其中 Gi≌ i K2 ,i≤

图集上的一种新运算及若干性质

文章建立了图集上一种新运算并给出此运算的若干性质，尤其有两条值得注意的结论：Euler图经过该运算后依然是Euler图，Euler图经该运算后成为复杂的Hamilton图。

特殊射影线性群L_5(q)的OD-刻画

若存在k个互不同构的群与群G具有相同的群阶和素图度数序列,则称群G是可k重OD-刻画的.特别地,若k=1,则称群G是OD-刻画群.利用群阶和素图度数序列证明了特殊射影线性群L5(q)是OD-刻画群,其中q(2≤q<15)是素数的方幂.

某些具有完全素图的有限单群的分类

有限单群G称为完全素图群,当且仅当所有连通分支的素图都是完全图,即是说若r,s∈πi(i=1,2,…),则r^s.利用有限单群素图的连接准则对所有满足5∈π(G)且dG(5)=1的完全素图群G进行了分类.

有限单群L_6(5)的OD-刻画(英文)

用一个新的引理来处理素图连通的有限群,并由此证明了射影特殊线性群L6(5)是可OD-刻画的.

维数分别为45和46的对称群的新刻画

利用有限群的阶和它的度数型分别对对称群S45和S46进行了刻画,得到了:对称群S45和S46均可3-重OD-刻画.

某些素图连通的对称群的OD-刻画

利用有限群的阶及其度数型的性质对素图连通的对称群S9和S28进行了刻画,得到如下结论:设G为有限群,如果|G|=|H|且D(G)=D(H),则G是3-重OD-刻画的,其中H=S9或者H=S28.

某些素图连通的对称群的新刻画

文献(A.R.Moghaddamfar,A.R.Zokayi,M.R.Darafsheh.Algebra Colloquium,2005,12(3):431-442.)介绍了与群G的素图有关的度数型D(G).群G称为k-重OD-刻画,如果恰好存在k个不同构的群H使得|G|=|H|且D(G)=D(H).而且1-重OD-刻画群简称为OD-刻画.利用有限群的阶和它的度数型对对称群S39和S40进行了刻画,得到:设G为有限群,如果|G|=|H|且D(G)=D(H),其中H=S39或者S40,则G是3-重OD-刻画.

交错群A_(16)的OD-刻画(英文)

利用有限群的群阶和它的度数型对具有连通素图的交错群A16进行了刻画,得到了如下定理:设G是一有限群,若D(G)=D(A)且|G|=|A|,则G A.

顶点覆盖问题的贪心算法的设计与分析

设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 .