赋权连通图的最小树图的连通情况

以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。     

求赋权图上最小树的两个算法

该文证明了赋权图上的树为最小树的一个充要条件，并由此得到求赋权图上最小树的两个算法。     

赋权图中最重的最长v-路与赋权周长

对2－连通非Hamilton赋权图G,本文证明：若P（u,v)是G中最重的最长路，则G的赋权周长C^w(G)≥d^w(u) d^w(v)，假设G满足文中描述的额外条件C1，C2，则max｛d^w(x),d^w(y)|d(x,y)=2｝≥m/2时，对每个顶点v,G含量最重长v-路P（u,v)使d^w(u)≥m/2，而d^w(x) d^w(y) d^w(z)≥m（当d(x,y,z)=2)时，c^w(G)≥2m/3.改进了非赋权图的周长及赋权图的赋权周长的若干已有结果。     

一类极大临界h连通图

讨论了最小度等于３ｈ／２－１的极大临界ｈ连勇图的性质，并给出这类图的构造方法。     

3连通图生成树上的可去边

摘要：设G是3连通图，e是G中的一条边．若G—e是3连通图的一个剖分．则称e是3连通图G的可去边．否则，称e是G的不可去边．本文给出某些3连通图的生成树上可去边的分布情况及数目。     

图的路连通问题

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。     

λ3,q-连通图的刻画

连通图G称为λ3,q-连通的如果存在边割S使得G-S有两个阶数分别至少为p和q的连通分支。给出一个图是λ3,q-连通的一些充分和必要条件。     

二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

关于点赋权图的赋权控制数的一个上界

点赋权图Gw=（V,E,W）是指对简单图G的顶点集作一个赋权函数W：V→R^＋。在图G所有的控制集D V（G）（V（G）／D中的任意顶点v都与D中的点关联）中最小的权和W（D）称为图Gw的赋权控制数。记作γw（Gw）。证明了对基数为N,平均权为W^-的图Gw,其赋权控制数γw（Gw）≤Nw^-1δ＋1^——1＋1n（δ＋1）。     

单圈图的连通子图的数目

图的某种子图的计数是个被广泛研究的课题,考虑了单圈图的连通子图的计数问题,给出了一个线性算法来计算单圈图中连通子图的数目.     

关于k临界n连通图

介绍k临界n连通图的性质和已经证明以及尚未证明的一些猜想。     

矩阵方法求赋权图中最短路的算法

目的 给出一些计算赋权图中任意两个节点之间最短路的算法。方法 利用矩阵方法。结果 给出了赋权图中任意两点之间最短路的算法；任意两点之间在含有最少边数情况下的最短路算法；赋权图中的所有最短路算法，以及前N条最短路的算法。结论 所研究的算法解决了传统算法的某些不足，因基于矩阵运算，程序设计简单，实用性强。     

k—连通图为Dλ—连通的一个充分条件

本文在对有限简单图给出 D_λ—连通的定义之后,证明了下述定理:设 G 是n 阶 k—连通(k≥3)的有限简单图,如果对任意的 Y∈I_k(G,λ),有sum from i=1 to k (k+i-2)/(k-1)s_i(Y、λ)>n-k(λ-1),则 G 是 D_λ—连通的.     

有关连通图的连通包数的一些结果

通过图的连通包集和连通包数的定义,确定了测地数、包数和连通包数三者之间的大小关系,并通过一些特殊图(完全二部图、分裂图)构造了连通包数为3的3类图.     

一类极大临界h连通图的性质

设G是h连通图，图G的顶点υ称为临办点，G－υ不再h连通，如果G的每个顶点都是临界的，则称G为临界h边连通图。对于G中任意两个相邻的项点x与y，G＋xy不再临界h连通，则称G为极大临界h连通图。引入图的粘合的概念，讨论了δ（G）＝3h／2－1的极大临界h连通图的性质，得到了这类图有关原子，最小点割和分支的重要性质，这有利于进一步研究这类图的结构。     

Hamilton连通图的一个充分条件

设Ｇ是ｎ阶３－连通图，若对任意不相邻二点｛ｕ，ｖ｝Ｖ（Ｇ）有ｄ（ｕ）＋ｄ（ｖ）＋２｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥２ｎ＋１，则Ｇ是Ｈａｍｉｔｏｎ连通的。     

赋权图过指定点的圈

设G是满足条件D1和D2的2-连通非Hamilton赋权图,证明了如下新结果：若G满足dw（x）＋dw（y）≥m（xy不属于E（G）,x≠y）,则通过图G的每个顶点存在权重大于或等于m的圈.该结果推广了非赋权图的已有结果.     

图的赋权邻域坚韧度

将邻域坚韧度引入赋权图中,提出图的赋权邻域坚韧度概念。在给出一些基本图的赋权邻域坚韧度的基础上,着重研究几类图的赋权邻域坚韧度的极值问题。结果表明,参数值与图的结构、权值大小和赋权方式均有关系,因而能更为准确地刻画网络的抗毁性。     

连通图二次幂图的Hamilton连通性

本文对圈和树的二次幂图的 Hamilton 连通性进行了研究。     

一类极大临界h连通图的结构

引入图的粘合的概念,进一步研究最小度等于3h/2-1的极大临界h连通图均性质,给出一个图是这类图的一个充要条件,由此给出这类图的一种新的构造方法,更易操作．