图的树宽的分解定理(英文) 被引量：9

1

作者 林诒勋 《数学研究》 CSCD 2000年第2期113-120,共8页

图的树宽问题是著名的 NP-困难问题 .其分解原则在确定树宽的一般算法和特殊算法中有重要应用 .本文给出这方面的若干定理 .

关键词 弦图 树宽 分解定理 图 算法

下载PDF 职称材料

图的扩张与稀疏矩阵计算中的若干优化问题(英文) 被引量：7

2

作者 林诒勋 《数学进展》 CSCD 北大核心 2001年第1期9-21,共13页

本文研究从稀疏矩阵计算中提出的若干离散最优化问题，即带宽，树宽，路宽，侧廓，扩充侧廓及填充问题．实际上，它们是一类图扩张问题；这些问题同时来源于各式各样的课题，如图子式理论，ＶＬＳＩ电路设计，互联网络及分子生物学等．... 本文研究从稀疏矩阵计算中提出的若干离散最优化问题，即带宽，树宽，路宽，侧廓，扩充侧廓及填充问题．实际上，它们是一类图扩张问题；这些问题同时来源于各式各样的课题，如图子式理论，ＶＬＳＩ电路设计，互联网络及分子生物学等．本文从图论观点着重讨论两种统一途径：图的标号及图的扩张． 展开更多

关键词 稀疏矩阵 标号 扩张 计算 离散最优化 图 带宽 树宽 路宽

下载PDF 职称材料

树宽较小的图的线性荫度

3

作者 陈宏宇 《山东大学学报（理学版）》 CAS CSCD 北大核心 2024年第6期25-28,35,共5页

设G=(V,E)为一个图,如果染相同颜色α的边导出的子图是一个线性森林,其中1≤α≤t,则从E(G)到{1,2,…,t}的一个映射φ称为t-线性染色。线性荫度la(G)表示图G的所有t-线性染色中最小的t。本文确定了最大度为Δ,树宽最多为Δ+1/4的图G,其... 设G=(V,E)为一个图,如果染相同颜色α的边导出的子图是一个线性森林,其中1≤α≤t,则从E(G)到{1,2,…,t}的一个映射φ称为t-线性染色。线性荫度la(G)表示图G的所有t-线性染色中最小的t。本文确定了最大度为Δ,树宽最多为Δ+1/4的图G,其线性荫度la(G)=「Δ/2」。 展开更多

关键词 线性荫度 线性染色 树宽

原文传递

图的树分解及其算法应用研究进展 被引量：5

4

作者 高文宇 李绍华 《计算机科学》 CSCD 北大核心 2012年第3期14-18,共5页

图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做... 图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。 展开更多

关键词 图子式 树宽 树分解 参数算法 近似算法

下载PDF 职称材料

图的树宽的结构性结果(英文) 被引量：5

5

作者 林诒勋 《数学进展》 CSCD 北大核心 2004年第1期75-86,共12页

图G的树宽是使得G成为一个k-树的子图的最小整数k.树宽的算法性结果在图子式理论及有关领域中已有深入的研究.本文着重讨论其结构性结果,包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质.

关键词 图论 树宽 图子式 拓扑不变性 子式单调性 可分解性

下载PDF 职称材料

具有大的奇围长的符号图的圆环染色

6

作者 周欢 朱绪鼎 《数学进展》 CSCD 北大核心 2023年第5期795-803,共9页

图G的一个圆环r-染色(r≥2)是将G的每个顶点v对应到一个周长为r的圆上的点的一个映射f,使得对于G中任意的边xy,f(x)和f(y)在圆上的距离不小于1.G的圆环色数χc(G)是G存在圆环r-染色的最小实数r.符号图的圆环染色和图的圆环染色基本相同... 图G的一个圆环r-染色(r≥2)是将G的每个顶点v对应到一个周长为r的圆上的点的一个映射f,使得对于G中任意的边xy,f(x)和f(y)在圆上的距离不小于1.G的圆环色数χc(G)是G存在圆环r-染色的最小实数r.符号图的圆环染色和图的圆环染色基本相同,不同的是对于负边xy,我们要求f(x)和f(y)的对点在圆上的距离不小于1.符号图(G,σ)的圆环色数是使得(G,σ)在圆环r-染色的最小实数r.本文证明:对于任意正整数k和实数ε>0,存在整数g使得对于任意树宽至多为k的符号图(G,σ),如果(G,-σ)的负围长至少是g,那么(G,σ)的圆环染色数至多是2+ε. 展开更多

