面向顶点染色算法的专用指令集优化处理器

为了提高图形处理器中顶点染色器的工作效率,设计一款改进的可编程顶点染色器。设计引入适用于顶点染色器的一种专用指令集,以完成顶点染色的加减乘除等基本操作,并加入染色算法中常见的向量操作和特殊函数计算的指令,另在浮点4路单指令多数据的结构基础上加入带有旁路功能的五级宏流水线和超越函数运算单元。在工作站使用Linux环境下的QuestaSim6.5b进行功能仿真,使用Xilinx公司Virtex6-760芯片为目标器件对可编程顶点染色器进行逻辑综合。实验结果表明,该顶点染色器可以绘制出真实图形,其最大工作频率可达197MHz,顶点的处理能力可达5Mvertex/s。

图形处理器中双核顶点染色器的设计与实现

为了提高图形处理器(graphic processing unit,GPU)中顶点染色器的工作效率,设计了一款改进的可编程双核顶点染色器.它可以同时对来自命令处理器的两条命令进行解析,然后交由PE双核进行处理,这样既可以提高处理器的资源利用率又可以加强处理器的并行执行能力.采用基于FPGA的验证方式,整个双核顶点染色器占用Xilinx V6系列550T型号FPGA芯片硬件资源的7%,最大工作频率能够达到155.411 MHz.

De Bruijn图的均匀顶点染色和有向图线图的一个顶点染色定理

给出了ｎ维ｄ进位ＤｅＢｒｕｉｊｎ图Ｂ（ｄ，ｎ）的一种均匀顶点ｄ＋１染色，即将其顶点集分拆成顶点个数至多相差１的ｄ＋１个无关集，并证明了关于一般有向图的线图的一个顶点染色定理．

基于超长指令字的顶点染色处理器设计

为了提高嵌入式图形处理器GPU(Graphic Process Unit)中顶点染色处理器,设计了一款超长指令字格式的可编程顶点染色处理器,采用六级流水线实现,每条指令在同一个周期最多执行7种操作,软硬件协同设计,降低了功耗.采用基于FPGA的验证方式,可编程顶点染色处理器在Xilinx Virtex-7FPGAs V2000T上最大工作频率达到50MHz,顶点的处理速度达到0.16M/s,处理一个顶点平均44个周期,在Synopsys公司Design Compiler工具130μm工艺综合下,主频150MHz,功耗约为177.742 8mW.

一类特殊图的顶点染色及其猜想的证明

通过研究一类特殊图的顶点染色,得到了以下结果:给出了S=p-3且p∈{4,5,6},图G的顶点染色数;证明了︱S︱>p2且︱S︱=p-3的图G不存在第p-m类图,m≥7且m是正整数;证明了︱S︱=p-3时,χ(G)≤4θ(G)+θ2(G)-1;进一步证明了猜想χ(G)≤4θ(G)+θ2(G)-1是正确的;为今后研究该猜想和图的顶点染色提供一些思想方法.

图的2-赋权乘积顶点染色

图G=(V,E)的k-赋权w是对图的每条边e∈E安排一个权值w(e)∈{1,2,…,k}.由边权导出图G的一个乘积顶点染色c,使得对图的每一个顶点v,c(v)=∏v∈e w(e)且对任意的边e=uv∈E,都有c(u)≠c(v).本文研究了Kn-e,Pm×Pn(m,n≥2)和Pm×Cn(m≥2)2-赋权乘积顶点染色的存在性.

一类特殊图的顶点染色数

如果图G含有的所有最大团存在公共顶点,且公共顶点的个数为κ,就称此图为第κ类图。据此,本文给出了研究图的顶点染色的一种新方法,并以此研究了一类特殊图的顶点染色及一些图的顶点染色数。

与图的顶点染色数有关的几个问题

设c(G)是无向简单图G(V,E)的顶点染色数,证明了:若︱S︱>p/2且︱S︱=p-m,则图G不存在第p-q类图,其中:q≥2m+1,m≥3且m∈Z^+;若︱S︱=p-4,则小x(G)≤p-3;若︱S︱=p-4,则x(G)≤4■(G)+■2(G)-1.

关于顶点染色的一个猜想

