共查询到20条相似文献,搜索用时 46 毫秒
1.
AN INVARIANT FOR HYPERGRAPHS 总被引:11,自引:0,他引:11
ANINVARIANTFORHYPERGRAPHSWANGJIANFANG(InstituteofAPPliedMathematics,ChineseAcademyofSciences,Beijing100080,ChinaandAsia-Pacif... 相似文献
2.
Paths and cycles of hypergraphs 总被引:1,自引:0,他引:1
Hypergraphs are the most general structures in discrete mathematics. Acyclic hypergraphs have been proved very useful in relational
databases. New systems of axioms for paths, connectivity and cycles of hypergraphs are constructed. The systems suit the structure
properties of relational databases. The concepts of pseudo cycles and essential cycles of hypergraphs are introduced. They
are relative to each other. Whether a family of cycles of a hypergraph is dependent or independent is defined. An enumeration
formula for the maximum number of independent essential cycles of a hypergraph is given. 相似文献
3.
Enumeration of Maximum Acyclic Hypergraphs 总被引:1,自引:0,他引:1
Jian-fang Wang Hai-zhu LiInstitute of Applied Mathematics Academy of Mathematics System Sciences Chinese Academy of Sciences Beijing China 《应用数学学报(英文版)》2002,18(2):215-218
Abstract Acyclic hypergraphs are analogues of forests in graphs.They are very useful in the design ofdatabases. In this article,the maximum size of an acvclic hypergraph is determined and the number of maximumγ-uniform acyclic hypergraphs of order n is shown to be (_(r-1)~n)(n(r-1)-r~2 2r)~(n-r-1). 相似文献
4.
5.
郑国彪 《纯粹数学与应用数学》2012,28(3):294-302
混合超图的上、下色数的研究是超图研究中一个重要的话题.由于超图本身结构上的复杂性,近年来对超图色性的研究也近局限于对一些特殊图类的研究,其中完全一致混合超图是最为热门的图类之一.给出了D完全(C不完全)一致混合超图的概念,并运用组合数学中有关分划的思想和方法对该图类的色性进行了进一步的研究,对相关文献中给出的结论进行了推广,得到了一个较为一般化的结论.并在该定理的证明中得到并证明了一个关于混合超图C稳定集的重要论断,对超图色性研究有着重要的意义. 相似文献
6.
Christopher Kusch Juanjo Ru Christoph Spiegel Tibor Szab 《Random Structures and Algorithms》2019,55(2):371-401
Biased Maker‐Breaker games, introduced by Chvátal and Erd?s, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container‐type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H‐building games studied by Bednarska and ?uczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game‐theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging. 相似文献
7.
A hypergraph is a generalization of a graph where edges can connect any number of vertices. In this paper, we extend the study of locating-dominating sets to hypergraphs. Along with some basic results, sharp bounds for the location-domination number of hypergraphs in general and exact values with specified conditions are investigated. Moreover, locating-dominating sets in some specific hypergraphs are found. 相似文献
8.
A recently introduced graph-theoretic notion of signed hypergraph is studied. In particular, a structural characterization of balanced signed hypergraphs is given, and two optimization problems related to the balance property — the maximum balance and the minimum covering problems — are introduced and characterized. It is shown that both problems are NP-complete in general. Applications of the theory of signed hypergraphs to two VLSI optimization problems, namely via minimization and constrained logic encoding, are described. 相似文献
9.
1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的. 相似文献
10.
We present some reoptimization techniques for computing (shortest) hyperpath weights in a directed hypergraph. These techniques are exploited to improve the worst-case computational complexity (as well as the practical performance) of an algorithm finding the K shortest hyperpaths in acyclic hypergraphs. 相似文献
11.
We explore connections between the generalized multiplicities of square-free monomial ideals and the combinatorial structure of the underlying hypergraphs using methods of commutative algebra and polyhedral geometry. For instance, we show that the j-multiplicity is multiplicative over the connected components of a hypergraph, and we explicitly relate the j-multiplicity of the edge ideal of a properly connected uniform hypergraph to the Hilbert–Samuel multiplicity of its special fiber ring. In addition, we provide general bounds for the generalized multiplicities of the edge ideals and compute these invariants for classes of uniform hypergraphs. 相似文献
12.
13.
超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果. 相似文献
14.
《European Journal of Operational Research》2006,175(2):1164-1179
Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best deterministic Markov policies. That is, we are interested in ranking the first K deterministic Markov policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria. 相似文献
15.
A surprising diversity of different products of hypergraphs have been discussed in the literature. Most of the hypergraph
products can be viewed as generalizations of one of the four standard graph products. The most widely studied variant, the
so-called square product, does not have this property, however. Here we survey the literature on hypergraph products with
an emphasis on comparing the alternative generalizations of graph products and the relationships among them. In this context
the so-called 2-sections and L2-sections are considered. These constructions are closely linked to related colored graph structures
that seem to be a useful tool for the prime factor decompositions w.r.t. specific hypergraph products. We summarize the current
knowledge on the propagation of hypergraph invariants under the different hypergraph multiplications. While the overwhelming
majority of the material concerns finite (undirected) hypergraphs, the survey also covers a summary of the few results on
products of infinite and directed hypergraphs. 相似文献
16.
A supertree is a connected and acyclic hypergraph. For a hypergraph H, the maximal modulus of the eigenvalues of its adjacency tensor is called the spectral radius of H. By applying the operation of moving edges on hypergraphs and the weighted incidence matrix method, we determine the ninth and the tenth k-uniform supertrees with the largest spectral radii among all k-uniform supertrees on n vertices, which extends the known result. 相似文献
17.
B. D. Acharya 《Mathematics in Computer Science》2011,5(1):3-6
A hypergraph-property P is supra-hereditary if whenever a hypergraph H has property P and K is a hypergraph generated by a nonempty subset A of X(H), then K also has the property P. In this paper we give a characterization of irreducible supra-hereditary hypergraphs thereby doubly extending a similar
result in graph theory. Hence, we raise some fundamental questions in hypergraph theory. 相似文献
18.
《Discrete Mathematics》2020,343(6):111853
A planar support for a hypergraph is a planar graph that captures the structural properties of the hypergraph. In this paper, we show, using elementary techniques, that a wide class of geometric hypergraphs of planar non-piercing regions admit a planar support. We also discuss some direct consequences of our results. 相似文献
19.
C.T.J. Dodson 《Fuzzy Sets and Systems》1981,6(3):293-308
The generalisation from graph theory to hypergraph theory can be formulated categorically. This paper shows that hypergraphs are more or less hazy manifolds, which themselves are a particular kind of hazy space. Thus, the category Haz of hazy spaces contains the category Hph of hypergraphs which itself contains the category Gph of graphs. Various induced and coinduced structures are investigated in these categories and some analytic properties are traced through the generalisations. 相似文献