“三色图”的一个充分条件

文中证明了定理:若图G中不存在与K_4同胚的子图,则其色数X(G)≤3,进而得到三色图的一个充分条件。只要能证明与上述定理类似的一个定理:“若图G中不存在与K_5同胚的子图,则其色数X(G)≤4”,则世界著名的“四色猜想(4CC)”即得证。     

利用矩阵求极大相容类的一种方法

寻找相容关系的极大相容类和简单图的极大完全子图,在解决二元关系与数据挖掘和管理决策中的具体问题时有重要作用。利用相容关系的极大相容类与简单图的极大完全子图之间的对应关系,对极大完全子图的路径长度进行分析,得到了关于极大完全子图路径长度的一个定理。并根据该定理构造了一个用矩阵的路径长度搜索简单图的极大完全子图的方法,进而利用该方法找出了对应相容关系的极大相容类。     

图C4t∪4t的调和标号

不连通图的标号问题是图论研究中的重要课题之一,本文首先给出了调和图的定义,然后证明了两个图C4t的并图C4t∪C4t是调和图。     

关于图的一个边重构性定理之证明

若图Ｇ存在一个次为δｐ＋ｋ的顶点至少和ｋ＋１个小次顶点相邻,则Ｇ是边可重构的（δｐ为某小次,ｋ≥０为整数）。文（１）并没有证明,本文给出其证明方法,且得到一个推论。     

具有正交(g,f)-因子分解的子图

设G是一个图 ,g (x)和f (x)是定义在V (G)上的整数值函数 ,且对任意的x∈V (G) ,设g (x)≤f (x) ,H是G的一个子图 ,F ={F1,F2 ,… ,Ft}是G的一个因子分解 ,如果对任意的 1≤i≤t,|E (H)∩E (Fi) |=1 ,则称F与H正交。闫桂英和潘教峰在文 [3]中提出如下猜想 :设G是一个 (mg+k,mf-k) -图 ,1≤k相似文献   

路、Ti^＊广义θ-图的成分着色

设H是一个超图（图）,对于它的一个k边着色c：E（H）→{1,2,∧k},我们记f（H,c）是由k种颜色中,由同一色类导出的子超图（子图）中所含分枝数最少的子超图（子图）的分枝数。fk（H）表示H中所有k边着色中f（H,c）的最大值,即fk（H）=maxf（H,c）。本文主要研究了路、Ti’、广义θ-图的成分着色,并得到了fi（Pn）=（n-1/k,f（Ti^＊）=[i-1/k]＋1∫k（Gθ）=2     

关于图的n-Irredundance数和n-Domination数

设G是简单连通图,r_n~c(G)和ir_n(G)分别表示图G的连通n-Domination数和n-Irredundance数、本文证明了如下结论:r_n~c(G)≤(3n+1)ir_n(G)-2n。     

警报关联图：一种网络脆弱性量化评估的新方法

作为一种基于模型的脆弱性分析技术,攻击图能够识别网络中存在的脆弱性和它们之间的相互关系,分析出可能的攻击路径和潜在威胁.论文在攻击图的基础上提出了警报关联图的概念,利用攻击图中蕴含的脆弱性先验知识,将实时IDS警报信息映射到攻击路径,动态反映攻击进程和攻击者意图.在此基础上提出了一种基于警报关联图的网络脆弱性量化评估方法,通过计算警报关联边的权值对网络脆弱性进行动态分析,这种方法结合了静态的网络脆弱性先验知识和动态变化的攻击者意图,能有效反映网络脆弱性在动态攻击情况下的变化.     

色空间对HDRI亮度测量方法的影响