关键词 符号图 环染色 树宽 奇围长 负围长

原文传递

树与偏k-树的乘积的树宽(英文) 被引量：3

7

作者 原晋江 《运筹学学报》 CSCD 北大核心 2001年第3期57-62,共6页

本文确定了一棵树与一个ｋ－连通偏ｋ－树的乘积图的树宽．其中，偏ｋ－树是一个树宽为Ｋ的图．

关键词 树宽 前沿带宽 偏k-树 图

下载PDF 职称材料

基于平均度的树分解启发式算法 被引量：3

8

作者 沈静 任耀峰 +1 位作者 梅丹 杨美妮 《海军工程大学学报》 CAS 北大核心 2019年第5期49-53,共5页

很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数... 很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数构造顶点消除序列,快速得到树分解的宽度。在随机正则图和DIMACS图着色实例上的测试结果表明:这两种算法简单易实现,与最小填边法相比能找到更优的树宽上界。 展开更多

关键词 树宽 树分解 启发式算法

下载PDF 职称材料

复杂网络中近似最短路径问题 被引量：2

9

作者 刘微 肖华勇 《计算机系统应用》 2016年第5期107-112,共6页

随着网络规模的不断增大,经典算法(如Dijkstra等)效率越来越低.针对这一问题,研究者们提出了许多近似搜索算法,但如何既能提高搜索效率又能保持准确性一直是一大难点.本文根据复杂网络的结构特性引入区域划分,同时改进树分解的构造,将... 随着网络规模的不断增大,经典算法(如Dijkstra等)效率越来越低.针对这一问题,研究者们提出了许多近似搜索算法,但如何既能提高搜索效率又能保持准确性一直是一大难点.本文根据复杂网络的结构特性引入区域划分,同时改进树分解的构造,将图构造成一棵树进行搜索,得到了一个新的适合于复杂网络的最短路径近似算法.此外通过实例验证,该算法不仅在一定程度上降低了计算复杂性,而且保持了较高的近似准确性. 展开更多

关键词 复杂网络 树分解 树宽 树 最短路径近似算法

下载PDF 职称材料

关于多重有向根树的一种乘法运算 被引量：1

10

作者 祁忠斌 尹文基 《兰州工业高等专科学校学报》 2004年第3期1-4,共4页

有向根树就是只有一个顶点的出度为0,其余顶点的出度均为1的有向树.张福基等人提出了有向根树之间的一种乘法运算(记为 ),并指出有限个有向根树经这种运算后仍为一个有向根树.在此把这种运算推广到多重有向根树上,证明了这种运算对多重... 有向根树就是只有一个顶点的出度为0,其余顶点的出度均为1的有向树.张福基等人提出了有向根树之间的一种乘法运算(记为 ),并指出有限个有向根树经这种运算后仍为一个有向根树.在此把这种运算推广到多重有向根树上,证明了这种运算对多重有向根树的封闭性,并证明了有限个多重有向根树经这种运算后为一棵有向根树当且仅当每个多重有向根树为一棵有向根树.另外,计算了这种运算结果(多重有向根树)的分支个数及每个分支的树高与树宽. 展开更多

关键词 多重有向根树 乘法运算 树宽 树高 图论

下载PDF 职称材料

几类特殊图的树宽 被引量：2

11

作者 冯爱芬 王秀梅 王锋叶 《洛阳师范学院学报》 2004年第2期7-9,共3页

本文主要研究了一些特殊图的树宽 .利用树宽的分解定理 ,分别给出了多个图的联 ,(m ,n) -构形 ,球面经纬线图Cm ,n(n =3,4) ,扇形格子图Fm ,n(m =1 ,2 )等的树宽表达式 ,并给出了进一步研究的建议 .

关键词 树宽 扇形格子图 球面经纬线图 (m n)-构形

下载PDF 职称材料

基于树宽的警示传播算法收敛性分析 被引量：1

12

