关于图(Graph)的一些问题： (1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边? (2)表示有1 000个顶点、1 000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?

admin2017-11-14 35

问题关于图(Graph)的一些问题：
(1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
(2)表示有1 000个顶点、1 000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?

选项

答案(1)n(n—1)，n (2)10⁶，不一定是稀疏矩阵提示：此题考查的知识点是图的相关术语。 (1)在有向图G中，如果对于每一对v_i，v_j，属于V，v_i不等于v_j，从v_i到v_j和从v_j到v_i都存在路径，则称G是强连通图。最多边是所有的顶点每对之间都有边，边数为n(n一1)；最少只有一个方向有边，为n。 (2)元素个数为矩阵的大小，即10⁶，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律，不一定稀疏。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/5DRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

关于图(Graph)的一些问题： (1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边? (2)表示有1 000个顶点、1 000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?

计算机408

学硕统考专业

战后西欧经济由严重衰落几近崩溃发展到20世纪60年代重又与美国分庭抗礼的原因是什么?

1934年9月苏联加入国联，对此说法错误的一项是()。

关于“尊王攘夷”运动，不正确的说法是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

已知加权有向图G如下，回答下列问题：(1)画出该有向图G的邻接矩阵；(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

下列有关审计重要性的说法中，错误的是()。

芒硝的化学成分主要是

一般纳税人企业，增值税的明细科目设置为三级，下列各项中，应在借方表示的是()

政治与教育之间并不是只有单向的决定作用，它们之间是彼此制约的。

简述违法行为、法律责任与法律制裁的联系与区别

甲下班时误将同事的同款手机当成自己的手机带回家。甲对该手机的占有属于()。

从多个关系中抽取出所需要的属性组成新关系，应使用的操作是