子图识别的层分解方法

子图识别问题(SRP)就是在一个图G中确定并寻找是否存在和另一个图H相同构的子图．本文将引入图的层分解概念，并以此为基础建立识别图的同构子图的算法．该算法的复杂性为O(n(△-1)^k-1)，其中△是图G的度，即G中点的最大度，n，k分别是图G，H的阶．     

二分（0，mf—m＋1）-图的正交（0，f）-因子分解

设G=（X,Y,E（G））是一个二分图,分别用V（G）=X∪Y和E（G）表示G的顶点集和边集．设f是定义在V（G）上的整数值函数且对任意x∈V（G）有f（x）≥k．设H1,H2,…,Hk是G的k个顶点不相交的子图,且｜E（Hi）｜=m,1≤i≤k．本文证明了每个二分（0,mf—m＋1）．图G有一个（0,f）-因子分解正交于Hi（i=1,2,…,k）     

一个复杂网络中完全子图的搜索算法

现实中很多复杂网络是由完全子图通过公共的节点连接而成的．本文提出了一个复杂网络中完全子图的搜索算法，并通过实例说明了所提算法的有效性．     

关于k—消去图的若干新结果

设G是一个图．k是自然数．图G的一个k-正则支撑子图称为G的一个k-因子．若对于G的每条边e．G—e都存在一个k-因子，则称G是一个k-消去图．该文得到了一个图是k-消去图的若干充分条件，推广了文［2—4］中有关结论．     

与任意图正交的[0,ki]1^m—因子分解

设G是一个图,k1,…,km,是正整数,若图G的边能分解成m个边不交的[0,k1]-因子 F1,…,[0,]-l因子Fm,则称F＝{F1,…,Fm}是G 的一个[0,ki]1^m-因子分解,如果H是G的一个有m条边的了了图且对任意的1≤i≤m有E（H）E（Fi)=1,则称F与H正交,证明了若G是一个[0,k1 ,…, km-m 1]-图,。H是G的一个有m条边的子图,则图G有一个[0,ki]1^m-因子分解与H正交。     

二部图上完美匹配的正交匹配分解

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。     

与任意图正交的［0，ki］m1-因子分解

设G是一个图, k1,…, km是正整数.若图G的边能分解成m个边不交的［0,k1］-因子 F1,…,［0,km］-因子Fm,则称＝F1,…,Fm是G的一个［0,ki］m1-因子分解.如果H是G的一个有m条边的子图且对任意的1≤I≤m有｜E(H)∩E(Fi)｜＝1,则称与H正交.证明了若G是一个［0,k1＋…＋km－m＋1］-图,H是G的一个有m条边的子图,则图G有一个［0,ki］m1-因子分解与H正交.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

关于k－复盖图的几个条件

设Ｇ是一个图，ｋ为正整数．图Ｇ的一个ｋ－正则支撑子图Ｆ称做图Ｇ的一个ｋ－因子．若图Ｇ的每一条边ｅ都属于Ｇ的一个ｋ－因子，则称Ｇ是一个ｋ－复盖图．本文给出了一个图Ｇ是ｋ－复盖图的几个充分条件．     

与任意图正交的[0,k_i]_1~m-因子分解

设G是一个图 ,k1,… ,km 是正整数·　若图G的边能分解成m个边不交的 [0 ,k1]_因子F1,… ,[0 ,km]_因子Fm,则称 F =F1,… ,Fm 是G的一个 [0 ,ki]m1_因子分解·　如果H是G的一个有m条边的子图且对任意的 1≤i≤m有｜E(H) ∩E(Fi) ｜=1,则称 F与H正交·　证明了若G是一个 [0 ,k1 … km-m 1]_图 ,H是G的一个有m条边的子图 ,则图G有一个 [0 ,ki]m1_因子分解与H正交     

图Gn的优美表示

