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

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

admin2017-11-14  43
问题 关于图(Graph)的一些问题：
    (1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
    (2)表示有1 000个顶点、1 000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?
选项
答案(1)n(n—1)，n (2)106，不一定是稀疏矩阵 提示：此题考查的知识点是图的相关术语。 (1)在有向图G中，如果对于每一对vi，vj，属于V，vi不等于vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。最多边是所有的顶点每对之间都有边，边数为n(n一1)；最少只有一个方向有边，为n。 (2)元素个数为矩阵的大小，即106，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律，不一定稀疏。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/5DRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)