作者 谢志新 王晓峰 +3 位作者 于卓 曹泽轩 吴宇翔 莫淳惠 《计算机应用研究》 CSCD 北大核心 2022年第10期3061-3064,3077,共5页

警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式... 警示传播算法作为一种基本的信息传播算法,其收敛时求解可满足性问题十分有效,但因子图结构较为复杂时,算法往往不收敛导致求解失败。为了对这种现象给予理论解释,同时对警示传播算法收敛性进行有效分析,利用树分解方法构造了命题公式对应因子图的树宽度量模型,计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系,给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析,结果表明该方法有效,对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。 展开更多

关键词 警示传播算法 收敛性 树宽 命题公式 可满足性问题

下载PDF 职称材料

k-树的补图的最小填充和树宽(英文)

13

作者 张振坤 王秀梅 林诒勋 《运筹学学报》 CSCD 北大核心 2006年第2期59-68,共10页

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．

关键词 运筹学 组合优化 填充 树宽 k-树 k-补树 团树

下载PDF 职称材料

图的弱准带宽和前沿带宽 被引量：1

14

作者 原晋江 《中国科学（A辑）》 CSCD 1995年第11期1121-1129,共9页

引入图的弱准带宽和前沿带宽,并将其应用于研究图的带宽、拓扑带宽、填充、侧廓、路宽和树宽等。

关键词 带宽 填充 侧廓 路宽 树宽 图

全文增补中

K_3与偏k-树乘积的树宽 被引量：1

15

作者 冯爱芬 杨万才 《辽宁师范大学学报（自然科学版）》 CAS 北大核心 2005年第3期273-275,共3页

图G的树宽是使图G成为1个k-树的子图的最小整数k,也可以基于“前沿分支”的观点定义树宽.若知道1个图的树宽的下界,又能构造1种标号,使其达到下界值,则此图的树宽即能确定.笔者利用这种方法确定了K3与偏k-树乘积图的树宽,给出了它的树... 图G的树宽是使图G成为1个k-树的子图的最小整数k,也可以基于“前沿分支”的观点定义树宽.若知道1个图的树宽的下界,又能构造1种标号,使其达到下界值,则此图的树宽即能确定.笔者利用这种方法确定了K3与偏k-树乘积图的树宽,给出了它的树宽表达式及达到此树宽的标号. 展开更多

关键词 图 偏k-树 标号 树宽

下载PDF 职称材料

任意连通图与偏k-树乘积图的树宽 被引量：1

16

作者 冯爱芬 黄志勇 《河南科技大学学报（自然科学版）》 CAS 2008年第1期78-79,共2页

一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图G与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了... 一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图G与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了在满足顶点数n≥mk的条件下二者乘积图树宽表达式。 展开更多

关键词 树宽 连通图 乘积图 偏k-树

下载PDF 职称材料

割宽与图的有关参数(英文)

17

作者 林诒勋 《郑州大学学报（理学版）》 CAS 2002年第1期1-5,共5页

起源于 VLSI设计及网络通讯 ,一个图的割宽是将它嵌入于一条路的最小“拥挤度”.研究了割宽与其它图论参数的关系 ,包括与带宽、路宽。

关键词 标号 嵌入 割宽 图论参数 带宽 路宽 树宽 页数 最小“拥挤度”

下载PDF 职称材料

一棵赤松的制作过程

18

作者 任晓明 朱顺如 +1 位作者 陈勇 刘启华 《花木盆景（下半月）》 2009年第4期26-28,共3页

图1、图2、图3、创作前赤松的各面树相。干部直径16cm,高150cm,树宽180cm。树干虬曲多变,树势向一方生长,但枝片分布较为凌乱。

关键词 赤松 树相 树宽

下载PDF 职称材料

树的线图的图扩充问题

19

作者 侯亚林 张振坤 李学志 《数学的实践与认识》 CSCD 北大核心 2009年第16期252-259,共8页

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、... 图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题. 展开更多

关键词 填充数 树宽 侧廓 树 线图

原文传递

2006年《情报科学》总目录

20

《情报科学》 CSSCI 北大核心 2006年第12期1914-1920,共7页

关键词 情报科学 知识产权保护 数据库 数据库系统 企业知识资本 竞争情报 树宽 郑建明 层次分析法 A H P法 数字图书馆建设

下载PDF 职称材料