题名 用最小下标原则避免对偶单纯形迭代的循环
1
作者
吴举林
杜林古
机构
青岛大学数学系
山东纺织工学院
出处
《青岛大学学报(工程技术版)》
CAS
1990年第3期78-81,共4页
文摘
本文提出了用对偶单纯形方法求解线性规划问题时避免循环的最小下标原则,即:(ⅰ)当有几个基变量可以出基时,就选下标最小的那个为换出变量;(ⅱ)当有几个非基变量可以进基时,就选下标最小的那个为换入变量.
关键词
对偶单纯形法
循环
最小下标原则
Keywords
dual simplcxmethod
cycling
the smallest-subseript rules
分类号
TB-55
[一般工业技术]
题名 关于图的强Helly性质
2
作者
吴举林
崔玉亭
机构
青岛大学
青岛海洋大学
出处
《青岛海洋大学学报(自然科学版)》
CSCD
1992年第4期122-127,共6页
文摘
给出图的点团二分图和边团二分图具有强Helly性质的充分必要条件,证明了使点团二分图具有强Helly性质的图的团贪心性和团不变性。
关键词
强Helly性质
点团二分图
图
Keywords
strong Helly property
vertex-clique bipartite graph
edge-clique bipartite graph
clique-greedy graph
clique-invariance
分类号
O157.5
[理学—基础数学]
题名 关于图的领域复盖
3
作者
吴举林
机构
青岛大学
出处
《青岛大学学报(自然科学版)》
CAS
1990年第1期1-6,共6页
文摘
图G=(V,E)中一个点V的领域是点V及其邻点导出的G的子图。领域复盖问题就是求一级量小个的领域,使其复盖子G的每一条边。本文证明了无三角形图上和分离图上的领域复盖问题是NP-完全问题。通过研究集族的强Helly性质,得到了领域复盖问题可转化为团复盖问题的条件一图的领域二分具有强Helly性质。文中给出了弦图的领域二分图具有强Helly性质的禁用子图形式的充分必要条件。
关键词
图
邻域复盖
NP-完全问题
弦图
邻域二分图
分类号
O157.5
[理学—基础数学]
题名 关于图的导出森林独立系统
4
作者
吴举林
机构
青岛大学数学系
出处
《高校应用数学学报(A辑)》
CSCD
北大核心
1991年第3期420-426,共7页
文摘
本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.
关键词
独立系统
组合规划
图
导出森林
Keywords
Independence system. Matroid. Strongly chordal graphs. Algorithm.
分类号
O224
[理学—运筹学与控制论]
题名 团剖分问题的复杂性
5
作者
吴举林
机构
青岛大学数学系
出处
《应用数学》
CSCD
北大核心
1990年第3期91-92,共2页
文摘
本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性.
关键词
无向简单图
团剖分问题
复杂性
分类号
O157.5
[理学—基础数学]
题名 弦图的团复盖和邻域复盖
6
作者
吴举林
机构
青岛大学数学系
出处
《青岛海洋大学学报(自然科学版)》
CSCD
1991年第1期131-137,共7页
文摘
证明了弦图的团二分图是子树二分图,从而把弦图上一般形式的团复盖问题化为弦图上的对点团复盖,可以在多项式时间内求解。对强弦图上的邻域复盖问题,本文提出两条求解途径:一是化为弦图上的团复盖问题,一是化为可用组合方法求解的线性规划问题。
关键词
图
弦图
团复盖
邻域
Keywords
clique covering,neighborhood covering,chordal graphs,strongly chordal graphs,totally balanced Dipartite graphs
分类号
O157.6
[理学—基础数学]
题名 关于弦图的团序列
7
作者
吴举林
机构
青岛大学数学系
出处
《山东师范大学学报(自然科学版)》
CAS
1991年第1期32-35,共4页
文摘
设G=(V,E)是一个有限无向简单图,C_k是G中具有k个点的完备子图的数目。序列(C_1,C_2,…)称为图G的团序列。本文给出了整数序列是弦图的团序列的充分必要条件、两个弦图有相同的团序列的充分必要条件和弦图k连通的充分必要条件。
关键词
弦图
色多项式
团序列
Keywords
chordal graph
chromatic polynomial clique sequence
分类号
O157.5
[理学—基础数学]
题名 由树导出的强弦图
8
作者
吴举林
出处
《青岛大学学报(自然科学版)》
CAS
1991年第1期37-41,共5页
关键词
树
领域子树
强弦图
图
交图
分类号
O157.5
[理学—基础数学]
题名 关于图的邻域复盖(Ⅱ)
9
作者
吴举林
出处
《青岛大学学报(自然科学版)》
CAS
1991年第3期64-70,共7页
关键词
图论
邻域复盖
闭复盖
邻域图
分类号
O175.5
[理学—基础数学]
题名 箭线图的系统设计
被引量:1
10
作者
吴举林
机构
青岛大学数学系
出处
《系统工程理论与实践》
EI
CSCD
北大核心
1991年第5期16-18,共3页
文摘
箭线图的绘制是对大规模工程进行网络控制的基础。绘制箭线图一般都要用到引入虚工序,以帮助建立实工序的先后关系。由于虚工序的引入,使箭线图变得复杂,使得计算网络有关参数和对工程施实控制变得困难。在绘制箭线图时,怎样较少地引入虚工序,又能正确地表示工序的顺序关系呢?黄沛钧、程国平和李随成提出了简便有效的途径和方法。他们的方法改进了[3]中的方法。
关键词
剪线图
系统设计
网络图
分类号
N94
[自然科学总论—系统科学]
题名 弦图的最大权强独立集
11
作者
吴举林
机构
青岛大学
出处
《应用数学学报》
CSCD
北大核心
1991年第1期50-56,共7页
文摘
一、 引言 本文中未加说明的图论术语来自文献[1]。图G=(V,E)称为弦图,如果G的任何长度大于3的圈都有弦,或者等价地,任何长度大于3的圈都不会是G的点导出子图。本文中,子图总是指点导出子图,点子集S导出的G的子图记为G[S]。团是指完备子图,通常用它的点集来表示。如果图G的每个点v都带有点权w(v),则点子集S的权定义为S中点的权的和。
关键词
弦图
最大权
独立集
整数规划
分类号
O157.5
[理学—基础数学]
题名 弦图上团划分数问题的复杂性
被引量:1
12
作者
马绍汉
吴举林
机构
山东大学计算机科学系
青岛大学数学系
出处
《山东大学学报(自然科学版)》
CSCD
1989年第2期14-19,共6页
文摘
本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。
关键词
弦图
图覆盖数
团划分数
NP-困难
Keywords
chordal graph, cligue covering number, cligue partition number, NP-hardness
分类号
O157.5
[理学—基础数学]
题名 亲于图的邻域复盖
13
作者
吴举林
出处
《泸天化科技》
1990年第1期1-6,共6页
关键词
图
邻域复盖
NP-完全问题
团复盖
分类号
O157.5
[理学—基础数学]