首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 78 毫秒
1.
Let G = (V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1- p, let mp(G) be the minimum of qe(V1) +pe(V2) over partitions V = V1V2, where e(Vi) denotes the number of edges spanned by Vi. We show that if mp(G) = pqm-δ, then there exists a bipartition V1, V2 of G such that e(V1) ≤ p2m - δ + pm/2 + o(√m) and e(V2) ≤ q2m - δ + qm/2 + o(√m) for δ = o(m2/3). This is sharp for complete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) = (1 - 1/k)m + α, then G admits a k-partition such that each vertex class spans at most m/k2 - Ω(m/k7.5) edges for α = Ω(m/k6). Both of the above improve the results of Bollobás and Scott.  相似文献   

2.
It is shown that for fixed 1 r s < d and > 0, if X PG(d, q) contains (1 + )qs points, then the number of r-flats spanned by X is at least c()q(r+1)(s+1−r), i.e. a positive fraction of the number of r-flats in PG(s + 1,q).  相似文献   

3.
In this paper, we propose and analyze two kinds of novel and symmetric energy-preserving formulae for the nonlinear oscillatory Hamiltonian system of second-order differential equations Aq"(t)+ Bq(t)=f(q(t)), where A ∈ Rm×m is a symmetric positive definite matrix, B ∈ Rm×m is a symmetric positive semi-definite matrix that implicitly contains the main frequencies of the problem and f(q)=-▽qV(q) for a real-valued function V(q). The energy-preserving formulae can exactly preserve the Hamiltonian H(q', q)=(1)/2q'τ Aq' + (1)/2qτ Bq + V(q). We analyze the properties of energy-preserving and convergence of the derived energy-preserving formula and obtain new efficient energy-preserving integrators for practical computation. Numerical experiments are carried out to show the efficiency of the new methods by the nonlinear Hamiltonian systems.  相似文献   

4.
Let p be an odd prime and q = 2(p-1).Up to total degree t-s max{(5p~3+ 6p~2+ 6 p +4)q-10,p~4q},the generators of H~(s,t)(U(L)),the cohomology of the universal enveloping algebra of a bigraded Lie algebra L,are determined and their convergence is also verified.Furthermore our results reveal that this cohomology satisfies an analogous Poinare duality property.This largely generalizes an earlier classical results due to J.P.May.  相似文献   

5.
The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log2 n) space. For the static case, the query time is O(log2 n log log n + K). The dynamic case is supported in O(log3 n + K) query time using O(log3 n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log2d-2 n log log n + K) for the static case and O(log2d-1 n + K) for the dynamic case. The space used is O(n> log2d-2 n) and the amortized time for an update is O(log2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log2d n + K) query time, O(log2d n) time for an insertion and O(log2d-1 n) time for a deletion.  相似文献   

6.
Let q(x) L2(D), D R3 is a bounded domain, q = 0 outside D, q is real-valued. Assume that A(\Gj;\t';,\Gj;,k) A(\Gj;\t';,\Gj), the scattering amplitude, is known for all \Gj;|t',\Gj; S2, S2 is the unit sphere, an d a fixed k \r>0. These data determine q(x) uniquely and a numerical method is given for computing q(x).  相似文献   

7.
We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1−t*)r, where t*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τr,n lets approximately t*n arrivals go by and then stops ‘almost immediately’, in the sense that τr,n/nt* in probability as n→∞, r→∞  相似文献   

8.
In 2006, Sullivan stated the conjectures:(1) every oriented graph has a vertex x such that d~(++)(x) ≥ d~-(x);(2) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 d~-(x);(3) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 · min{d~+(x), d~-(x)}. A vertex x in D satisfying Conjecture(i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx("or" is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasitransitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.  相似文献   

9.
Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog3n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n2) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n2) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.  相似文献   

10.
We prove that for any integer n in the interval there is a maximal partial spread of size n in PG (3, q) where q is odd and q7. We also prove that there are maximal partial spreads of size (q2+3)/2 when gcd(q+1,24)=2 or 4 and of size (q2+5)/2 when gcd(q+1,24)=4.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号