论文部分内容阅读
图G的Wiener指数定义为G中所有点对的距离和。最近Wiener指数的概念被推广到非强连通有向图中,这一推广可被应用于大规模有向网络的分析。图G的定向是对G的每条边指定一个方向得到的有向图。M.Knor等人猜想图G的极小Wiener指数可由某种c(G)导出定向取得。第一章概述有向图Wiener指数的研究进展和基于度的几类拓扑指数的研究现状,提出本文拟解决的问题和取得的主要结果。第二章提出I-点和Wiener增量的概念,构造了一类不满足着色导出定向猜想的图,否定了该猜想。进一步的,我们猜想对任意的正整数k(k33),存在色数为3的图,其极小Wiener指数定向中含有至少k长的有向路,并证明了k£6的情况。第三章研究一些特殊图类的极小Wiener指数定向问题,给出了几个基本结果,研究了两类双圈图的极小定向。第四章讨论具有较大Randi?指数的图结构,确定了含悬挂点三圈图的Randi?指数上界,给出了三圈图的前六大Randi?指数,并刻画了相应的极图。第五章研究harmonic指数的极值问题,确定了三圈图的前六大harmonic指数及相应极图。