如果表示有向图的邻接矩阵是对称矩阵,则该有向图一定是完全有向图。()
此题为判断题(对,错)。
此题为判断题(对,错)。
A、c
B、2e
C、e2
D、n2
互联网是一张有向图,每一个网页是图的一个顶点,网页间的每一个超链接是图的一个边,邻接矩阵B=(b)w如果从网页i到网页j有超链接,则by=1,否则为0。
记矩阵B的列和及行和分别是它们分别给出了页面j的链人链接数目和页面i的链出链接数目。假如在上网时浏览页面并选择下一个页面的过程,与过去浏览过哪些页面无关,而仅依赖于当前所在的页面。那么这一-选择过程可以认为是一一个有限状态、离散时间的随机过程,其状态转移规律用Markov链描述。定义矩阵A=(ay)wxn为式中:d是模型参数,通常取d=0.85;A是Markov链的转移概率矩阵;ay表示从页面i转移到页而j的概率。根据Markov链的基本性质,对于正则Markov链存在平稳分布x=式中:x为在极限状态(转移次数趋于无限)下各网页被访问的概率分布,Google将它定义为各网页的PageRank值。假设x已经得到,则它按分量满足方程网页i的PageRank值是划,它链出的页面有τ个,于是页面i将它的PageRank值分成r份,分别“投票"给它链出的网页。x为网页k的PageRank值,即网络上所有页面“投票给网页k的最终值。根据Markov链的基本性质还可以得到,平稳分布(即PageRank值)是转移概率矩阵A的转置矩阵AT的最大特征值(=1)所对应的归一化特征向量。
已知一个N=6的网络如图4.8所示,求它的PageRank取值。
A、用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关,而与图的边数无关
B、邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用
C、邻接矩阵只适用于稠密图(边数接近于顶点数的平方),邻接表适用于稀疏图(边数远小于顶点数的平方)
D、存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的下(上)三角部分就可以了
对图9.17给出的有向图G:
(1)写出它的邻接矩阵A,用邻接矩阵计算各个结点的出度与人度.
(2)计算说出从出到后的长度为1,2,3,4的拟路径各有多少条.
(3)计算,说出它们中第2,3分量及第4,4分量的意义.
(4)计算它的路径矩阵B及可达性矩阵P,并从P说出G的各强分图.
A、O(nlog2e)
B、0(n+e)
C、((n')
D、O(n2)
在如图8-1所示的有向图中:
(1)该图是强连通的吗?若不是,给出其强连通分量。
(2)请给出该图的所有简单路径及有向环。
(3)请给出每个顶点的入度和出度。
(4)请给出该图的邻接矩阵、邻接表、逆邻接表和十字链表。
点序列和按广度优先搜索遍历得到的顶点序列。