L∞模下的二维带宽问题

The two-dimensional bandwidth problem is to determine an embedding of graph G in a grid graph in the plane such that the longest edges are as short as possible. In this paper we study the problem under the distance of L∞-norm.     

匹配可扩图的结构

设G是一个有限的简单连通图。D（G）表示V（G）的一个子集，它的每一个点至少有一个最大匹配不覆盖它。A（G）表示V（G）-D（G）的一个子集，它的每一个点至少和D（G）的一个点相邻。最后设C（G）=V（G）-A（G）-D（G）。在这篇章中，下面的被获得。⑴设u∈V（G）。若n≥1和G是n-可扩的，则（a)C(G-u)=φ和A（G-u)∪{u}是一个独立集，（b)G的每个完美匹配包含D（G-u)的每个分支的一个几乎守美匹配，并且它匹配A（G-u)∪{u}的所有点与D（G-4）的不同分支的点。⑵若G是2-可扩的，则对于u∈V（G），A（G-u）∪{u}是G的一个最大障碍且G的最大障碍的个数是2或是│V(G)│.⑶设X=Cay(Q,S),则对于u∈Q,(a)A(X-u)=φ=C（G-u)和X-u是一个因子临界图，或（b)C(X-u)=φ和X的两部是A（X-u)∪{u}和D（X-u)且│A(X-u)∪{u}│=│D(X-u）│。⑷设X=Cay(Q,S),则对于u∈Q，A（X-u)∪{u}是X的一个最大障碍且X的最大障碍的个数是2或是│Q│。     

图的割宽总是的度序列方法

The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges is minimized. This paper presents an approach based on the degree sequence of G for determining the exact value of cutwidth of typical graphs (e. g. , n-cube,cater-pillars). Relations between the cutwidth and other graph-theoretic parameters are studied as well.     

紧急网络中的最小饱和流问题

网络N中的一个流,如果沿前向已无法再增流,则称为饱和流,在交通拥挤或紧急疏散时,网络往往被一饱和流所堵塞。显然,这饱和流的值越小,网络的性能就越差。于是从网络分析的观点就提出最小饱和流问题。本文首先证明此问题NP－困难的。然后给出关于最小饱和流与最大流的关系及算法方面的结果。