将给出三个结果：（i）如果图G是SZ（｜S｜=n≥2）上的整数和图,那么0∈S当且仅当图G至少有一个（n-1）度顶点;（ii）图G（G≠K2）是至少有两个零点的整数和图当且仅当G■K2·Gn;（iii）设图G（G≠K2）是SZ上的整数和图,｜S｜=n＋2,n∈N＋.若图G至少有两个零点,则S={mx｜m=-1,0,1,2,…,n;x∈Z且x≠0}.     

The traveling salesman problem on a graph and some related integer polyhedra

Given a graphG = (N, E) and a length functionl: E , the Graphical Traveling Salesman Problem is that of finding a minimum length cycle goingat least once through each node ofG. This formulation has advantages over the traditional formulation where each node must be visited exactly once. We give some facet inducing inequalities of the convex hull of the solutions to that problem. In particular, the so-called comb inequalities of Grötschel and Padberg are generalized. Some related integer polyhedra are also investigated. Finally, an efficient algorithm is given whenG is a series-parallel graph.Work was supported in part by NSF grant ECS-8205425.     

Recognizing Balanceable Matrices

A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/±1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuéjols, Kapoor and Vušković gave an algorithm to test if a 0/±1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists. Received: October 2004     

A method of centers algorithm for certain minimax problems

An algorithm is presented for the numerical solution of nonlinear programming problems in which the objective function is to be minimized over feasiblex after having been maximized over feasibley. The vectorsx andy are subjected to separate nonlinear constraints. The algorithm is obtained as follows: One starts with an outer algorithm for the minimization overx, that algorithm being taken here to be a method of centers; then, one inserts into this algorithm an adaptive inner procedure, which is designed to compute a suitable approximation to the maximizery in a finite number of steps. The outer and inner algorithms are blended in such a way as to cause the inner one to converge more rapidly. The results on convergence and rate of convergence for the outer algorithm continue to hold (essentially) for the composite algorithm. Thus, what is considered here, for the first time for this type of problem, is the question of how one inserts an approximation procedure into an algorithm so as to preserve its convergence and its rate of convergence.     

Banach空间中有限个增生算子公共零点的迭代强收敛定理

令E为实自反Banach空间具一致Gteaux可微范数,AiE×E(i=1,2,…,k)为增生算子且满足∩ki=1Ai-1(0)≠φ.令C为E的非空闭凸子集并满足■C∩r>0R(I+rAi),i=1,2,…,k.将引入一种带误差项的迭代算法,并证明迭代序列强收敛于{Ai}ki=1的公共零点.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

关于图的导出森林独立系统

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.     

Computing the face lattice of a polytope from its vertex-facet incidences

We give an algorithm that constructs the Hasse diagram of the face lattice of a convex polytope P from its vertex-facet incidences in time O(min{n,m}··), where n is the number of vertices, m is the number of facets, is the number of vertex-facet incidences, and  is the total number of faces of P. This improves results of Fukuda and Rosta [Computational Geometry 4 (4) (1994) 191–198], who described an algorithm for enumerating all faces of a d-polytope in O(min{n,m}·d·²) steps. For simple or simplicial d-polytopes our algorithm can be specialized to run in time O(d··). Furthermore, applications of the algorithm to other atomic lattices are discussed, e.g., to face lattices of oriented matroids.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C，如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G），Vj′∈V（G′）且vivj∈E（G））那么，称D（C）是C的倍图，如果V（D（G））=V（C）∪V（G′），E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G），vj′∈V（G’）and vivj∈（G）），称D（C）是G的补倍图，这里G′是G的拷贝．本文研究了D（G）和D的色数，边色数，欧拉性，哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

二分(0,mf-m+1)-图的正交(0,f)-因子分解

设G=(X,Y,E(G))是一个二分图,分别用V(G)=XUY和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对(A)x∈V(G)有f(x)≥k.设H_1,H_2,…,H_k是G的k个顶点不相交的子图,且|E(H_i)|=m,1≤i≤k.本文证明了每个二分(0,mf-m+1)-图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k).