首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.  相似文献   

2.
李赵祥  任韩 《数学学报》2011,(2):329-332
研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入.  相似文献   

3.
陈仪朝等运用覆盖矩阵和Chebyshev多项式计算了一些图类在曲面上的亏格分布,本文给出了一类不能运用Chebyshev多项式的类循环图,计算出它在可定向曲面上的嵌入.  相似文献   

4.
图的最大亏格的一个性质   总被引:2,自引:0,他引:2  
本文所考虑的图均指有限元向图,没有解释的术语和记号同[1].一个图称为简单图如果不含重边及环.曲面S这里指一个紧的,连通的,2-维闭流形(定向或不可定向),其亏格记为g(S).连通图G在曲面S上的一个2-胞腔嵌入意指存在一个1-1连续映射h:G→S使得S\h(G)的每个连通分支与圆盘拓扑同胚.连通图G的定向亏格γ(G)(或不可定向亏格γ(G))是指最小的整数k使得G在亏格为k的定向(或不可走向)曲面S上有2-胞腔嵌入;而图G的最大定向亏格,也常称之为最大亏格,记为γM(G),是指最大的整数k使得G在亏格为k定向曲面S上有…  相似文献   

5.
本文研究了图嵌入到给定紧致曲面上的拉普拉斯谱半径,确定了将顶点数为n、最大度为△的图分别嵌入到亏格为g的定向曲面和亏格为h的不可定向曲面上的新上界.  相似文献   

6.
首先由完全图K19的两种电流图满足KCL电流定律,建立线性方程组,利用计算机求出方程组的所有解,由一组解对应K18电流图的一种电流赋值方式,得到两种电流图的不同电流赋值方式数为34和6,然后求出K19两种电流图的基础图在可定向曲面上分别有16种不同的单面嵌入;由上面的结论得到完全图K19在可定向曲面上至少有640种不同...  相似文献   

7.
证明了一个连通无环图G如果能嵌入某个 (定向或不可定向 )曲面S上使得每个面的大小不超过 5 ,则G是上可嵌入的 .  相似文献   

8.
关于图的余树的奇连通分支数的内插定理   总被引:4,自引:0,他引:4  
本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.  相似文献   

9.
不可定向的流形曲面不仅在拓扑学中占据重要的地位,在可视化和极小曲面等问题中也有很多的应用.从拓扑学的观点来看,二流形曲面的每个局部与圆盘同胚,该性质与曲面的全局可定向性无关.但在离散化的网格表示上,可定向的二流形曲面常用半边结构来表达,而不可定向的二流形曲面大多表达成若干多边形的集合,这给以可定向网格曲面为主要研究对象的数字几何处理带来很多不便.本文提出了把不可定向的二流形网格曲面上的测地距离问题转化到可定向曲面上进行处理的一般算法框架.该框架有望在不可定向的二流形网格曲面与传统数字几何处理方法之间搭起一座桥梁.为了展示该算法框架的普适性,本文将其应用于不可定向曲面上的三个重要场合,包括测地距离的求解、离散指数映射和最远点采样.  相似文献   

10.
不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格.  相似文献   

11.
A two-dimensional framework (G,p) is a graph G = (V,E) together with a map p: V → ℝ2. We view (G,p) as a straight line realization of G in ℝ2. Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if %and for all equivalent frameworks (G,q), the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. The graph G is globally rigid if all of its pairs of vertices are globally linked. We extend the characterization of globally rigid graphs given by the first two authors [13] by characterizing globally linked pairs in M-connected graphs, an important family of rigid graphs. As a byproduct we simplify the proof of a result of Connelly [6] which is a key step in the characterization of globally rigid graphs. We also determine the number of distinct realizations of an M-connected graph, each of which is equivalent to a given generic realization. Bounds on this number for minimally rigid graphs were obtained by Borcea and Streinu in [3].  相似文献   

12.
图G是一个简单图,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图.鸡尾酒会图CP(n)=K_(2n)-nK2(K_(2n是完全图)和完全图K_a都是整谱图.μ_1表示图类αK_a∪βCP(b)的一个主特征值,确定了当μ_1=2a并且a-1>2b-2时,图类αK_a∪βCP(b)中的所有的整谱图.  相似文献   

13.
The clique-transversal number τc(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number αc(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058–1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n2) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding αc and τc.  相似文献   

14.
图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.  相似文献   

15.
The first and second Zagreb eccentricity indices of graph G are defined as:E1(G)=∑(vi)∈V(G)εG(vi)~2,E2(G)=∑(vivj)∈E(G)εG(vi)εG(vj)whereεG(vi)denotes the eccentricity of vertex vi in G.The eccentric complexity C(ec)(G)of G is the number of different eccentricities of vertices in G.In this paper we present some results on the comparison between E1(G)/n and E2(G)/m for any connected graphs G of order n with m edges,including general graphs and the graphs with given C(ec).Moreover,a Nordhaus-Gaddum type result C(ec)(G)+C(ec)(■)is determined with extremal graphs at which the upper and lower bounds are attained respectively.  相似文献   

16.
对于一个简单图G, 方阵Q(G)=D(G)+A(G)称为G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别为G的度对角矩阵和邻接矩阵. 一个图是Q整图是指该图的无符号拉普拉斯矩阵的特征值全部为整数.首先通过Stanic 得到的六个顶点数目较小的Q整图,构造出了六类具有无穷多个的非正则的Q整图. 进而,通过图的笛卡尔积运算得到了很多的Q整图类. 最后, 得到了一些正则的Q整图.  相似文献   

17.
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.  相似文献   

18.
A product dimension of bipartite graphs bid G analogous to the Dushnik-Miller dimension of posets and to the dimension of general symmetric graphs is studied. It is shown that bidG ≦ 1/2|V(G)| + 1 and almost all bipartite graphs G have bidG close to 1/2|V(G)|. On the other hand it is shown to be considerably less for everyday graphs like trees, cycles, cubes, etc.  相似文献   

19.
图G的一个匹配M是导出的,若M是图G的一个导出子图。图G是导邮匹配可扩的(简记IM-可扩的),若图G的任一导出匹配均含于图G的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得M≥r”是NP-完全的。⑵对直径为2的图以及直径为3的偶图,问题“确定一个给定图是否为导出匹配可扩的”是CO-NP完全的;而对完全多部图而言,问题“  相似文献   

20.
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号