共查询到19条相似文献,搜索用时 109 毫秒
1.
研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界. 相似文献
2.
3.
超图聚类方法是目前主流聚类方法之一.它的经典版本出现在超大规模集成电路研究领域.近年来,它的各种改进版本被提出并广泛应用于机器视觉领域.例如,在图像聚类和运动分割方面,它的各种版本常有较好的表现.本文将超图聚类方法引入文本聚类领域.首先,根据文本数据高度稀疏的特点,采用SVD(或PCA)对其进行降维;其次,采用基于大超边的超图规范割聚类对文本的低维投影进行聚类;最后,采用聚类准确率指标对聚类进行评价.在两个文本数据集的实验中,基于超图规范割聚类取得了比传统的k均值聚类和层次聚类更好的聚类表现. 相似文献
4.
5.
1980年,M.Hegde和M.R.Sridharan沿用R.C.Read的计数方法,得到了标号偶有向图和偶超图的计数公式。我们推广了[1]的结果,得到了恰有2k个奇度点的p阶有向图和(p,q)有向图,恰有k个奇度点的p阶超图和(p,q)超图的计数式。本文所讨论的图均指标号图。 相似文献
6.
7.
郑国彪 《纯粹数学与应用数学》2012,28(3):294-302
混合超图的上、下色数的研究是超图研究中一个重要的话题.由于超图本身结构上的复杂性,近年来对超图色性的研究也近局限于对一些特殊图类的研究,其中完全一致混合超图是最为热门的图类之一.给出了D完全(C不完全)一致混合超图的概念,并运用组合数学中有关分划的思想和方法对该图类的色性进行了进一步的研究,对相关文献中给出的结论进行了推广,得到了一个较为一般化的结论.并在该定理的证明中得到并证明了一个关于混合超图C稳定集的重要论断,对超图色性研究有着重要的意义. 相似文献
8.
利用张量理论研究一致超图的谱半径.首先,利用对角相似张量与原张量同谱的性质,结合张量特征值的圆盘定理,给出谱半径的上界,这一上界严格小于最大度;其次,通过超图的度向量给出谱半径的下界.改进了超图谱半径上下界的原有结果. 相似文献
9.
基于王建方和李东给出的超图哈密顿圈的定义和Katona-Kierstead给出的超图哈密顿链的定义,近年来,国内外学者对一致超图的哈密顿圈分解的研究有一系列结果.特别是Bailey-Stevens和Meszka-Rosa研究了完全3-一致超图K_n~((3))的哈密顿圈分解,得到了n=6k+1,6k+2(k=1,2,3,4,5)的哈密顿圈分解.本文在吉日木图提出的边划分方法的基础上继续研究,得到了完全3-一致超图K_n~((3))的哈密顿圈分解的算法,由此得到了n=6k+2,6k+4(k=1,2,3,4,5,6,7),n=6k+5(k=1,2,3,4,5,6)时的圈分解.这一结果将Meszka-Rosa关于K_n~((3))的哈密顿圈分解结果从n≤32提高到了n≤46(n≠43). 相似文献
10.
1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的. 相似文献
11.
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. 相似文献
12.
J.A. Rodríguez 《Applied Mathematics Letters》2009,22(6):916-921
We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on partition problems in hypergraphs which are computationally difficult to solve (NP-hard or NP-complete). Therefore it is very important to obtain nontrivial bounds. More precisely, the following parameters are bounded in the paper: bipartition width, averaged minimal cut, isoperimetric number, max-cut, independence number and domination number. 相似文献
13.
Chunfeng Cui Ziyan Luo Liqun Qi Hong Yan 《Numerical Linear Algebra with Applications》2023,30(2):e2468
The analytic connectivity (AC), defined via solving a series of constrained polynomial optimization problems, serves as a measure of connectivity in hypergraphs. How to compute such a quantity efficiently is important in practice and of theoretical challenge as well due to the non-convex and combinatorial features in its definition. In this article, we first perform a careful analysis of several widely used structured hypergraphs in terms of their properties and heuristic upper bounds of ACs. We then present an affine-scaling method to compute some upper bounds of ACs for uniform hypergraphs. To testify the tightness of the obtained upper bounds, two possible approaches via the Pólya theorem and semidefinite programming respectively are also proposed to verify the lower bounds generated by the obtained upper bounds minus a small gap. Numerical experiments on synthetic datasets are reported to demonstrate the efficiency of our proposed method. Further, we apply our method in hypergraphs constructed from social networks and text analysis to detect the network connectivity and rank the keywords, respectively. 相似文献
14.
The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002 相似文献
15.
Given a hypergraph, a partition of its vertex set, and a nonnegative integer k, find a minimum number of graph edges to be added between different members of the partition in order to make the hypergraph k‐edge‐connected. This problem is a common generalization of the following two problems: edge‐connectivity augmentation of graphs with partition constraints (J. Bang‐Jensen, H. Gabow, T. Jordán, Z. Szigeti, SIAM J Discrete Math 12(2) (1999), 160–207) and edge‐connectivity augmentation of hypergraphs by adding graph edges (J. Bang‐Jensen, B. Jackson, Math Program 84(3) (1999), 467–481). We give a min–max theorem for this problem, which implies the corresponding results on the above‐mentioned problems, and our proof yields a polynomial algorithm to find the desired set of edges. 相似文献
16.
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. 相似文献
17.
Mekkia Kouider 《Discrete Mathematics》2006,306(7):617-623
In this paper we obtain some upper bounds for the b-chromatic number of K1,s-free graphs, graphs with given minimum clique partition and bipartite graphs. These bounds are given in terms of either the clique number or the chromatic number of a graph or the biclique number for a bipartite graph. We show that all the bounds are tight. 相似文献
18.
图的最大亏格与图的顶点划分 总被引:7,自引:0,他引:7
本文研究了图的Betti亏数与图的顶点划分的导出子图之间的关系,得到了图的最大亏格上界由其顶点划分的导出子图所表达的关系式,由此给出了图的最大亏格的一些新结果. 相似文献
19.
The adjacency matrices for graphs are generalized to the adjacency tensors for uniform hypergraphs, and some fundamental properties for the adjacency tensor and its Z-eigenvalues of a uniform hypergraph are obtained. In particular, some bounds on the smallest and the largest Z-eigenvalues of the adjacency tensors for uniform hypergraphs are presented. 相似文献