非色唯一的连通顶点可迁图的广泛存在性

本文中,我们构造性地证明了:对应于每一个给定的色唯一的连通顶点可迁图,均存在着无穷多个与之对应的非色唯一的连通顶点可迁图.据此,我们部分地回答了G.L.Chia在[4]中提出的第二个问题.     

过特定顶点集S的S—D—圈与S—D—路

利用领域域交给出了图Ｇ的每个Ｓ－厚大圈都是Ｓ－Ｄ－圈的一个充分条件，并给出了对任意｛ｕ，ｖ｝包含Ｖ（Ｇ），Ｇ的每条（ｕ，ｖ）－Ｓ－最大路都是Ｓ－Ｄ－路的一个充分条件。     

图之极小顶点覆盖

图的一个顶点覆盖被称为极小的假如其任何真子集不再是该图的一顶点覆盖，本文证明了某些图之所有极小顶点覆盖的个数的明确表达式，其中包括路径，梯形图，及线性ｎ部图。     

CmP1Cn的优美性

设Cp表一个长为p的圈，CmP1Cn表示由一条1个点的路P1联结两个圈Cm和Cn得到的图，其中P1的内部顶点不在V（Cm）∪V（Cn）中，且当1＝1时，|V（Cm）∩V（Cn）|＝1；当1＞1时，|V（Cm）∩V（Cn）|＝0。本的目的是证明：CmP1Cn（l＝1，2，3）当4|m,4|n时，是k－优美图。     

一些可靠通讯网络的构造

本文首先得到了循环图的原子部分仍为连通循环图的结果,同时还得到了连通循环图的连通度的一些性质。然后应用这些结果与循环图的理论,得到了5,7,8,9度连通循环图的连通度等于其度数的充要条件,从而可构造出5,7,8,9度可靠通讯网络。     

具有三个单模的有限维遗传代数的Hochschild上同调群

计算代数的Hochschild上同调群是非常重要且复杂的,高维代数Hochschild上同调群维数的计算能否通过计算较低维代数的Hochschild上同调群的维数来实现是一个有趣的问题.本文利用有向图的顶点矩阵,通过计算二维代数的Hochschild上同调群的维数来计算具有三个单模的有限维遗传代数的Hochschild上同调群的维数.     

树按Wiener指标的排序

n个顶点的树的集合记为Fn,连通图G的Wiener指标等于图G中任意两点的距离和．本考虑．Fn中树的按Wiener指标排序的问题．先对Fn中树按非悬挂边的数目分类．确定出具有1条非悬挂边．2条非悬挂边．和3条非悬挂边的树包括的图类．根据Wiener指标的计算公式及中提到的变换方式．得到这些图类的序关系．基于这些序关系．确定了Fn中具有最小Wiener指标的前15个树．     

SOME RESULTS ON CIRCULAR PERFECT GRAPHS AND PERFECT GRAPHS

An r-circular coloring of a graph G is a map f from V(G) to the set of open unit intervals of an Euclidean circle of length r, such that f(u) ∩ f(v) = Ф whenever uv ∈ E(G). Circular perfect graphs are defined analogously to perfect graphs by means of two parameters, the circular chromatic number and the circular clique number. In this paper, we study the properties of circular perfect graphs. We give (1) a necessary condition for a graph to be circular perfect, (2) some circular critical imperfect graphs, and (3) a characterization of graphs with the property that each of their induced subgraphs has circular clique number the same as its clique number, and then the two conjectures that are equivalent to the perfect graph conjecture.     

点可迁图的顶点划分

设G是k正则连通点可迁图。图G的一个边割S称为限制性边割，如果G－S不含孤立点，最小限制性边割所含的边数λ′称为限制性边连通度。已经证明λ′≤2k-2，等号成立时，称图G是极大限制性边连通的。本文证明了：如果G不是极大限制性边连通的，那么G的顶点集存在一个划分π＝（C1，…，Cm)，使得由Ch导出的子图同构于一个连通k-1正则点可迁图H,h=1,2，…，m，而且k≤|H|≤2k-3。     

部分可重构系统布局的一种新算法

针对动态部分可重构系统的瓶颈,即布局算法必须在保证运行速度的基础上,尽可能增加可重构芯片利用率的问题,提出了一种布局算法KVIT(keeping the vertexes information of tasks).其核心思想是尝试将新到达的硬件任务放置在已布局硬件任务的顶点处,并通过对可重构芯片内部计算单元进行编码迅速判断新任务是否可放置在该顶点.该算法的时间复杂度为O(N),N是可重构系统中当前运行的硬件任务的数目.仿真实验结果表明,KVIT算法的布局质量与现有的O(N2)时间复杂度布局算法基本一致,而其执行速度则明显高于已有算法.