共查询到19条相似文献,搜索用时 127 毫秒
1.
本文的研究方法主要是将模糊拟阵问题转化为普通拟阵问题来研究的方法。本文首先建立独立子集套概念,并使用这个概念和独立集函数概念构建了闭模糊拟阵的充要条件和模糊独立集的充要条件;然后,本文仔细分析了模糊基的性质,找到了一个使用独立子集套和独立集函数来描述的模糊基的充要条件;最后,利用模糊基的这个充要条件提出并证明了闭正规模糊拟阵的充要条件。 相似文献
2.
陈礴 《高校应用数学学报(A辑)》1989,4(3):319-326
针对一类比两个拟阵交更广泛的独立系统——交拟阵,本文探讨了它的某些性质;证明了:任一交拟阵是(2,2)-系统。从而,初步解决了如何在多项式时间内找到一给定交拟阵的最大独立集问题。 相似文献
3.
本文主要方法是通过基本序列、导出拟阵序列和模糊集分解定理,将模糊圈的研究转化为对圈子集套和数组的研究。在闭模糊拟阵中,我们得出三个结论:以同一集合为支撑集的模糊圈的最大模糊圈总是存在;以同一子集串为圈子集套的模糊圈的最大模糊圈不一定存在。但是,找到了存在最大模糊圈的充要条件;以同一集合为支撑集的模糊圈的最小模糊圈,以同一子集串为圈子集套的模糊圈的最小模糊圈都是不存在的。但它们的最小模糊势是存在的,而且找出了计算最小模糊势的公式。我们构造了两个算法:一是构造支撑集最大模糊圈算法。通过这个算法可构造出支撑集最大模糊圈,同时计算出其最大模糊势;二是判断和构造圈子集套最大模糊圈算法。通过这个算法首先判断最大模糊圈是否存在,如果存在就可以找出圈子集套最大模糊圈同时计算出最大模糊势。 相似文献
4.
5.
任意基数集上的拟阵之单扩张 总被引:1,自引:1,他引:1
对于由Betten和Wenzel于2003年提出的任意基数集上的拟阵其相应的秩公理给予了证明,并将此结果用于研究任意基数集上的拟阵的单扩张问题. 相似文献
6.
7.
8.
9.
10.
研究了闭正则模糊拟阵的子拟阵的正则性等性质.得到了闭正则模糊拟阵的两种子拟阵的正则性等性质,即k-子拟阵为闭正则模糊拟阵,限制子拟阵不是闭正则模糊拟阵,给出了闭正则模糊拟阵的收缩拟阵为闭正则模糊拟阵等结论. 相似文献
11.
12.
13.
Marc Demange 《Computational Optimization and Applications》1999,14(1):157-169
We consider the polynomial approximation behavior of the problem of finding, in a graph with weighted vertices, a maximal independent set minimizing the sum of the weights. In the spirit of a work of Halldórson dealing with the unweighted case, we extend it and perform approximation hardness results by using a reduction from the minimum coloring problem. In particular, a consequence of our main result is that there does not exist any polynomial time algorithm approximating this problem within a ratio independent of the weights, unless P = NP. We bring also to the fore a very simple ratio guaranteed by every algorithm while no polynomial time algorithm can guarantee the ratio (1 – ). The known hardness results for the unweighted case can be deduced. We finally discuss approximation results for both weighted and unweighted cases: we perform an approximation ratio that is valid for any algorithm for the former and propose an analysis of a greedy algorithm for the latter. 相似文献
14.
对一些基本的不等式进行了推广,给出了含有n个无关变元的非线性的离散不等式.所得结果推广了已有的一些结论. 相似文献
15.
In this paper, we define GG-E-convexity and GG-E-concavity. We also establish some inequalities in relation to GG-E-convex function using various integral inequalities with enough examples of various categories, which verifies our results. 相似文献
16.
We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as . The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 565–586, 2017 相似文献
17.
We prove that the existence of a polynomial time-approximation algorithm (where < 1 is a fixed constant)for a class of independent set problems, leads to a polynomial timeapproximation algorithm with approximation ratio strictly smallerthan 2 for vertex covering, while the non-existence of such analgorithm induces a lower bound on the ratio of every polynomialtime approximation algorithm for vertex covering. We also prove asimilar result for a (maximization) convex programming problemincluding quadratic programming as subproblem. 相似文献
18.
主要研究了具有两个独立变量的不连续函数(有跳跃间断点)的一类更为广泛的新型积分不等式(Wendroff型),得出了一些新的结论,从而推广了前人的工作. 相似文献
19.
Galvin showed that for all fixed δ and sufficiently large n, the n‐vertex graph with minimum degree δ that admits the most independent sets is the complete bipartite graph . He conjectured that except perhaps for some small values of t, the same graph yields the maximum count of independent sets of size t for each possible t. Evidence for this conjecture was recently provided by Alexander, Cutler, and Mink, who showed that for all triples with , no n‐vertex bipartite graph with minimum degree δ admits more independent sets of size t than . Here, we make further progress. We show that for all triples with and , no n‐vertex graph with minimum degree δ admits more independent sets of size t than , and we obtain the same conclusion for and . Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree δ whose minimum degree drops on deletion of an edge or a vertex. 相似文献