强完美图定理及相关的问题

介绍强完美图定理(The Strong Perfect Graph Theorem,SPGT)的历史和获证经过,同时简述SPGT被克服后生发的一些新问题,以期对图理论的一般研究起到鼓励和促进作用.因具体的证明浩大聱曲,在技术的部分仅注重框架而不涉及细节.

基于超完美图着色的存储分配算法

为了提高性能,一些应用需要在编译时对主存进行针对性的管理。提出了基于超完美图的主存分配方法,其基本思想是通过生命周期分割将一般的相干图转换为超完美图,从而可以使用已有的线性时间的区间着色算法完成主存的分配。分别基于自底向上的积极生命周期分割策略和自顶向下的被动生命周期分割策略,实现了两个分配算法。初步评测表明,我们的分配算法是有效的编译时管理主存手段。

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.

强完美图猜想的两个等价命题

讨论了图的 P_4-封闭集的几个基本性质,证明了当且仅当以下两命题中的任何一个成立时.著名的强完美国猜想成立:①极小不完美图是无大偶洞的;②极小不完美图不含 P_4-封闭集.

图的笛卡尔积图的结构及其完美性(英文)

目的研究笛卡尔积图的完美性.方法利用图的笛卡尔积刻画了扩容图.结果与结论得到任意图与其线图的笛卡尔积与扩容图的密切关系,证明了完全扩容图的完美性。

关于完美3-全图的一点注记

得到３全图含有奇洞的充要条件。

几个特殊超图在完美图上的应用

由超图与其线图的关系,分别证明了单模超图、平衡超图、树形超图的线图是完美图。定义了k-完美超图,使其成为完美图的推广。讨论了正规超图和拟正则超图的完美性,并得出相应的结果。

一种层次完美差异图的超节点拓扑结构研究

超节点网络采用两层结构组织超节点和普通节点,有利于提高网络性能和搜索效率。而现有的超节点拓扑结构及其动态维护机制和搜索路由机制存在维护复杂或查询产生信息多的缺陷。针对这些问题,提出一种新颖的层次完美差异图HPDG(k)拓扑结构,建立了一种超节点网络HPDGN,给出了HPDGN的路由和动态维护机制。它具有常数度数和固定邻接点特性,不但支持模糊查询,而且解决了结构化超节点拓扑对动态性支持差的问题。与现有拓扑结构的模拟对比实验结果表明,HPDGN减少了查询所带来的带宽消耗,具有更小的拓扑构造和失效修复成本。

关于二次型图的完美性

本文应用强完美图定理,解决了二次型图的完美图判别问题.

基于二分图K优完美匹配的虚拟网映射算法设计

为提高虚拟节点映射的可行性,基于可行性检验定理和用于衡量节点可用性的节点等级指标,设计了基于二分图K优完美匹配的以降低映射代价为目标的虚拟网映射迭代算法。实验表明,所提出的算法能提高虚拟网构建请求接受率和虚拟网构建收益代价比,从而提高物理网提供商的收益。

基于k-完美差异图的超节点拓扑结构构造

在超节点网络中,超节点拓扑结构及其动态维护和搜索路由机制,是影响网络性能和搜索效率的关键因素之一。在完美差异图(PDG)的基础上,提出了一种新的k-PDG结构,并利用该结构,建立了超节点网络——KPDGN,给出了KPDGN的动态维护和搜索路由机制。分析和模拟结果表明:KPDGN具有常数度数和固定邻接点特性,减少了查询所产生的带宽消耗,降低了拓扑构造和修复成本。

3_线图的完美性

本文给出了3—线图含有奇洞的充要条件,从而使3—线图的完美图猜想得到彻底解决,同时,本文还给出完美3—线图是k点染色的充要条件及3—线图是连通的充要条件等一些结论。

Rivas-Eddy RNA二级结构图书嵌入分类的实现方法

书嵌入数是对图进行分类的一个拓扑标准,通常来说,计算一个图的书嵌入数及给出一种嵌入实例都是NP完全问题。针对Rivas-Eddy(R&E)类中RNA分子的二级结构图,从二级结构图的语法出发,通过其交叉关系图的点着色,构造性地得到了RNA分子二级结构图书嵌入的具体实现方法,完成了对RNA分子二级结构的书嵌入分类。该方法具有多项式时间复杂性,为求解NP完全问题提供了有益的参考。

不含3K_1+K_2和C_4为导出子图的图的色数

Gyárfás曾猜想:对于每一个不含森林F作为导出子图的图G,存在整数函数f(F,ω(G))使得χ(G)≤f(F,ω(G)),其中χ(G)和ω(G)分别表示图的色数和团数。以强完美图定理为基础,通过对不含3K1+K2和C4作为导出子图的图的结构进行分析,根据图的独立数进行分类讨论,得到该类图色数的关于团数线性函数的表达式的上界。

关于路图P_k(G)的一点注记

本文主要得到结论：图Ｐ３（Ｇ） 是完美图的充要条件是图Ｇ不含有长至少为５ 的奇圈和图Ｈ 作为子图；２－连通图Ｇ的路图Ｐ３（Ｇ）是２－连通图；以及ｘ（Ｐ３（ｋｎ））≤４，当ｎ≤９时等．

完美正方形补遗

笔者在文[1]中曾介绍过完美正方形——用规格完全不同的小正方块拼成的无缝隙、无重叠的大正方形(或者说可裁成规格完全不同的小正方块且无剩余的大正方形).这个问题是1930年前后英国剑桥大学的四位学子提出的。

边临界图

本文定义了边临界图,并对其进行了研究,主要得到了以下性质:1)若G是△(G)边临界图,则G必为星图S△(G);2)若G是△(G)+1边临界图,则G没有割边;3)若G是△(G)+1边临界图,则对任意边uv,有d(u)+d(v)≥△(G)+2;4)若G是△(G)=3的简单连通图,且ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=χ/(G)=△(G)+1。此外,我们还提出猜想:"若G是简单图,G是△(G)+1边临界图,则ν(G)为奇数",并证明了此猜想与猜想"若G是简单图,ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=△(G)+1。"是等价的等结论。

局部颜色特征在基于内容的图像检索中的应用

全局颜色直方图是基于内容的图像检索中使用最广泛的特征之一。然而 ,它不包含颜色的空间分布关系 ,因此不同的图像可能具有同样的颜色直方图。采用图像分块的局部直方图方法考虑了颜色的位置信息 ,但却不具有旋转、平移不变性。文中利用分块颜色矩 ,借助带权二部图的最小完美匹配提出了一种新的相似度量方法 ,既考虑了颜色的空间分布关系 ,又具有旋转、平移不变性。