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

设G是一个图,f是定义在V(G)上的整数值函数,且对坌x∈V(G),有2k≤f(x),设H1,H2,…,Hk是G的k个顶点不相交的子图,且|E(Hi)|=m,1≤i≤k,证明了每个(0,mf-m+1)图有一个(0,f)因子分解正交于Hi(i=1,2,…,k)。     

基于局部比值法的强弦图带权控制集问题的线性时间算法

一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。     

steiner树问题的近似算法

著名的Steiner树问题是,给定图G=(V、E),QV,在边集E上定义权函数f:E→Z~+,要求在图G上找一子树T=(Y,U),使得QY且 ∑_(c∈U)f(e)达到极小以后,我们称该问题为ST问题,R.M.Karp曾证明ST问题为NP-完全的,本文作者曾提出图上Steiner树问题:在图G=(V,E),QV上,要求一子树T=(Y,     

无向圆盘图中最大r跳独立邻居数的估计

本文考虑无向圆盘图中的最大r-跳独立邻居数(r≥2)。给定一个圆盘图G=(V,E),对任意v?V,用N'(V)表示所有距节点v跳数最多为r的节点集合,则对G中任何一个r-跳独立集I,其在N'(V)内最多有β个节点,■这里K是圆盘图的最大圆盘半径与最小圆盘半径的比值.     

微分几何方法与非线性控制系统（4）

7 非线性控制系统的几何理论 7.1 非线性控制系统的几何描述 定义在R~n上的一般非线性系统可以用微分方程描述如下: x=f(x,4) (7.1a) y=h(x) (7.1b)这里,状态x∈R~n;控制u∈R~m;输出y∈R~r,等式(7.1a)称为状态方程,(7.1b)称为输出方程。为了便于使用微分几何的工具,假设f对x和u都是光滑或解析函数,同样,h(x)也是C~∞     

图上STEINER树问题及其近似算法

1.图上STEINER树问题是NP-完全的 著名的网络上Steiner问题是:对给定图G=(V,E),其中V=PUS,在边集E(G)上定义权函数f:E(G)→Z~ ,构成网络N(G,f)。要求在网络N(G,f)上寻找一棵子树T=(Y,u),使得P(?)Y,且     

两个多色顶点Folkman数的界*

对于正整数a1,a2,…,ar以及无向简单图G, 当且仅当对G的任意一种顶点r着色,都对某个i∈{1,2,…,r}存在顶点都着有颜色i的ai阶的完全子图, 则记G→(a1,a2,…,ar)v。对于k＞max{a1,a2,…,ar},顶点Folkman数定义为Fv(a1,a2,…,ar;k)=min{｜V(G)｜:G→(a1,a2,…,ar)v,KkG}。借助于计算机 得到了18≤Fv(2,2,2,3;4)≤Fv(2,3,3;4)≤30。     

强竞赛图的强连通性

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。     

关于出现网的S切

出现网是研究Petri网的进程的工具,而出现网的S切又是研究进程的重要概念。讨论S切的基本性质：定义并证明S切M在E的元素e的作用下发生的变换M→u[e]=（u-·e）Ue·以及发生变换的条件。定义并证明S切u在E的元素e的反作用下发生的变换v→v[e-1]=（v-e·）U·e以及发生变换的条件;证明对于任意S切u有u[e][e-1]=u,对于任意S切v有v[e-1][e]=v。证明每一个S切u（≠w1）都能够被某一个e作用,每一个S切v（≠W0）都能够被某一个e反作用。     

图的分数[a,b]-因子存在的一个条件

图G的孤立韧度定义为I(G)=min｛｜S｜/i(G-S):S!V(G),i(G-S)≥2｝,若G不是完全图;否则,令I(G)=∞。论文给出了图的分数[a,b]-因子的存在性与图的孤立韧度的关系。证明若δ(G)≥I(G)≥a-1+a/b,则图G有分数[a,b]-因子,其中a相似文献   

Remarks on the L/sup p/-input converging-state property

Let X /spl sub/ /spl Ropf//sup N/ and consider a system x/spl dot/ = f(x,u), f : X /spl times/ /spl Ropf//sup M/ /spl rarr/ /spl Ropf//sup N/, with the property that the associated autonomous system x/spl dot/ = f (x,0) has an asymptotically stable compactum C with region of attraction A. Assume that x is a solution of the former, defined on [0,/spl infin/), corresponding to an input function u. Assume further that, for each compact K /spl sub/ X, there exists k > 0 such that |f(z,v) - f(z,0)| /spl les/ k|v| for all (z,v) /spl isin/ /spl times/ /spl Ropf//sup M/. A simple proof is given of the following L/sup p/-input converging-state property: if u /spl isin/ L/sup p/ for some p /spl isin/ [1,/spl infin/) and x has an /spl omega/-limit point in A, then x approaches C.     

极大限制边连通网络的充分条件

限制边连通度是度量网络可靠性的重要参数。设[G]是一个边集为[E]的连通网络。称一个边集合[S?E]是一个限制边割,如果[G-S]是不连通的且每个分支至少有两个顶点。网络[G]的限制边连通度,记为[λ'],定义为[G]的最小限制边割的基数。设[d(v)]表示顶点[v]的度,[ξ=min{d(u)+d(v)-2:uv∈E}]表示[G]的最小边度。称网络[G]是极大限制边连通的,如果[λ'=ξ]。给出了网络是极大限制边连通的一些充分条件。     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

Channel assignment with separation for interference avoidance in wireless networks

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1相似文献   

Testing list <Emphasis Type="Italic">H</Emphasis>-homomorphisms

In the List H- Homomorphism Problem, for a graph H that is a parameter of the problem, an instance consists of an undirected graph G with a list constraint \({L(v) \subseteq V(H)}\) for each variable \({v \in V(G)}\), and the objective is to determine whether there is a list H-homomorphism \({f:V(G) \to V(H)}\), that is, \({f(v) \in L(v)}\) for every \({v \in V(G)}\) and \({(f(u),f(v)) \in E(H)}\) whenever \({(u,v) \in E(G)}\).We consider the problem of testing list H-homomorphisms in the following weighted setting: An instance consists of an undirected graph G, list constraints L, weights imposed on the vertices of G, and a map \({f:V(G) \to V(H)}\) given as an oracle access. The objective is to determine whether f is a list H-homomorphism or far from any list H-homomorphism. The farness is measured by the total weight of vertices \({v \in V(G)}\) for which f(v) must be changed so as to make f a list H-homomorphism. In this paper, we classify graphs H with respect to the number of queries to f required to test the list H-homomorphisms. Specifically, we show that (i) list H-homomorphisms are testable with a constant number of queries if and only if H is a reflexive complete graph or an irreflexive complete bipartite graph and (ii) list H-homomorphisms are testable with a sublinear number of queries if and only if H is a bi-arc graph.     

无线网络邻近图综述

网络拓扑结构可由邻近图表述,定义其为一个包含点集V和边集E的图,某有向边(u,v)属于该图当且仅当点v位于点u的邻城内,这个邻域是在某事先定义的邻近测度作用下产生的.回顾了迄今为止一些重要图结构,内容主要集中在5个方面,包括邻近图的定义或概念、构造算法、图例、隶属关系、拓扑参数,还谈到进一步的研究方向.     

L 2-Error bounds for approximate solutions of elliptic partial differential equations with Dirichlet-boundary conditions

New a posteriori (computable) upper bounds for theL ₂-norms, both ofD(u?v) and ofu?v are proposed, whereu is the exact solution of the boundary value problem $$Au: = - D(pDu) + qu = f, x \in G and u = 0,x \in \partial G$$ andv any approximation of it (D is here the vector of partial derivatives with respect to the components ofx). It is shown that the new error bounds are better than the classical one, which is proportional to ‖Av?f‖, in many cases. This happens, e. g., ifq has some zero point inG, as in the case of a Poisson equation.     

Constructing edge-disjoint spanning trees in product networks

A Cartesian product network is obtained by applying the cross operation on two graphs. We study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G=(V/sub G/, E/sub G/) be a graph having n/sub 1/ EDSTs and F=(V/sub F/, E/sub F/) be a graph having n/sub 2/ EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G/spl times/F. The graph G has t/sub 1/=|E/sub G/|/spl middot/n/sub 1/(|V/sub G/|-1) more edges than that are necessary for constructing n/sub 1/ EDSTs in it, and the graph F has t2=|E/sub F/'-n/sub 2/(|V/sub F/|-1) more edges than that are necessary for constructing n/sub 2/ EDSTs in it. By assuming that t/sub 1//spl ges/n/sub 1/ and t/sub 2//spl ges/n/sub 2/, our first construction shows that n/sub 1/+n/sub 2/ EDSTS can be constructed in G/spl times/F. Our second construction does not need any assumption and it constructs n/sub 1/+n/sub 2/-1 EDSTs in G/spl times/F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.