共查询到20条相似文献,搜索用时 15 毫秒
1.
LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR
k–1,fVR
k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica
8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n
2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n
0.19; e.g., for
, the factor of improvement is >n
0.62. Both algorithms have processor efficient parallel versions that run inO((logn)2) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn
2/(logn)3 while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph. 相似文献
2.
Theprofile of a hypergraph onn vertices is (f
0, f1, ...,f
n) wheref
i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain
many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton). 相似文献
3.
Let ℱ be a family of subsets of a finite set ofn elements. The vector (f
0, ...,f
n
) is called the profile of ℱ wheref
i
denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF
1⊄F
2 andF
1∩F
2≠0 for allF
1,F
2teℱ. It is proved that the extreme points of this set inR
n+1 have at most two non-zero components.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
4.
For a convex body K
d
we investigate three associated bodies, its intersection body IK (for 0int K), cross-section body CK, and projection body IIK, which satisfy IKCKIIK. Conversely we prove CKconst1(d)I(K–x) for some xint K, and IIKconst2 (d)CK, for certain constants, the first constant being sharp. We estimate the maximal k-volume of sections of 1/2(K+(-K)) with k-planes parallel to a fixed k-plane by the analogous quantity for K; our inequality is, if only k is fixed, sharp. For L
d
a convex body, we take n random segments in L, and consider their Minkowski average D. We prove that, for V(L) fixed, the supremum of V(D) (with also nN arbitrary) is minimal for L an ellipsoid. This result implies the Petty projection inequality about max V((IIM)*), for M
d
a convex body, with V(M) fixed. We compare the volumes of projections of convex bodies and the volumes of the projections of their sections, and, dually, the volumes of sections of convex bodies and the volumes of sections of their circumscribed cylinders. For fixed n, the pth moments of V(D) (1p<) also are minimized, for V(L) fixed, by the ellipsoids. For k=2, the supremum (nN arbitrary) and the pth moment (n fixed) of V(D) are maximized for example by triangles, and, for L centrally symmetric, for example by parallelograms. Last we discuss some examples for cross-section bodies.Research (partially) supported by Hungarian National Foundation for Scientific Research, Grant No. 41. 相似文献
6.
Branko ?urgus 《Discrete Applied Mathematics》2007,155(13):1774-1792
Let S be a finite set with m elements in a real linear space and let JS be a set of m intervals in R. We introduce a convex operator co(S,JS) which generalizes the familiar concepts of the convex hull, , and the affine hull, , of S. We prove that each homothet of that is contained in can be obtained using this operator. A variety of convex subsets of with interesting combinatorial properties can also be obtained. For example, this operator can assign a regular dodecagon to the 4-element set consisting of the vertices and the orthocenter of an equilateral triangle. For two types of families JS we give two different upper bounds for the number of vertices of the polytopes produced as co(S,JS). Our motivation comes from a recent improvement of the well-known Gauss-Lucas theorem. It turns out that a particular convex set co(S,JS) plays a central role in this improvement. 相似文献
7.
W. Mader 《Combinatorica》1985,5(2):161-165
It is shown that there is a digraphD of minimum outdegree 12m and
μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively. 相似文献
8.
We prove that for a measurable subset of S
n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R
2 and R
3.Partially supported by KBN (Poland), Grant No. 2 1094 91 01. 相似文献
9.
We show that there are close relations between extremal problems in dual Brunn-Minkowski theory and isotropic-type properties for some Borel measures on the sphere. The methods we use allow us to obtain similar results in the context of Firey-Brunn-Minkowski theory. We also study reverse inequalities for dual mixed volumes which are related with classical positions, such as ?-position or isotropic position. 相似文献
10.
Properties of pointwise second differentiability of real-valued convex functions in
n
are studied. Some proofs of the Busemann-Feller-Aleksandrov theorem are reviewed and a new proof of this theorem is presented. 相似文献
11.
A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex.
This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347.
This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347
Dedicated to Paul Erdős on his seventieth birthday 相似文献
12.
David Hilbert discovered in 1895 an important metric that is canonically associated to an arbitrary convex domain Ω in the Euclidean (or projective) space. This metric is known to be Finslerian, and the usual proof of this fact assumes a certain degree of smoothness of the boundary of Ω, and refers to a theorem by Busemann and Mayer that produces the norm of a tangent vector from the distance function. In this paper, we develop a new approach for the study of the Hilbert metric where no differentiability is assumed. The approach exhibits the Hilbert metric on a domain as a symmetrization of a natural weak metric, known as the Funk metric. The Funk metric is described as a tautological weak Finsler metric, in which the unit ball in each tangent space is naturally identified with the domain Ω itself. The Hilbert metric is then identified with the reversible tautological weak Finsler structure on Ω, and the unit ball of the Hilbert metric at each point is described as the harmonic symmetrization of the unit ball of the Funk metric. Properties of the Hilbert metric then follow from general properties of harmonic symmetrizations of weak Finsler structures. 相似文献
13.
A.R. Ashrafi M. SaheliM. Ghorbani 《Journal of Computational and Applied Mathematics》2011,235(16):4561-4566
Let G be a molecular graph. The eccentric connectivity index ξc(G) is defined as ξc(G)=∑u∈V(G)degG(u)εG(u), where degG(u) denotes the degree of vertex u and εG(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC4C8(S) nanotube and TC4C8(S) nanotorus are given. 相似文献
14.
Motivated by a conjecture of Steinhaus, we consider the mapping F, associating to each point x of a convex hypersurface the set of all points at maximal intrinsic distance from x. We first provide two large classes of hypersurfaces with the mapping F single-valued and involutive. Afterwards we show that a convex body is smooth and has constant width if its double has the above properties of F, and we prove a partial converse to this result. Additional conditions are given, to characterize the (doubly covered) balls. 相似文献
15.
We show that the shapes of convex bodies containing m translates of a convex body K, so that their Minkowskian surface area is minimum, tends for growing m to a convex body L.Received: 7 January 2002 相似文献
16.
Costin V?lcu 《Mathematische Annalen》2008,340(3):543-567
Various properties are given concerning geodesics on, and distance functions from points in, typical degenerate convex surfaces;
i.e., surfaces obtained by gluing together two isometric copies of typical (in the sense of Baire category) convex bodies,
by identifying the corresponding points of their boundaries. 相似文献
17.
We give cogenerators for the categories of convex (= finitely superconvex), finitely positively convex, and absolute convex (= finitely totally convex) spaces introduced by Pumplün and Röhrl.Dedicated to our academic teacher Dieter Pumplün on the occasion of his sixtieth birthday. 相似文献
18.
This paper is concerned with various geometric averages of sections or projections of convex bodies. In particular, we consider Minkowski and Blaschke sums of sections as well as Minkowski sums of projections. The main result is a Crofton-type formula for Blaschke sums of sections. This is used to establish connections between the different averages mentioned above. As a consequence, we obtain results which show that, in some circumstances, a convex body is determined by the averages of its sections or projections.The research of the first author was supported in part by NSF grants DMS-9504249 and INT-9123373 相似文献
19.
Peter Kohlmann 《Geometriae Dedicata》1996,60(2):125-143
We consider noncompact, closed and convex sets with nonvoid interior in Euclidean space. It is shown that if such a set has one curvature measure sufficiently close to the boundary measure, then it is congruent to a product of a vector space and a compact convex body. Related stability and characterization theorems for orthogonal disc cylinders are proved. Our arguments are based on the Steiner-Schwarz symmetrization processes and generalized Minkowski integral formulas. 相似文献
20.
Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences. 相似文献