相机内置预处理环节中的白平衡、色度空间转换是数码成像过程中的重要环节,sRGB和Adobe RGB是数码相机2种常用的色空间.为进一步研究色空间对HDRI亮度测量方法的影响,在荧光灯照明的实验室,分别利用sRGB和Adobe RGB色空间对色板成像,测量该亮度测量方法中各色板的标定因数,计算各色板标定因数的相对不确定度.实验结果表明:2种不同色空间获得的标定因数不同,且Adobe RGB色空间标定因数相对不确定度的平均值小于sRGB色空间的;色空间改变后,标定因数需要重新进行标定,且优先选用色域较宽的Adobe RGB色空间.     

关于图的距离Irredundance数

G=(V,E)是简单连通图,用G—v表示从G中删除v以及与v相关联的边所得到的图,ir_n(G)表示G的n—irredundance数,证明了下列不等式: ir_n(G—v)≥(ir_n(G) 1)/2这个结果推广了Favaron的相应结论。     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

一种基于模型的系统设计方法

提出一种面向功能需求,基于模型的"V"型系统设计方法,通过图形化行为建模技术对系统功能进行分解,运用多种仿真和验证技术,在设计过程中实现对系统功能、行为以及与需求规范的一致性和完整性进行实时验证,及时发现并纠正错误,从而避免在产品的物理原型阶段或测试阶段才发现系统设计的错误.     

P3，4m的优美性

设u、v是两个固定顶点,用b条内部互不相交且长度均为a的道路连接u、v所得到的图用Pa,b表示.Kathiresan证实P2r,2m-1(r,m均为任意正整数)是优美的,且猜想除了(a,b)=(2r+1,4s+2)外,所有的Pa,b都是优美的.杨元生已证实P2r+1,2m-1是优美的.本文证明P3,4m是优美图,从而当a=3时Kathiresan猜想成立.     

GPS定位系统显示定位座标的一种方法

通过对地图座标的分析,介绍了在计算机上显示的地图中,显示GPS定位信息的座标转换方法、图形调用方法,并结合实际进行了分析。     

一种面向虚拟维修训练的拆装序列描述方法

通过分析机电产品的维修特点、虚拟维修训练的需求以及产品维护规程的结构特点,提出了一种采用树型和有向图混合结构来统一描述产品维护规程和拆卸安装序列的方法,并以Visual C++/MFC为工具,开发了维护规程控件,解决了虚拟维修训练中产品维护规程和拆卸安装序列的同步直观显示、约束关系解算、规程文件存取等问题,并为维护规程的可视化编辑提供了工具。实践表明,该方法满足虚拟维修训练对维护规程和拆装序列的描述要求。     

Graph distance‐dependent labeling related to code assignment in computer networks

For nonnegative integers d₁, d₂, and L(d₁, d₂)‐labeling of a graph G, is a function f : V(G) → {0, 1, 2, …} such that |f(u) − f(v)| ≥ d_i whenever the distance between u and v is i in G, for i = 1, 2. The L(d₁, d₂)‐number of G, λ(G) is the smallest k such that there exists an L(d₁, d₂)‐labeling with the largest label k. These labelings have an application to a computer code assignment problem. The task is to assign integer “control codes” to a network of computer stations with distance restrictions, which allow d₁ ≤ d₂. In this article, we will study the labelings with (d₁, d₂) ∈ {(0, 1), (1, 1), (1, 2)}. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

一个基于图着色的CACHE优化方法

提出了一个编译时的Cache管理优化方法。该方法根据访存行为将程序中的数据划分成若干数据对象,根据数据对象的大小将Cache划分为一个带有别名的伪寄存器文件,每个伪寄存器由若干Cache行组成,可以容纳一个数据对象;使用一个经过改进的图着色寄存器分配算法来决定这些对象在Cache中的位置以及发生冲突时的替换关系。数据对象的划分将Cache的管理分为两个层次,一个是编译时编译器对粗粒度的数据对象的管理,另一个是运行时硬件对细粒度的Cache行的管理,这样编译器和硬件的优势都得到发挥。基于GCC进行了方法实现,并通过simplescalar构造了支持Cache Coloring的硬件模拟平台。实验结果表明Cache Coloring能较好地开发程序的局部性,降低Cache失效率。