有向图的顶点加权zeta函数

给定一个有向图,每个顶点赋予一个权重。对于这个有向图定义了它的顶点加权zeta函数,函数的权重是由上面给定的顶点的权重诱导的有向图的圈的权重。并利用Amitsur恒等式和线性代数的相关知识给出了有向图的顶点加权zeta函数的两个行列式表达式。当有向图是对称有向图时,已有的结果是本文结果的自然推论。最后给出了一个例子并计算出此时顶点加权zeta函数的具体形式。     

扩充竞赛图的控制图

设D=(V,A)是一个有向图,对x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D。有向图D的控制图记为dom(D),它是一个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

强连通多部竞赛图中顶点和弧的外路

为了在强连通多部竞赛图中寻找顶点和弧的外路，采用对原图去顶点或去弧的方法。通过在新得到的有向图中寻找哈密尔顿圈，进而找到顶点和弧的外路。研究结果表明强连通多部竞赛图中顶点和弧泛外路的两个充分条件被获得。     

商Cayley图与顶点传递图

本文得到的一个令人感兴趣的结论是,顶点传递有向图(或无向图)必定是Cayley有向图(或无向图),反之亦然。     

竞赛图中Hamilton路数的矩阵求法

任一对不同顶点都相邻且无2-圈的有向图称为竞赛图.每个竞赛图都有Hamilton路,利用矩阵方法可求得计算竞赛图中的Hamilton路及Hamilton路数的方法,既为计算竞赛图的Hamilton路及Hamilton路数增加了一种新的计算途径,还可用来计算任意有向图的所有长为k有向路.     

一类乘积图的Pfaffian性

给图G的边任意一个定向,如果该有向图对应的斜邻接矩阵的行列式等于图G的完美匹配数的平方,那么就称这个定向是Pfaffian定向,图G称为Pfaffian图.研究Pfaffian图的意义在于它的完美匹配数能在多项式时间内得到.该文通过证明给出的定向是Pfaffian定向的方法证明了一类偶剖分图与三个顶点的路的乘积图是Pfaffian图.     

一类非负矩阵对的本原指数

研究了一类特殊的双色有向图,它的未着色图中含有3n-2个顶点,包含一个（2n＋1）-圈和一个n-圈的图,给出了本原条件和指数的上、下界,并对极图进行了刻划.     

立方图的可圈性

图的可圈性是哈密尔顿性的一个推广.设G是有向图,如果对G的每一个定向D,都存在S(D) V(G)使在D中改变所有恰与S(D)中一个顶点相关联的弧的方向后所得到的图为有向哈密尔顿图,则称G为可圈图.证明至少含5个顶点的连通图G的立方图是可圈图当且仅当G不同构于任何一条偶路.该结果改进了Klostermeyer的3个定理.     

有限有向图与有限幂零半群

本文给有限有向图Ｄ定义了乘法，从而得到这个有向图确定的半群Ｓ，证明了Ｓ的最小生成集Ａ＝Ｓ－Ｓ２＝Ｖ（Ｄ的顶点集）且，这个半群的秩等于Ｄ的顶点的个数。证明了两个有限有向图同构，当且仅当，它们分别确定的半群同构。     

无收点的有向图代数

对于有向图代数的研究通常是假定图是无收点的，对于一个有收点（没有任何边以其为起点的顶点）的有向图E往往要把它处理成无收点的图F，而且使得C^*（E）与C^*(F）间有良好的关系。据此给出一种方法，并且证明了C^(E)是C^*(F)的C^*－子代数，随之给出几个比较有趣的推论。     

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

点赋权图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点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.     

图P_n~k的着色

设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pnk满足点、边全着色猜想等结论.     

关于图论码的进一步分析

图论码是由一类简单无环图构造的一类特殊码,它的编码方式是由一个图的顶点所关联的边来建立编码关系。文章对图论码进行研究并得出一些结论,并对完全图所对应的图论码是等重码进行了讨论。     

P_m∨F_n(m=1,2,3,4,n+1)的点可区别均匀边染色

图G的一个正常边染色如果满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别的边染色,其所用的最少的颜色数称为图G的点可区别均匀边色数.运用组合方法研究联图Pm∨Fn的点可区别完全均匀边染色,得到当m=1,2,3,4,n+1时的Pm∨Fn的点可区别均匀边色数.     

广义Petersen图GP(n,k)的着色

本文研究广义Petersen图GP(n,k)的点着色、边着色和点-边全着色,得到广义Petersen图GP(n,2)的点色数、边色数和全色数,同时还得到当n为偶数,k为奇数时,该广义Petersen图GP(n,k)满足点-边全着色猜想等结论.     

基于酒店特征信息和在线评价信息的酒店选择

为辅助游客通过旅游网站进行酒店选择,提出了一种基于旅游网站提供的备选酒店特征信息和在线评价信息的酒店选择方法.首先,基于酒店特征信息和在线评价信息构建备选酒店有向加权图,依据备选酒店特征信息,基于离差最大化法对酒店特征进行客观赋权,并采用简单加权法确定有向加权图结点权重,依据备选酒店间在线评价信息的比较关系确定有向加权图的有向边及有向边权重;然后,基于PageRank算法原理给出备选酒店排序值求解算法;最后,以基于缤客网站提供的酒店特征信息和在线评价信息进行酒店选择.结果说明了提出方法的有效性和可行性.     

与图的支配性有关的不变量的若干不等式

证明了关于图的支配数、上支配数、全支配数、连通支配数、点－边弱（强）支配数及边－点弱（强）支配数的一些不等式，并继而讨论了这些不变量的若干介值性质     

图的一种加权邻接矩阵谱半径和能量的界

图G的一种加权邻接矩阵记为A_db(G)=(a^db_ij)_n×n,若顶点v_i和顶点v_j相邻,则$a_{i j}^{d b}=\frac{d_{i}+d_{j}}{d_{i} d_{j}}$, 反之a^db_ij=0.给出图G的加权谱半径的上下界,并在此基础上给出加权谱半径的Nordhaus-Gaddum-type关系.得到了图G的加权能量的几个上下界,并在此基础上给出加权能量的Nordhaus-Gaddum-type关系.