本文提出顶点染色的一个猜想:χ(G)≤|S|+C,其中χ(G)和|S|分别是一个图的顶点染色数和最大团的顶点数; C是常数且C∈Z^+。若C=1,p为图G的顶点数,我们证明对于|S|=p-6的一些图,有χ(G)≤p-5。

刍议图顶点正常染色的计数公式

图的染色计数问题是高中数学“计数原理”章节的常见题型.图的染色问题主要有顶点染色、边染色和面染色三类,这三类染色问题都可以归结为顶点染色问题.介绍了图顶点正常染色计数公式的背景、重要性质、“删边减收缩”算法和一般表达形式,最后举例介绍有特殊限制条件的顶点正常染色计数公式.

几类图的相邻顶点可区别的全染色

给出了几类特殊图相邻顶点可区别的全色数,如双路间和二部(V1,V2)间叠加匹配形成的系列图、双圈(prism)、双轮.并得到边连通度λ(G)=1的图相邻顶点可区别的全染色的性质.

基于Welsh-Powell染色的PCI自配置算法

提出了一种基于Welsh-Powell染色的PCI自配置算法,详细介绍了算法流程,并通过程序验证得出:该算法对PCI资源进行了合理分配,规避了小区间冲突、混淆和模三干扰。

图的完全b-染色与完全b-连续

图G的（k）b-染色是一个顶点染色，且在每一个色类中至少存在一个顶点，该顶点在其余每个色类中与至少一个顶点是邻接的。每个色类中满足此条件的顶点称作b-染色顶点。若用k颜色可对图Gb-染色，但用大于k种颜色都不能对G进行b-染色，称整数女为G的b-染色数，用符号φ（G）表示。

圈图与路径图的r-冠图的b-染色

图G的正常顶点染色中,若任意色类当中都存在顶点u,使得u在其他任意色类中至少有一邻居,称此正常顶点染色为b-染色。若k种颜色能够对G实现b-染色,而任意t>k,t种颜色都不能够对G实现b-染色,称k为G的b-染色数。研究了圈图与路径图的r-冠图的b-染色,通过构特殊造染色方案,给出了图Ir(Cn)与Ir(n P)b-染色数。

钻石项链图Nk的点被多重集可区别的E-全染色(2 ≤ k ≤ 165)

利用反证法和构造具体染色的方法,讨论了钻石项链图Nk的顶点被多重集可区别的E-全染色。给出了钻石项链图Nk的相应染色方案,构造了具体的钻石项链图Nk的点被多重集可区别的E-全染色,其中2 ≤ k ≤ 165。

关于图的(k,d)染色问题

对（ｋ，ｄ）染色问题的起源和进展情况作了简要的回顾；总结了其已有研究成果；并对Ｖｉｎｃｅ Ａ（１９８８）文中提出的问题给出了部分答案．

稀疏图平方图的染色数上界

图G的平方^G^2定义为顶点集V(G)=V(^G^2),并且uv∈E(^G^2)当且仅当u和v之间的距离至多为2.^G^2的色数χ(^G^2)是指使得^G^2存在正常k-顶点染色的最小整数k.用权转移的方法证明:如果mad(G)<4且Δ(G)≥7,则χ(^G^2)≤3Δ(G)+1;如果mad(G)≤4且Δ(G)≥8,则χ(^G^2)≤3Δ(G)+5.

关于非平面图染色的一个猜想

本文提出以下猜想:若θ(G)=2,则χ(G)≤9;若θ(G)≥3,则χ(G)≤6θ(G)-1。证明了当 |S|∈{p,p-1,p-2,p-3,p-4,p-5}时,该猜想是正确的。

轮图的列表染色

文章给出了边列表染色和顶点列表染色的定义,证明了对轮图,边选择数χLE(G)=△(G),点选择数χLE(G)=4,点边选择数χLE(G)=△(G)+1.

点染色和边赋权

Lyngsie,Thomassen和Zhong 在1-2-3-猜想的基础上提出了一个强化4-色定理的猜想:对于任意不含孤立边的平面图G,存在G的一个边赋权,使得对任意相邻的两个顶点u,v,有 我们称满足上述条件的边赋权w为G的一个3-边赋权4-染色。这是一个比4-色定理强很多的猜想。在本文中我们证明了阶数至少为3的树满足这个猜想。另外,利用4-色定理,我们证明了每一个平面图 存在一个4-边赋权4-染色。