共查询到20条相似文献,搜索用时 31 毫秒
1.
Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively,there is no general algorithm of finding a k-partition for a k-connected graph G=(V,E),where k is the vertex connectivity of G.In this paper,an O(k^2n^2) general algorithm of finding a k-partition for a k-connected graph is proposed,where n=|V|. 相似文献
2.
Bertossi A.A. Pinotti C.M. Tan R.B. 《Parallel and Distributed Systems, IEEE Transactions on》2003,14(3):222-235
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相似文献
3.
一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法——三角排序,利用该排序的结果证明了当n=7(mod8)且Cn-1^4/2+2〈m≤Cn ^4/2+2时,梯图Lm≌Pm×P2的点可区别全色数为n。 相似文献
4.
首先研究了任意无向不加权图情况下的极小K点连通扩充算法,在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理.最终推出了任意无向加权图K点连通最小扩充的模拟退火算法. 相似文献
5.
6.
一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同。其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法:三角排序。利用该排序的结果证明了当n≡5(mod8)和C4n-1/2+2〈m≤C4n/2+2时,梯图Lm≌Pm×P2的点可区别全色数为n。 相似文献
7.
图的均匀树[k]-染色是图的一个点[k]-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图[G]具有均匀树[k]-染色的最小整数[k]称为图[G]的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。 相似文献
8.
9.
《国际计算机数学杂志》2012,89(6):689-707
We examine in this work the following graph theory problem that arises in neural computations that involve the learning of boolean expressions by studying the asymptotic connectivity properties of $G_{n\comma 1/\lpar kn\rpar ^{1/2}}$ random graphs, where k is a fixed positive integer. For an undirected graph $G = \lpar V\comma \; E\rpar $ let $N\lpar X\comma \; Y\rpar = \lcub v \in V - \lpar X \cup Y\rpar \!\mid$ $ \exists x \in X\ \hbox{with}\ \lpar v\comma \; x\rpar \in E\rcub $ . For fixed k construct an undirected graph $G = \lpar V\comma \; E\rpar $ such that for all disjoint sets $A\comma \; B \subseteq V$ such that $\vert A \vert = \vert B \vert = k$ , and $C = N\lpar A\comma \; B\rpar \cap N\lpar B\comma \; A\rpar $ , set C is such that $\vert C \vert$ is either exactly k or as close to k as possible. Asymptotic results for large values of k are also presented. 相似文献
10.
11.
一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法:三角排序。利用该排序的结果证明了当n≡4(mod8)和C4n-1/2+2〈m≤C4n/2+2时,梯图Lm■Pm×P2的点可区别全色数为n。 相似文献
12.
图[G]的[s]-均匀边[k]-染色是指用[k]种颜色对图的边进行染色,使得图[G]的每个顶点所关联的任何两种颜色的边的条数至多相差[s]。使得对于每个不小于[k]的整数[t],图[G]都具有[s]-均匀边[t]-染色的最小整数[k]称为图[G]的[s]-均匀边色数阈值。文中证明了外1-平面图的1-均匀边色数阈值最多为5,不含有相邻的3圈的外1-平面图的均匀边色数阈值最多为4,外1-平面图的2-均匀边色数阈值恰好为1。 相似文献
13.
S. J. FARLOW 《International journal of control》2013,86(5):1293-1299
It is shown how a vector control function f(x,t) = (fi(x,t)) can be found that will drive the solution of the linear diffusion system from an arbitrary initial condition u(x,0) = φ(x) = (φi(x), i = 1,2,...,n, to an arbitrary final condition u(x,T) = ψ(x) = (ψi(x)), i = 1,2,...,n, in arbitrary time T. 相似文献
14.
A perturbed system of linear equalitieslangle a_{i},x rangle = b_{i}, i = 1,2,...,n;a_{i} inA_{i};b_{i},inB_{i};xinX (the sets Ai and the intervals Bi prescribed a priori) is said to be robust if a solution vectorx_{0}inX can be found resulting inlangle a_{i},x_{0}rangle in B_{i} for alla_{i} inA_{i} and alli = 1, 2,...,n . A numerical "test for robustness" is developed. This test is seen to involve 2n parameters at most-even when the solution setX is an infinite-dimensional vector space. 相似文献
15.
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$. 相似文献
16.
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$. 相似文献
17.
针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O(n+logn)的结论。 相似文献
18.
设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。 相似文献
19.
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G
have non-negative weights assigned to them. In this problem a {-1,0,1} incidence vector is associated with each cycle and
the vector space over
generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for
its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. This
paper presents an
algorithm, which is the first polynomial-time algorithm for computing a minimum cycle basis in G. We then improve it to
an
algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. In this problem
a {0,1} incidence vector is associated with each cycle and the vector space over
generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has
lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis
in an undirected graph cannot be used as black boxes to solve the problem in directed graphs. 相似文献
20.
张国珍 《计算机工程与应用》2017,53(8):19-22
限制边连通度是度量网络可靠性的重要参数。设[G]是一个边集为[E]的连通网络。称一个边集合[S?E]是一个限制边割,如果[G-S]是不连通的且每个分支至少有两个顶点。网络[G]的限制边连通度,记为[λ'],定义为[G]的最小限制边割的基数。设[d(v)]表示顶点[v]的度,[ξ=min{d(u)+d(v)-2:uv∈E}]表示[G]的最小边度。称网络[G]是极大限制边连通的,如果[λ'=ξ]。给出了网络是极大限制边连通的一些充分条件。 相似文献