树图的全控制数

设G为n阶连通图，集合S称为图G的全控制集，如果V（G）的每个顶点都和S中某点相邻。图G的全控制数，记为γt（G），是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1，n-1的树T，γt（T）=min{（2n/3），n-l，[n/2]＋l-1}，这里l表示树T中叶子的数目。     

树图及其顶点数的计算

文章从生成树之间的距离出发,定义了连通图的树图概念并证明了若干个简单性质,然后根据基本关联矩阵的性质,讨论了用行列式计算给定连通图的树图的顶点数。     

一类树图的第二大特征值

利用图的子图结构与插值理论,研究树图T (1,b,c)(c≥b≥5)的第二大特征值与其子图P_i(c≥i≥c-3)第一大特征值的关系,进而给出这类树图第二大特征值的分布及变化情况,并确定T(1,b,c)与T(1,b-2,c+2)依第二大特征值的排序关系.     

树图和单圈图的调和指标

利用改变图的叶子点数目的变换,得到了关于调和指标的两个引理,证明了固定阶数的树图和单圈图的调和指标的紧的上下界,并给出相应极值的图类。     

最大外可平面图的树图

通过对最大外可平面图和Ｋ临界图的研究给出三个主要结论（１）最大外可平面图的生成树有２＾ｐ－３＊３棵。（２）最大外可平面图的树图ＧＴ,β（ＴＧ）≥ｐ＋１。（３）临界图Ｇ,当Ｋ（Ｇ）＝１时,树图ＧＴ是平凡图,当Ｋ（Ｇ）＝２时,对图ＧＴ是ｐ图。     

类树图的亏格多项式问题

一个图G的亏格多项式表征了图G亏格的亏格分布情况.本文在解决M系列图的亏格多项式的基础上,利用切分与还原的方法,建立了计算类树图的亏格多项式的公式.     

树图的外围维纳指标的下界

设G=(V,E)为简单连通图.对v∈V(G),顶点v的离心率ε(v)=max{d(u,v)│u∈V(G)}, d(u,v)为图G中顶点u,v间的距离.图G的直径为d(G)=max{ε(v)│v∈V(G)}.外围顶点集P(G)指图G中满足ε(v)=d(G)的所有v=V(G).图G的外围维纳指标为■.首先讨论了当树图T的外围顶点个数确定时,它的第二下界;然后讨论了当树图T的顶点数目确定时,其对应的PW(T)的最小值,及达到其最小值的极图.     

类树图亏格分布的单峰性

图的亏格分布是否为单峰,这一猜想至今没有得到证明.文章首先给出了单峰性的概念及性质,并进一步推导得到了单峰性的另一重要性质。在此基础上,使用分类讨论的方法,证明了类树图的亏格分布是单峰的.     

两类树图的Hamiltonian色数

一个n阶连通图G的Hamiltonian染色是从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射c,使得对于G的任意2个不同的顶点u和v满足|c(u)-c(v)|+D(u,v)≥n-1,其中D(u,v)表示G中u到v的最长路径的长度。对一个Hamiltonian染色c,将max{c(u):u∈V(G)}称为c的值,记作hc(c)。将min{hc(c):c是G的任意Hamiltonian染色}称为G的Hamiltonian色数,记作hc(G)。本次研究得到了满足max{D(u,v)|u,v∈V(G),u≠v}≤n/2的d-重似星树和广义双星这两类树图的Hamiltonian色数的确切值。     

对树图生成算法的比较研究

通过对树图生成算法的分析比较,得到各种树图生成算法的优劣性,从而可根据数据集合的特征和用户对可视化效果的不同要求,来选择算法或将几种算法结合使用。     

有向树图的连通性及其算法

证明了树形图图的连通性，给出了求全部树形图的广探算法。     

关于树图的四个等价概念

给出树图的四个刻划定理，并证明了它们的等价性。     

对树图生成算法的比较研究

通过对树图生成算法的分析比较,得到各种树图生成算法的优劣性,从而可根据数据集合的特征和用户对可视化效果的不同要求,来选择算法或将几种算法结合使用.     

树图集散集数与中心的性质

本文讨论了树图的集散函数和集散中心的性质，首先给出了树图集散函数的上、下确界以及给定集散函数值，树的存在性，然后讨论了集散的构成和树去掉一悬挂点后所得到的集散中心与原树集散中心的关系。     

树图集散函数与中心的性质

本文讨论了树图的集散函数和集散中心的性质。首先给出了树图集散函数的上、下确界以及给定集散函数值、树的存在性;然后讨论了集散的构成和树去掉一悬挂点后所得到的集散中心与原树集散中心的关系。     

关于树图的谱半径的界

给出了由边数为m、顶点数为n的简单连通图G生成的树图T(G)及邻树图T^*(G)的谱半径的上界：ρ（T（G））≤det(Hr(G))(1-1/m) ρ(T^*(G))≤det(Hr(G))(1-1/x′（G））其中x′（G）是图G的边色数;并指出当G≌Cn时,ρ（T（G））的上界可达。     

关于树图的秩与行列式的计算

到目前为止,对于图的邻接矩阵的秩与图的关系一直没有多少结果。特别是图的行列式的计算,除直接计算行列式外,还不能利用图本身的组合性质去得到行列式的值。本文采用了全新的方法,完整地解决了树图邻接矩阵的秩的计算,并且得到了树图的行列式的值是单模的。     

树图的最大匹配的一个简易算法

0 前言 目前一般简单图的最大匹配的算法主要是1965年Edmonds提出的逐次调整的方法[1]。对于较特殊的双图,其最大匹配的算法主要是匈牙利方法[2]和网络最大流算法[3]。Edmonds算法和匈牙利方法的本质是一致的,都是对图中未饱和点生长一个M—交错树,逐步扩大匹配,最终达到求出最大匹配的目的;而双图的最大匹配的网络最大流算法也具有类似的性质,即逐步调整流量来达到求最大匹配的目的。这些方法均不可避免地要对已经计算过的点(或线)在不同程度上重新进行计算,即便当图是树图时也是如此。这样当图的点数相当大时,其计算量是很大的。本文根据[4]提出的理论和结论,给出了树图的最大匹配的一种简易算法。该算法设有重复计算,从而在计算量上比上述诸方法大大降低。由该算法还能同时给出树图邻接矩阵的秩和行列式的值。     

树图与单圈图的线图的Hyper-Wiener指数

主要考虑了线图的hyper-Wiener指数,分别得到了树图和单圈图的线图的hyper-Wiener指数的上下界及取得上下界的极图.