共查询到10条相似文献,搜索用时 62 毫秒
1.
2.
一、 引言 本文中未加说明的图论术语来自文献[1]。图G=(V,E)称为弦图,如果G的任何长度大于3的圈都有弦,或者等价地,任何长度大于3的圈都不会是G的点导出子图。本文中,子图总是指点导出子图,点子集S导出的G的子图记为G[S]。团是指完备子图,通常用它的点集来表示。如果图G的每个点v都带有点权w(v),则点子集S的权定义为S中点的权的和。 相似文献
3.
扈生彪 《数学的实践与认识》2011,41(15)
设A(G)是简单图G的邻接矩阵,H是由G的独立边和不交圈组成的生成子图的集合,e是H中某个图的独立边,C是H中图的圈,且e∈E(C).记G-e是G的删边子图,G\W是从G中删去导出子图W中的顶点及其关联边后得到的图.那么A(G)的行列式为detA(G)=detA(G-e)-detA(G\e)-2(-1)~(|V(C)|)detA(G\C)A(G)的积和式为perA(G)=perA(G-e)+perA(G\e)+2perA(G\C)这里,C取遍H中图的经过边e的圈. 相似文献
4.
吴举林 《高校应用数学学报(A辑)》1991,6(3):420-426
本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法. 相似文献
5.
黄振杰 《数学的实践与认识》2000,30(4)
一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 . 相似文献
6.
设G是n阶2-连通图,3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L,若d(u)且如果dL(u,v)=2有(v)=min{,|M3(u)|/2}这里M3(u)={v|dc(u,v)≤3},则G包含长至少为c的圈. 相似文献
7.
无爪图的导出匹配可扩性 总被引:6,自引:0,他引:6
若图G的一个匹配M也是G的点导出子图,则称M是图G的一个导出匹配.我们称图G是导出匹配可扩的,若它的任何一个导出匹配可以扩充成一个完美匹配,本文我们讨论无爪图的导出匹配可扩性,得出如下结论,并同时指出这些结果是最好可能的.设图G是有2n个顶点的无爪图,1.若图G是最小度大于或等于2 1,则图G是导出匹配可扩的.2.若图G是局部2连通的,则留G是导出匹配可扩的.3.若图G是k正则的且k≥n,则图G是导出匹配可扩的. 相似文献
8.
设G是一个图且a,b是非负整数,a≤b.图G的一个[a,b]-因子是图G的一个支撑子图H且满足对所有的x∈V(G),a≤dH(x)≤b都成立.给出了图中[a,b]-因子包含给定圈的一个充分条件. 相似文献
9.
设t,a,b和n为整数且1≤a<b,t≥3以及n≥1.如果G的导出子图不含有K1,t,则该图G称为K1,t-无爪图.如果对于图G中含有n条边的任意匹配M,都在G中有[a,b]-因子F包含M以及在G中有另一个[a,b]-因子F'不包含M,则图G称为[a,b;n]-均匀图.给出了K1,t-无星图G是[a,b;n]-均匀图的度条件.进一步,指出本文中的结果在某种意义上说是最佳的. 相似文献