图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.     

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

负整数阶变参数复迭代系统的吸引子及其分形图

研究了一类负整数阶变参数复迭代系统的吸引子分布规律，且利用研究结果和计算机图示技术得到了相关的分形图。     

图的结构多项式与子图恒等式

本文定义了一族多项式并建立了它们与非标定图之间的一一对应关系.利用这些多项式,可以导出任一个图中一些子图的数目之间的关系.由于建立了图与多项式之间的联系,一些图的问题有相应的代数形式,特别是,我们给出了重构猜想的代数等价命题.此外,我们也给出了将图进行编号的一种方案.     

图的子图序列和图的子林分解

在文献[1]里,Michael.O.Albertson和David Berman对任意图G定义了一个函数f(G): 他们猜想当G是平面图时,f(G)的下界至少是1/2。如果这个猜想成立,则可以利用这结果,而不用四色定理来解决Erds-Vising问题.(在文献[2],251页,问题36).同时他们提出了对于其它类型图G,f(G)的下界问题.本文首先引进了子图序列概念,并用它作为工具来估计f(G)的下界.主要给出了在亏格大于零的定向曲面上图G的f(G)下确界。     

McKay箭图与覆盖空间

本文研究在自然扩张和嵌入下特殊线性群和一般线性群的有限子群的McKay 箭图间的关系. 我们证明在特定条件下, 一般线性群GL(m;C) 的有限子群G的McKay 箭图是其正规子群G∩SL(m;C)的McKay 箭图的正则覆盖, 而当把G 嵌入SL(m+1;C) 时, 新的McKay 箭图由在原来的McKay 箭图的每一顶点加上一个由其Nakayama 平移到其自身的箭向得到. 作为例子, 我们指出如何用这些方法得到一些有趣的McKay 箭图.     

图的孤立韧度与分数k-覆盖图

设G是一个图,若对于图G的任一条边e,都存在一个分数k-因子h,使得h(e)=1,则称图G是分数k-覆盖图.图G的孤立韧度I(a)定义为:若G是完全图,则I(C)= ∞;否则,I(G)=min{|S|/i(G-S):SCV(G),i(G-S)≥2},其中i(G-S)表示G-S中的孤立点数目.本文首次提出并研究了一个图是分数k-覆盖图与它的孤立韧度之间的关系,证明了当I(G)>k,并且δ(G)>k 1时,G是分数k-覆盖图.我们还证明了,这个结果是最好可能的.     

完全图删边子图的子刻画

In this paper, we show that some edges-deleted subgraphs of complete graph are determined by their spectrum with respect to the adjacency matrix as well as the Laplacian matrix.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了 k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了N(G,Kt)≤(n-k)(kt-1)+(kt).其次,如果s,t≥1,n≥k+1且s+t≤k...     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

图与补图全覆盖数间的关系

图与补图覆盖数、边覆盖数间的关系己得到,本文研究它们全覆盖数间的关系,术语、记号参见[1]。 定义1 对图G(V,E),B_T V∪E,若对于V∪E中的每一元素,或在B_T中、或与B_T中的至少一个元素相邻或相关联,则称B_T为G的全覆盖集;B_T是G的全覆盖集,若对G的任意的全覆盖集B'_T,有|B'_T|≥|B_T|,则称B_T为G的最小全覆盖集;G的最小全覆盖集中的元素数,称为G的全覆盖数,并简记为β_T(G),称使|E_T|最小、     

一类用于寻找欧拉生成子图边数的收缩子图

结合可折叠子图给出了可折叠α-子图的概念,得到可折叠α-子图一定为α-子图,并得到可折叠α-子图的顶点有交且边不交的并仍为可折叠α-子图.同时得到至多差1边具有3棵边不交的生成树的图和K_(l,m)(l≥3,m≥3)均是可折叠2/3-子图,并给出其在寻找欧拉生成子图极大边数的应用,同时也得到了一种寻找α-子图的方法.     

整数规划问题的滤子填充函数算法

全局优化是最优化的一个分支,非线性整数规划问题的全局优化在各个方面都有广泛的应用.填充函数是解决全局优化问题的方法之一,它可以帮助目标函数跳出当前的局部极小点找到下一个更好的极小点.滤子方法的引入可以使得目标函数和填充函数共同下降,省却了以往算法要设置两个循环的麻烦,提高了算法的效率.本文提出了一个求解无约束非线性整数规划问题的无参数填充函数,并分析了其性质.同时引进了滤子方法,在此基础上设计了整数规划的无参数滤子填充函数算法.数值实验证明该算法是有效的.     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

图中具有某种性质的子图

设ｇ和ｆ是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每个ｘ∈Ｖ（Ｇ）都有０≤ｇ（ｘ）≤ｆ（ｘ）且ｇ（ｘ）和ｆ（ｘ）为偶数。本文证明了：若Ｇ是一个（ｍｇ＋ｋ－１,ｍｆ－ｋ＋１）－图,１≤ｋ≤ｍ,Ｈ是Ｇ中一个给定的有ｋ条边的子图,则Ｇ存在一个子图Ｒ使得Ｒ有一个（ｇ,ｆ）－因子分解与Ｈ正交。     

关于图的子着色

本文主要讨论了子色唯一图的结构，并给出了唯一k-子色图、最大子色图的边临界子色图的特征．     

f—因子覆盖的图

设G为图,f是定义在V(G)上的正整数值函数。称图G的支撑子图F为f-因子如果d_(?)(x)-f(x),x∈V(G).称图G是f-因子覆盖的如果G的每条边包含在一个f-因子中.本文给出了一个图是f-因子覆盖的图的充要条件,其结果推广了C.H.C.Little et al.[1]的1-因子覆盖定理。     

关于图的星形因子覆盖

如果图 G 的支撑子图 M 的每个分支都同构于{K_(1,1)K_(1,2,)…,K_(1,k}(k≥2)中的某个 K_(1,i),则 M(?)叫做 G 的星形因子。进一步,如果对于图 G 的每一条边都存在一个星形因子包含这条边,则称图 G 是星形因子覆盖的。本文给出了图是{P_2,P_3}一因子覆盖的充要条件,并证明了任意正则图均存在星形因子覆盖。     

关于图的最小覆盖算法

本文就数学建模课的教学过程中 ,在“图的方法建模”一章中 ,关于图的最小覆盖法提出启发式算法 .用书中所给方法推出一个反例 ,分析了其产生错误的原因 ;通过对图的最小覆盖的概念的理解、结合分析图的关联矩阵的特点 ,给出了图的最小覆盖的启发式算法 .