共查询到18条相似文献,搜索用时 266 毫秒
1.
2.
本文讨论了 Cayley 图的直积不变性,进而得到了一个循环图可分解为若干个循环图的积图的充要条件,并旦得到了两个正则有向图的连通度与它们的积图的连通度的关系。 相似文献
3.
公全英 《大众科学.科学研究与实践》2007,(24)
在图的边面染色中,使得两相邻元素染不同颜色所需的最小色数,称为平图的边面染色数,首先系统地证明:假设是最大度为3的二连通平图,则边面染色数与最多度相等的充分必要条件是是一个2-连通3-正则二分平图,然后得出结论:任何连通平图,其边面染色数为3的充分必要条件是阶至少为三的一条路或2连通3正则二分平图。 相似文献
4.
本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω(G)的任意图G 的减最大-团横贯数给出了一个紧的下界1+ω(G)-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。 相似文献
5.
得出了3-正则图是Z3-连通的充要条件:一个连通的3-正则图G是Z3-连通的当且仅当G是正文中的图1或图2。 相似文献
6.
本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω(G)的任意图G的减最大-团横贯数给出了一个紧的下界1+ω(G)-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。
相似文献
相似文献
7.
8.
9.
10.
若连通图G在自同构群作用下具有两个轨道V1和V2且满足|V1|=|V2|;G[V1]是k-正则图;G[V2]是r-正则图且G[V1V2]是l-正则图,则K(G)≥min{k,r}+1.构造的例子表明上述结果是最好可能的. 相似文献
11.
斯琴巴特尔 《内蒙古民族大学学报(自然科学版)》2014,(6):621-623
双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,有重要的研究价值.确定一个图是否紧的是个困难的问题,目前已知的紧图族尚不多,本文介绍从某些已知的紧图出发构造紧图族的加边法,从而构造很多紧图族. 相似文献
12.
史天治 《长春师范学院学报》2006,(10)
该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。 相似文献
13.
王志雄 《华侨大学学报(自然科学版)》1993,14(4):412-418
给出若干类型多项式为简单图的色多项式的充分必要条件、连通图和连通双分图的色多项式必须满足的条件,研究图及其补图的色多项式对图特征的描述程度,并提出若干值得进一步探讨的问题。 相似文献
14.
利用图的邻接矩阵,构造出了若干紧图类.任意的链加1条边是紧图,任意的星加2条边是紧图,任意的星加3条边也是紧图. 相似文献
15.
刘儒英 《青海师范大学学报(自然科学版)》1989,(3)
设G是具有邻接矩阵A的简单图,P(x)是有理系数多项式,如果P(A)是某个图的邻接矩阵,我们记这个图为P(G)。我们考虑这样的问题:给一个图G,什么样的多项式P(x)给出一个图P(G)?这个图是什么样的图?当G是星图时,本文对上述问题给出完全的回答。然后,还导出一个连通正则图的不同特征根个数的新的下界。 相似文献
16.
针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。 相似文献
17.
18.
设G是连通循环图.本文讨论两个与循环图有关的图类的边着色问题,得到了下列结论:①如G是奇素数幂阶循环图,则对G的任意点v,G-v是第一类的;②如G是奇数阶循环图,则G的线图L(G)是1-可因子化的,当且仅当G的边数为偶数。 相似文献