图8.36给出了一个有向图，试求该图的邻接矩阵和可达性矩阵

请帮忙给出正确答案和分析，谢谢！

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“图8.36给出了一个有向图，试求该图的邻接矩阵和可达性矩阵”相关的问题

第1题

在图7-12中给出了一个有向图,试求此有向图对应的关系是否可传递的？如果不是可传递的.试求此图

在图7-12中给出了一个有向图,试求此有向图对应的关系是否可传递的？如果不是可传递的.试求此图的传递闭包。

点击查看答案

第2题

如果一个图中任意两个顶点vi，vj之间存在vi到达vj的路径，或vj到达vi的路径，则称该图是单向连通的。试证明单向连通的有向无环图具有唯一的拓扑有序序列。

点击查看答案

第3题

已知n阶无向完全图G有m条边，试求的补图的边数.

点击查看答案

第4题

问题描述:给定有向图G=（V,E).设P是G的一个简单路（顶点不相交)的集合.如果V中每个顶点恰好在P的

问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.

设计一个有效算法求一个有向无环图G的最小路径覆盖.

[设V={1,2,...,n},如下构造网络G₁=(V1,E₁):

每条边的容量均为1.求网络G₁的(x₀,y₀)最大流.]

算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).

结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.

点击查看答案

第5题

所谓单目标最短路径(single-destinationshortestpath)问题是指在一个带权有向图G中求从各个顶

所谓单目标最短路径（single-destinationshortestpath)问题是指在一个带权有向图G中求从各个顶

点到某一指定顶点v的最短路径，例如，对于图8-47(a)所示的带权有向图，用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.

关于最短路径的读法以顶点0为例，在从顶点0到顶点2的最短路径上，顶点0的后继为顶点1(即path[0]=1)，顶点1的后继为顶点3(即path[1]=3)，顶点3的后继顶点为2(即path[3]=2).

编写一个算法，求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char，边上权值的数据类型为float。

点击查看答案

第6题

PageRank算法是基于网页链接分析对关键字匹配搜索结果进行处理的。它借鉴传统引文分析思想：当

网页甲有一个链接指向网页乙，就认为乙获得了甲对它贡献的分值，该值的多少取决于网页甲本身的重要程度，即网页甲的重要性越大，网页乙获得的贡献值就越高。由于网络中网页链接的相互指向，该分值的计算为一个迭代过程，最终网页根据所得分值进行检索排序。

互联网是一张有向图，每一个网页是图的一个顶点，网页间的每一个超链接是图的一个边，邻接矩阵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)所对应的归一化特征向量。