论de Bruijn-Good图

<正> 前言 de Bruijn-Good图(文中简记为D-G图)是非线性移位寄存器的k(≥2)元n级序列的所有可能状态转移的一种图象表示.它在寄存器设计及编码理论中有着广泛的应用.因而对它的研究具有较高的理论与实际价值. 万哲先、刘木兰在[4]中研究了k=22的D-G图的自同构和2—1同态.最近,刘木     

De Bruijn-Good图的自同构和同态

<正> 所谓n级de Bruijn-Good图G_n是一个有向图:它有2~n个顶点,分别用2~N个二值n元素组 (a_1,a_2,…,a_n),a_i=0或1,来标记;它有2~(n+1)条弧,即对于任意两个以下形状的顶点     

求GF(q)上全部M序列的剪接方法

GF(2)上移位寄存器序列的概念可以很自然地推广到GF(q)上. GF(q)上n级de Bruijn-Good图是一个有向图G_n,它有q~n个顶点,每个顶点表示一个n级状态(a_1,a_2…,a_n),其中a_i=0,1,…,q-1;有q~(n+1)条弧,对于顶点P=(a_1,…a_n)及Q=(b_1,…,b_n)有一条以P为起点Q为终点的有向弧,如果b_1=     

关于某一类非奇反馈函数的自同构函数

本定义了k元de Bruijn-Good图G，的拟i对偶同构及拟对偶自同构，并利用同构的性质，给出了一类k元非奇反馈函数的自同构函数的表达式。     

体上长方矩阵的图同态I

设D~(m×n)为体D上m×n矩阵的集合.两个矩阵A,B∈D~(m×n)称为邻接的,如果rank(A-B)=1.按此邻接关系,以D~(m×n)为顶点集,本文得到一个连通图.设D和D′为两个体,|D|4,m,n,m′,n′2为整数.应用几何方法,本文刻画了从D~(m×n)到D′~(m′×n′)的非退化的图同态φ,其中φ满足条件:φ(0)=0且φ保持D~(m×n)中两个不同类型的标准极大邻接集的维数不变.作为一个推论,当D为EAS(every endomorphism to be automatically surjective)体时,本文给出了从D~(m×n)到D~(m′×n′)的非退化的图同态的代数公式.     

产生2元de Bruijn序列的一个新算法

de Bruijn序列是一类最长的非线性伪随机序列。本文给出了2元de Bruijn序列的一种新的生成算法,该算法能产生2~(δ·N(n,s))个n级de Bruijn序列,其中,0≤s≤2 (n-7)/2;当2~(l-1)相似文献   

从特殊线性群到一般射影线性群的同态的一个性质

设F,K为域,GLn（F）,SLn（F）分别表示F上的n级一般线生群和n级特殊线性群．PGLn（F）,PSLn（F）分别表示F上的n级射影一般线性群和n级射影特殊线性群．φ：SLn（F）→PGLn（K）,n≥3为非平凡同态．本文确定了当K的持征为2时η的—个性质．     

广义(m,n)超环

本文研究了广义(m,n)超环,n元正则关系以及n元强正则关系等的一些性质.利用广义(m,n)超环间的同态关系以及正则和强正则关系,得到了(m,n)子超环和(m,n)超理想的不变性,广义(m,n)超环的商结构,以及构成商超环和商环的充分必要条件,推广了文献[5]的一些结果.     

基于格半群的有限状态自动机的同态

本文研究了格值有限状态自动机(LFSA)的同态和强同态及其性质.利用强同态概念,在格值有限状态自动机的状态集上建立了一种等价关系,得到了格值有限状态自动机的商自动机,证明了商自动机与强同态像自动机同构.     

关于Euler e-函数和n的指数互素因子

对于任意正整数n,设n=pα11pα22…pαrr为n的标准素因数分解式,如果对于de n且de=pβ11pβ22…pβrr有(βi,αi)=1(i=1,2,…,k),则称de为n的指数互素因子.本文利用初等及解析方法研究了正整数n的所有de因子的求和及求积的计算问题,获得了两个有趣的计算公式;同时还研究了n的所有de因子个数函数,即Eu ler e函-数φe(n)的均值性质,并给出了一个较强的渐近公式.     

本原指数达到次大值的竞赛图的刻画

设n≥5,D为n阶强连通竞赛图,本文给出了本原指数达到次大值n 1的极图的完全刻画.     

DIGRAPH CATEGORIES AND LINE DIGRAPH FUNCTORS

The authors define line digraph functors on digraph category which are full and faith-ful and,as a consequence of the result,determine all homomorphisms in De Bruijn-Goodgraph category and automorphisms of Kautz digraph category.Moreover the authorsconsider a type of arc-full morphisms of digraph category such that F~n(f) is arc-full foreach functor F~n,and succeeding paper [9] study the strong homomorphisms of de Bruijn-Good digraph.     

p~2阶非正规Cayley图的核

图的核的研究是当前图论特别是代数图论中的一个前沿课题.一个图的核定义为与该图同态等价的最小阶的图.本文通过讨论p~2阶(p是素数)非正规Cayley图是否存在与其同态等价的诱导子图,研究该Cayley图与其诱导子图的色数、团数和独立数之间的关系,进而确定两个图之间是否存在同态等价.在此基础上确定出p~2阶非正规Cayley图的核.     

关于联图P_1VP_n的k-强优美性

本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果.     

n维有向de Bruijn图和无向de Bruijn图上的随机游动

本文对有向和无向de Bruijn图上的随机游动进行了研究，得出了有向de Bruijn图上简单随机游动任意两点之间平均击中时间的显式表达式，并证明了有向和无向de Bruijn图上随机游动的快速收敛性。     

竞赛图的始终点集偶

本文引进竞赛图的始终点集偶的概念,证明了,每个n-竞赛图(n≥4)都具有始终点集偶,然后,应用这个结果证明了,每个强n-竞赛图(n≥4)都可扩张为2强(n 1)-竞赛图,最后,得到对于任意给定的得分向量是否存在以它为得分向量的2强竞赛图的一个判别准则。     

几类强协调图与非强协调图

证明了风车图K4n3(n∈自然数)及其它几类强协调图,并给出了统一的强协调值标号,最后证明了Kn-e(n≥6)是非强协调图.     

3强竞赛图的得分向量

如果对n阶竞赛图T_n的每个h—1元顶点子集U,删点子图T_n—U都是强的,则称T_n是h强的。如果非降的非负整向量R_n=(r_1,r_2,…,r_n)是某个n阶h强竞赛图的得分向量,则称R_n是隐含h强的;如果所有以R_n为得分向量的n阶竞赛图都是h强的,则称R_n是完全h强的。本文给出了得分向量R_n隐含3强和完全3强的判准。     

扩展de Bruijn图的生成树和广播

扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为[log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.     

格值模糊有限自动机的同态

引入了格值模糊有限自动机的(强)同态的概念,研究了它们的相关性质,得出了同态基本定理。给出了A上容许关系及强同态的核的概念,研究了它们相关性质。