双循环，对集和树

令Ｇ＝（Ｖ，Ｅ）为一个图，它的节点数为ｎ，不仅是一个双循环也是一个上循环．记β（Ｇ）为Ｇ的双循环空间的维数．对于Ｇ的一个子图Ｈ，用φ（Ｇ，Ｈ）表示Ｇ的支撑森数目，使得它的每个树均恰含Ｈ的一条边．图Ｇ的Ｈ扩张Ｘ（Ｇ，Ｈ）在Ｇ上增添一个新节点ν，连ν与Ｈ的每一个奇次节点以一边所得到的图．本文证明，φ（Ｇ，Ｈ）是个偶数，要么Ｘ（Ｇ，Ｈ）不连通，要么Ｘ（Ｇ，Ｈ）有一个非零双循环．对于一个欧拉图Ｇ，令λ（Ｇ）为Ｇ中这样边的最小数目，使得在将它们从Ｇ中收缩掉而得到的图Ｇ中，所有那些落在奇数个完满对集上的边，形成一个非零双循环．同时还得到，在Ｇ的最大对集中边数为μ（Ｇ）的一个下界，即μ（Ｇ）≥（ｎ－｜β（Ｇ）－１｜）／２．对于非欧拉图Ｇ，令ψ（Ｇ）＝β（Ｘ（Ｇ，Ｇ）），和用γ（Ｇ）表示这样边的最小数目，使得在将它们从Ｇ中收缩掉而得到的图上，有边属于奇数个完满对集．我们证明，γ（Ｇ）＝ψ（Ｇ）以及μ（Ｇ）≥（ｎ－ψ（Ｇ））／２．     

树的奇因子

树的奇因子马润年１高安喜２（１空军电讯工程学院数学教研室，西安７１００７７；２陕西财经学院管理系，西安７１００６１；第一作者，男，３２岁，讲师）设Ｔ为一树，用Ｖ（Ｔ）和Ｅ（Ｔ）分别表示Ｔ的顶点集和边集，任给ｘ∈Ｖ（Ｔ），用ｄＴ（ｘ）表示ｘ在Ｔ中的顶点...     

求线图树集的DIDORTG方法

本文根据求线图树集的参考树组概念(RTG)和行列式的等降阶分解原理(DIDO),提出了一种新的参考树组法——DIDORTG方法,对完备图和非完备图各级置换系数进行了分析计算,并将DIDORTG方法和其它求线图树集的方法作了初步比较.     

4直径树线图的区间图扩充问题

起源于稀疏矩阵计算和其他应用领域的区间图扩充问题包含两个问题:图G的侧廓问题和路宽问题, 分别表示为P(G) 和 PW(G).本文首先利用图扩充方法,给出直径为4的树T的线图L(T)的区间图完全化方法I; 其次,根据完全化方法I,得到了线图L(T)的侧廓P(L(T))和路宽PW(L(T))的表达式.     

繁星树线图的完美匹配数

称一棵树T为繁星,如果它可以通过在星形树的悬挂点上添加一些悬挂边得到．给定两个正整数k和l满足k+l为偶数,令■表示由星形树S_1,k添加l条悬挂边而得到的所有繁星的集合．对任意的繁星■,本文首先得到了其线图完美匹配数M(L(T))的表达式,然后通过引进一些变换,确定了M(L(T)),■的最小值和最大值．     

K1,r—Free图的生成树及其算法

证明了任一连通的Ｋ１，ｒ－Ｆｒｅｅ图都有最大度小于等于ｒ的生成树，并建立了算法。     

求最小部分树的新方法

本文给出了求最小部分树的一种新方法，同时给出最短路权的矩阵求法。     

一类直径为6的优美树

利用毛毛虫的平衡二分性和直径为5的树的优美性,构造出一类直径为6的树,并证明了它的优美性。     

树的有效支配集

本文提出一个线性时间算法,利用这一算法可判断一棵树是否具有有效支配集。     

δ>2极大平面二分图间的关系

本文讨论δ>2极大平面二分图之间的关系,证明了 B_(mn)每一图可由其任一图经改边得到.     

沿通路送流的两个新算法

本文证明对满足一定约束条件的一类无耗网络,应用沿通路送流法,可获得一个有效的求多商品流算法,其运算复杂度仅为 O[d_(pr,max)|E(P_((?),max))|(n k-1)],并且当流网络中各边容量及各源汇对间传输要求量均为整数的情况下,可获得整数流解.本文还将上述算法推广到有耗网络中多商品流的求解问题,提出并证明了平面有耗网中多商品流存在的充分条件,据此获得一个求有耗网络多商品流的多项式时间算法.     

信号流图的化简方法及原则

信号流图与结构图一样,在各种系统分析中有着广泛的应用。本文详尽分析了信号流图与结构图的异同点,并在此基础上提出了正确化简信号流图的方法与原则。     

键合图法线性系统动态仿真

本文较详细地阐述了线性系统动态仿真的键合图法,给出了线性系统状态方程的统一表达式,利用该方法,对于具体问题按照键合图理论输入系统的结构参数及结型矩阵,就可以由计算机自动地以格式化的方式生成系统的状态方程并求解。同以前类似的方法相比较,本文所给出的系统状态方程的统一表达式,考虑了独立贮能场,非独立贮能场能的能量变量和共能量变量间关系存在耦合时的更一般情况,对前人的工作做了一些补充。     

完全二部图k_(4,n)去掉两条边的交叉数

用km,n表示完全二部图,用k4,n\e1,e2表示完全二部图k4,n去掉两条边e1、e2。本文确定了K4,n\e1,e2的交叉数为z(4,n)-22n+2。K4,n\e1,e2。     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图.两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系.面是平面图区别于非平面图的本质特征.同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的.任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过 D-过程画出.平面图与其对偶图互为对偶.显平面图与其隐对偶图合称为相伴对偶图.     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

星和完全等二部图联图的邻强边染色

对于1V（G）≥31的连通图G（V,E）,若缸正常边染色法满足相邻的边染色集合不同,则称该染色法为缸邻强边染色法,其最小的称为G的邻强边色数。本文用特殊的方法记图的染色,并得到了星和完全等二部图联图的邻强边色数。     

图论在大学生数学建模竞赛中的应用

随着图论的发展,图论的理论和方法广泛应用于大学生数学建模竞赛中．讨论了大学生数学建模竞赛中如下图论问题的应用：二分图的最大匹配,最大点独立集;最佳推销员回路,哈密尔顿图;最小生成树等．     

屏幕图形的保存与恢复方法

通过具体屏幕图形的实例，说明了在Ｃ语言中，屏幕图形保存与恢复的两种处理方法，即全屏幕保存与部分屏幕保存的方法，对两种处理方法在存储时间、存储的文件大小、恢复图形的时间进行了对比。