关于非完全覆盖图的重构

来源 :南开大学 | 被引量 : 0次 | 上传用户:a395744775
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文对非完全覆盖图的重构进行了研究。主要内容如下:   ⑴令Γ=(V(Γ),E(Γ))表示一个以V(Γ)为点集,E(Γ)为边集的有限非空无向图。对于任意一个非负整数s及V(Γ)上的一个s+1-序列α=(α0,…,α8),α称为Γ上的一条s-弧,如果{αi,αi+1)∈E(Γ),对于i=0,1,…,s-1,并且αi-1≠αi+1,对于i=1,2,…,s-1.记Arc8(Γ)为Γ上所有s-弧的集合。通常,我们将1-arc和Arc1(Γ)简记为arc和Arc(Γ)。令X表示作用在V(Γ)上的一个有限群,使得对于任意的x∈X,E(Γ)x=E(Γ)(即X保持Γ的邻接关系).Γ称为X-点传递的,如果X在V(Γ)上的作用是传递的(即对于任意的αi,αj,∈V(Γ),存在x∈X满足αix=αj)。一个点传递图Γ称为是(X,s)-弧-传递的,如果X在Arcs(Γ)上诱导的作用是传递的.(X,1)-弧-传递图又称为X-对称图.   ⑵称Γ是X-非本原图,如果V(Γ)允许一个非平凡的X-不变的划分召,也就是一个划分B,使得对于任意的B∈B及x∈X,有1<|B|<|V(Γ)|且Bx∈B.此时我们可以定义Γ关于划分B的商图ΓB为以B为点集的一个图,其邻接关系为:对于任意的B,C∈B,{B,C)∈E(ΓB)当且仅当存Γ中的两个点σ∈B和τ∈C使得{σ,τ}∈E(Γ).我们考虑ΓB不是空图的情形,此时由[1]我们有对于任意的B∈B,B是Γ的一个独立集。称Γ是ΓB的多重覆盖图,如果对于任意的{B,C}∈E(ΓB)和σ∈B,存在τ∈C使得{σ,τ]∈E(Γ),否则称Γ不是ΓB的多重覆盖图.特别地,如果上述τ是唯一存在的,就称Γ是ΓB的覆盖。当Γ是一个有限非空的(X,2)-弧-传递图,B为其上一个非平凡的X-不变的划分,使得ΓB非空且Γ不是ΓB的多重覆盖图时,文献[2]给出了(Γ,X,B)当|Γ(C)∩B|=2时的一个刻画,这里B∈B且C∈ΓB(B).这个结果促使我们研究当|Γ(C)∩B|=3的情形.完成这个工作需要研究度数为4或7的(X,2)-弧-传递图.基于[3]中的结果,我们将在第一章给出4度(X,2)-弧-传递图的一个划分;同时我们将证明任何一个4度的(X,2)-弧-传递的非完全图都是准n边形,这里n≥4是一个整数.对于7度的(X,2)-弧-传递图∑,我们将证明∑可以作为一个满足条件的Γ的商图,当且仅当Xr∑(τ)≌PSL(3,2),这里τ∈V(∑)。   ⑶对于任意一个X-对称图∑,我们将给出存在一个(X,s)-弧-传递图Γ以∑为商图,且Γ不是∑的完全覆盖图的充要条件。同时,当这一条件满足时,我们将给出一个方法来构造这样一个Γ;进一步地,对于任何一个(X,s)-弧-传递图Γ,这里s≥1,我们可以从∑出发,经过m(1m是一个自然数)次这样的构造过程,我们将得到一个图ΓBm,使得Γ≌ΓBm或者Γ是ΓBm的一个完全覆盖。
其他文献
本文讨论了几类时滞微分方程动力系统的退化分支.通过推广运用时滞微分方程的中心流行理论和标准性理论,分析了相应捕食被捕食系统、神经网络模型的动力学行为,推导出该系统的
随机规划和互补是数学规划的重要研究课题,在工程设计、最优控制、信息技术、经济均衡等领域有着广泛的应用.期望剩余再生(ERM)方法是求解随机互补问题(SCP)的有效途径之一. 本文
1987年J.G.Thompson在给施武杰的一封信中提出了下面的一个与代数数域有关的问题(见[24]的问题12.37).特别在Thompson的信中[48]写到:“我已经把关于同阶型的问题告诉了很多数学
对称性是自然界中普遍存在的现象,具有对称性的系统当中蕴含着某些重要的守恒性质。利用这些守恒性质可以对系统进行约化。对于一般的Hamilton系统,人们通常考虑的是Marsden等
文物古迹是人类发展史的真实写照和无价之宝.然而,由于社会的发展,所形成的环境污染,使得文物古迹遭受了严重的损害.这种损害是长期作用的结果,所以一时不易被人们察觉,一旦
Novikov超代数与二阶保形超代数相关,后者对应于汉密尔顿对,在完全可积组中起着关键作用。本文给出了4维非平凡的Novikov超代数的分类。                  
小覆盖的研究是环面拓扑领域中一个非常重要的工作.小覆盖给了等变拓扑学和组合学之间一个紧密的联系,使得我们可以用组合学的相关知识来研究拓扑学中的问题.单凸多胞形上小覆
大学生见习是教学实践的重要一环,文章以广东石油化工学院文秘见习生为例,探究了办公自动化理论在见习中的应用问题,并以此找出解决方案,对高校人才培养和大学生就业将会奠定
本文主要讨论一类非凸D.C.约束优化问题的UV-分解理论。全文共分四章。第一章是引言,主要介绍了关于UV-分解理论的历史概述与研究背景,及对本文的研究工作。第二章是预备知识,首
两水平的正规部分因析设计是众所周知的并被广泛应用于各个领域的试验中.这些设计的一个突出特点是它们有简单的别名结构,任意两个效应要么正交,要么完全别名.   效应排序原