共查询到20条相似文献,搜索用时 109 毫秒
1.
任意连通图与偏k-树乘积图的树宽 总被引:1,自引:1,他引:0
一个图的树宽是使图成为一个k-树的子图的最小整数k,本文考虑了顶点数为m的任意连通图C与顶点数为n的k-连通的偏k-树的乘积图的树宽,首先利用对已知结构图进行树分解的方法,确定了二者乘积图树宽下界,然后结合乘积图树宽的上界,得出了在满足顶点数n≥mk的条件下二者乘积图树宽表达式. 相似文献
2.
王红专 《湖南文理学院学报(自然科学版)》2007,19(4):27-28
设T是一棵似星树,即其中仅有一个顶点的度数大于2的树,并设其中最大的顶点度数为m,T的广义连通指数为R_a(t)∑uv∈E(T),其中d(u)为树T中顶点u的度,α是任意实数.通过图的变换,证明了似星树的广义连通指数Rα(T)是e1m(T)的递减函数,e1m(T)是T中连接一个1度顶点与m度顶点的边数;并由此刻画了具有最大、最小广义连通指数的似星树. 相似文献
3.
证明了:1)图G和H的强乘积图GH的控制数γ(GH)≤γ(G)γ(H),并举例说明此上界是可以达到的;2)若γ(H)=1,则G与H的字典乘积图的控制数γ(G H)=γ(G);若G不含孤立点并且γ(H)≥2,则γ(G H)=γt(G),其中γt表示图的全控制数. 相似文献
4.
图G=(V,E)的一个正常着色就是将G的顶点划分为独立集,或称之为色类,记为П=|V1,V2,…VK|.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则”被称为是满色的.如果在一个正常着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为xf(G).另外,记f(G)为使图存在满着色的最大颜色数.在这篇文章中,我们研究了一些乘积图的满着色,得出一些关于正则图的满着色的结果. 相似文献
5.
在定义了一般树的乘积树以后,讨论了文献[1]中关于k-Suslin树的自乘积树的一个命题.证明了当k为正则基数时,k-Suslin树的自乘积树不再是k-Suslin树,并构造了一个ω-Suslin树,其自乘积树仍然是ω-Suslin树. 相似文献
6.
对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。 相似文献
7.
证明了半群Cayley图的乘积图仍是半群Cayley图.由于(弱)点传递图的乘积图保持传递性,进一步得到结论:(弱)点传递的半群Cayley图的乘积图仍是半群Cayley图,并保持(弱)点传递性. 相似文献
8.
9.
10.
刘海涛 《甘肃联合大学学报(自然科学版)》2008,22(2):30-32
设G是阶数不小字3的简单连通图,G的k-正常边染色称为是邻点可区别的,如果对G任意相邻两顶点关联边的颜色集合不同,则k中最小者称为是G的邻点可区别的边色数.本文给出了几类乘积图的邻点可区别的边色数的上界,并由此得到一些乘积图的邻点可区别的边色数. 相似文献
11.
12.
通过对树图生成算法的分析比较,得到各种树图生成算法的优劣性,从而可根据数据集合的特征和用户对可视化效果的不同要求,来选择算法或将几种算法结合使用. 相似文献
13.
通过对树图生成算法的分析比较,得到各种树图生成算法的优劣性,从而可根据数据集合的特征和用户对可视化效果的不同要求,来选择算法或将几种算法结合使用。 相似文献
14.
15.
16.
高敬振 《曲阜师范大学学报》1989,(3)
本文证明:如果连通图G的树图Г(G)不是超立方体,则对G的任两支撑树T和T′,除了当每一e′∈T′—T都满足|C(T,e′)|=2并且C(T,e′)为G的块时,Г(G)中没有长为d(T,T′) 1的连接T和T′的路外,对每一自然数k,d(T,T′)≤k≤t(G)-1,Γ(G)中都有长为k的连接T和T′的路(这里C(T,e′)、d(T,T′)和t(G)分别表示T e′中的唯一圈,Γ(G)中T和T′的距离、及G的支撑树数目)。 相似文献
17.
Petri网的可达图与可达树的比较 总被引:1,自引:0,他引:1
Petri网的可达图和可达树都是用于分析Petri网的工具,章将展示如何用可产完成Petri风的各项分析,并将可达图与可达树相比较,证明可达图是较可达树更为有一种分析工具. 相似文献
18.
G=(V,E)表示顶点集为V,边集为E的所有的简单连通图的集合.本文研究了S(p,q)的度距离,得到D’(S(p,q))按照p(或q)的一个排序,并对它们的极值情况下的极图进行了刻画. 相似文献
19.
戚啸虎 《淮北煤炭师范学院学报(自然科学版)》2014,(1):5-7
冠图G°H是由图G和H合成的图,其中使图G的每一个顶点分别与图H的每一个拷贝的所有顶点相连.如果图G的边集合可以分解为若干个边不相交的子图H,那么称G有子图H的分解,当H是P3或P4时,就称G有{P}3,P4分解.文章讨论了一些冠图的{P}3,P4分解问题,得到冠图Pm°Pn、Pm°Cn、Cm°Pn及Cm°Cn存在{P}3,P4分解. 相似文献
20.
拓展了目前关于星与低阶图的笛卡儿积交叉数的某些结论,确定了1个特殊6-阶图与星K1,n的笛卡儿积交叉数为z(6,n)+4n,并给出了1个有在K2,4,n中加入2条边分别联结K2,4,n中2对n+2度点得到的1个特殊图类Hn的交叉数. 相似文献