共查询到20条相似文献,搜索用时 140 毫秒
1.
2.
3.
4.
5.
6.
Baker和Nuttle提出了下述单可变资源排序问题:$n$个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng 和 Ng 证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的. 相似文献
7.
研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较. 相似文献
8.
9.
假设G=(V,E,F)是一个平面图。如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻。图G的一个弱完备k-染色是指存在一个从V ∪ E ∪ F到k色集合{1, …, K}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及V ∪ E ∪ F中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成χ vef(G)。2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。 相似文献
10.
Baker和Nuttle提出了下述单可变资源排序问题:扎个工件利用某个单资源进行加工使得工件的完工时间的某个函数达到最小,而资源的可利用率是随着时间而变化的.当最小化的目标函数是工件的加权完工时间和时,Baker和Nuttle猜测该问题是NP-困难的.最近,Yuan、Cheng和Ng证明该问题在一般意义下是NP-困难的,但是问题的精确复杂性仍然是悬而未决的.本文我们证明了该问题是强NP-困难的. 相似文献
11.
Norbert Polat 《Discrete Mathematics》1995,140(1-3):119-127
A (finite or infinite) graph G is strongly dismantlable if its vertices can be linearly ordered x0,…, x so that, for each ordinal β < , there exists a strictly increasing finite sequence (ij)0 j n of ordinals such that i0 = β, in = and xij+1 is adjacent with xij and with all neighbors of xij in the subgraph ofG induced by {xy: β γ }. We show that the Helly number for the geodesic convexity of such a graph equals its clique number. This generalizes a result of Bandelt and Mulder (1990) for dismantlable graphs. We also get an analogous equality dealing with infinite families of convex sets. 相似文献
12.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph Jk(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of Jk(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J2(G) is planar are determined. 相似文献
13.
Georg Heinig 《Linear algebra and its applications》2002,340(1-3):1-13
The structure of the kernel of block Toeplitz-plus-Hankel matrices R=[aj−k+bj+k], where aj and bj are the given p×q blocks with entries from a given field, is investigated. It is shown that R corresponds to two systems of at most p+q vector polynomials from which a basis of the kernel of R and all other Toeplitz-plus-Hankel matrices with the same parameters aj and bj can be built. The main result is an analogue of a known kernel structure theorem for block Toeplitz and block Hankel matrices. 相似文献
14.
Let S be a compact, weak self-similar perfect set based on a system of weak contractions fj, j=1,…,m each of which is characterized by a variable contraction coefficient j(l) as d(fj(x),fj(y)) j(l)d(x,y), d(x,y)<l, l>0. If the relation ∑mj=1j(l0)<1 holds at at least one point l0, then every nonempty compact metric space is a continuous image of the set S. 相似文献
15.
Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals
下载免费PDF全文
![点击此处可从《数学学报(英文版)》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I. 相似文献
16.
Avram Sidi 《Linear algebra and its applications》1998,280(2-3):129-162
In this paper we propose a general approach by which eigenvalues with a special property of a given matrix A can be obtained. In this approach we first determine a scalar function ψ: C → C whose modulus is maximized by the eigenvalues that have the special property. Next, we compute the generalized power iterations uinj + 1 = ψ(A)uj, j = 0, 1,…, where u0 is an arbitrary initial vector. Finally, we apply known Krylov subspace methods, such as the Arnoldi and Lanczos methods, to the vector un for some sufficiently large n. We can also apply the simultaneous iteration method to the subspace span{x(n)1,…,x(n)k} with some sufficiently large n, where x(j+1)m = ψ(A)x(j)m, j = 0, 1,…, m = 1,…, k. In all cases the resulting Ritz pairs are approximations to the eigenpairs of A with the special property. We provide a rather thorough convergence analysis of the approach involving all three methods as n → ∞ for the case in which A is a normal matrix. We also discuss the connections and similarities of our approach with the existing methods and approaches in the literature. 相似文献
17.
For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices xo and xp in any color class there exist vertices x1, x2, …, xp-1 of the same class with dist(xi, xi+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.
We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1. 相似文献
18.
Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |NG(x1)NG(x2)NG(xk)|an/(a+b) for any independent subset {x1,x2,…,xk} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense. 相似文献
19.
Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal IΔ in the polynomial ring A = k[x1, …, xn], and its quotient k[Δ] = A/IΔ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dimk ToriA (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ*. As corollaries, we prove that IΔ has a linear resolution as A-module if and only if Δ* is Cohen-Macaulay over k, and show how to compute the Betti numbers dimk ToriA (k[Δ],k) in some cases where Δ* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed. 相似文献
20.
A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label |f(u)−f(v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…,k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if vi denotes the number of vertices labeled i and ei denotes the number of edges labeled i, we require |vi−vj|1 and |ei−ej|1 for every i,j in {0,1,2,…,k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable. 相似文献