共查询到20条相似文献,搜索用时 78 毫秒
1.
2.
广义图K(n,m)的全色数 总被引:1,自引:0,他引:1
1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的. 相似文献
3.
本刊2002年第3期,载有钱元石老师编制的11~2辐射母子方阵图和连环母子方阵图,造诣颇深,令人敬佩。 方阵图又叫纵横图,也有叫魔方图或幻方图的。它不仅是有趣的智力游戏,而且在图论、电子计算机、实验设计和工艺美术等方面有着广泛的应用。 相似文献
4.
无K4—图子式的图的谱半径 总被引:1,自引:0,他引:1
G是一个无K4-图子式、顶点数为n的简单图,ρ(G)是图G的谱半径。本文得出一个关于ρ(G)的上解界。ρ(G)≤1/2 √2n-15/4。等式成立当且仅当G≌K2倒△(n-2)K1,其中G1倒△G2是由G1∪G2组成,并且G1中的第一个点和G2中的每一个点之间都有一定边相连:(n-2)K1表示(n-2)个孤立点的集合。 相似文献
5.
图论中的图表示"二元关系",以拓扑图形来描述,点代表事物,边代表事物之间的联系.若图为平面图,则尚有第三个量,即区.本文把点、边和区这三个量视作变量,从图的"二元关系"的含义视边数的因变量,视点数和区数为自变量,"二元关系"即转化为函数关系,由此图的某些特性即寓于函数之中.文中将一些图的不同的关系以相应的函数来表达,又以函数的几何图形(数列)来表示,并对它们的特性进行了分析和讨论. 相似文献
6.
双圈图按谱半径的排序 总被引:1,自引:0,他引:1
一个n阶简单连通图G被称为双圈图,如果它的边数是n+1.记B(n)是n阶双圈图的全体.本文确定了B(n)(n≥20)中谱半径的第六大至第十大值和对应的图. 相似文献
7.
8.
现实中,过程参数常常未知,需由第Ⅰ阶段的受控样本数据估计得到.不同的第Ⅰ阶段样本数据集对应着目标参数的不同估计值,进而会导致不同的控制限与不同的控制图表现.对于某位实际工作人员而言,最可能的情况是他手里仅有一组第Ⅰ阶段数据集,因此研究在给定一组第Ⅰ阶段数据集下控制图的表现,即条件表现,更具实际意义.基于Monter Carlo模拟,研究了基于样本平均极差,样本平均标准差和样本合并标准差等3种参数估计形式下常见的等尾极差图和无偏极差图的条件平均链长分布,结果表明参数估计对控制图影响严重.为了弥补第Ⅰ阶段数据量的不足,基于bootstrap方法,提出了修正控制图以获得理想的条件受控表现.比较结果显示,基于样本合并标准差的估计方法更好,修正的无偏极差图表现优于相应的修正等尾极差图. 相似文献
9.
10.
11.
W. R. Pulleyblank 《Mathematical Programming》1979,17(1):91-103
The problem of finding a minimum cardinality set of nodes in a graph which meet every edge is of considerable theoretical as well as practical interest. Because of the difficulty of this problem, a linear relaxation of an integer programming model is sometimes used as a heuristic. In fact Nemhauser and Trotter showed that any variables which receive integer values in an optimal solution to the relaxation can retain the same values in an optimal solution to the integer program. We define 2-bicritical graphs and give several characterizations of them. One characterization is that they are precisely the graphs for which an optimal solution to the linear relaxation will have no integer valued variables. Then we show that almost all graphs are 2-bicritical and hence the linear relaxation almost never helps for large random graphs.This research was supported in part by the National Research Council of Canada. 相似文献
12.
图的最大亏格与图的顶点划分 总被引:7,自引:0,他引:7
本文研究了图的Betti亏数与图的顶点划分的导出子图之间的关系,得到了图的最大亏格上界由其顶点划分的导出子图所表达的关系式,由此给出了图的最大亏格的一些新结果. 相似文献
13.
We define a graph structure associated in a natural way to finite fields that nevertheless distinguishes between different models of isomorphic fields. Certain basic notions in finite field theory have interpretations in terms of standard graph properties. We show that the graphs are connected and provide an estimate of their diameter. An accidental graph isomorphism is uncovered and proved. The smallest non-trivial Laplace eigenvalue is given some attention, in particular for a specific family of 8-regular graphs showing that it is not an expander. We introduce a regular covering graph and show that it is connected if and only if the root is primitive. 相似文献
14.
结合边连通性,本文给出了一个图的Betti亏数由这个图的补图的着色数所确定的上界式,证明了所给出的上界式是最好的,得到关于图的最大亏格下界的若干新结果. 相似文献
15.
Ira M. Gessel 《Journal of Combinatorial Theory, Series A》2011,118(2):591-612
Point-determining graphs are graphs in which no two vertices have the same neighborhoods, co-point-determining graphs are those whose complements are point-determining, and bi-point-determining graphs are those both point-determining and co-point-determining. Bicolored point-determining graphs are point-determining graphs whose vertices are properly colored with white and black. We use the combinatorial theory of species to enumerate these graphs as well as the connected cases. 相似文献
16.
G. Palubeckis 《Journal of Global Optimization》1999,15(2):127-156
In this paper we consider the rectilinear version of the quadratic assignment problem (QAP). We define a class of edge-weighted graphs with nonnegatively valued bisections. For one important type of such graphs we provide a characterization of point sets on the plane for which the optimal value of the related QAP is zero. These graphs are used in the algorithms for generating rectilinear QAP instances with known provably optimal solutions. The basic algorithm of such type uses only triangles. Making a reduction from 3-dimensional matching, it is shown that the set of instances which can be generated by this algorithm is hard. The basic algorithm is extended to process graphs larger than triangles. We give implementation details of this extension and of four other variations of the basic algorithm. We compare these five and also two existing generators experimentally employing multi-start descent heuristic for the QAP as an examiner. The graphs with nonnegatively valued bisections can also be used in the construction of lower bounds on the optimal value for the rectilinear QAP. 相似文献
17.
Angela Gammella 《代数通讯》2013,41(10):3515-3528
In 1997, M. Kontsevich proved the L ∞-formality conjecture (which implies the existence of star-products for any Poisson manifold) using graphs. A year later, D. Tamarkin gave another proof of a more general conjecture (for G ∞-structures) using operads and cohomological methods. In this article, we show how Tamarkin's construction can be written using graphs. For that, we introduce a generalization of Kontsevich graphs on which we define a “Chevalley–Eilenberg–Harrison” complex. We show that this complex on graphs is related to the “Chevalley–Eilenberg–Harrison” complex for maps on polyvector fields, which is trivial and give Tamarkin's formality theorem as a consequence. This formality reduces to an L ∞-formality. 相似文献
18.
Wolff-Michael Roth 《The Journal of Mathematical Behavior》2004,23(1):75-92
This article raises questions about the meaning of “meaning,” which often is understood in terms of the referent or interpretant (sense) of mathematical signs. In this study, which uses data from an interview study with scientists who were asked to read graphs from their own work, a phenomenologically grounded approach is proposed with the intent to contribute toward a more appropriate theory of meaning. I argue that graphs accrue to meaning — which always arises from already existing, existential understanding of the world more generally and the workplace in particular — rather than having or receiving meaning from some place or person. We experience graphs as meaningful exactly at the moment when they are integral to a world that we already understand in an existential but never completely determinable way. 相似文献
19.
本文讨论一般含1-因子连通图的n次幂中边不交1-因子的个数.从而证明了L.Nebesky(1984)猜想对含1-因子图成立. 相似文献
20.
Michael Doob 《Linear algebra and its applications》2002,340(1-3):87-96
Circulant graphs satisfying det(−A(G))=−deg(G) are used to construct arbitrarily large families of graphs with determinant equal to that of the complete graph Kn. 相似文献