5个顶点的无向图最多有（）条边。A、5B、10C、20D、25

第1题：

第2题：

第3题：

在顶点个数为n的无向图G中，若对于任意一对顶点都存在邻接关系，则无向图G共有（）条边。

正确答案:n(n-1)/2

第4题：

具有n个顶点的有向图最多有（）条边。

• A、N
• B、n（n-1）
• C、n（n+1）
• D、n²

正确答案:B

第5题：

如果G1是一个具有n个顶点的连通无向图，那么G1最多有（）条边，G1最少有（）条边。如果G2是一个具有n个顶点的强连通有向图，那么G2最多有（）条边，G2最少有（）条边。

正确答案:n（n-1）/2；n-1；n（n-1）；n

第6题：

具有6个顶点的无向图至少应用（）条边才能确保是一个连通图。

• A、5
• B、6
• C、7
• D、8

正确答案:A

第7题：

对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为（）和（）条。

正确答案:e；2e

第8题：

设无向图的顶点个数为n，则该图最多有（）条边。

• A、n-1
• B、n（n-1）/2
• C、n（n+1）/2
• D、n2

正确答案:B

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

n个顶点的强连通有向图G，最多有（）条边，最少有（）边。强连通图即是任何两个顶点之间有路径相通，当所有结点在一个环上时，必定是强连通图。

正确答案:n(n-1),n

第15题：

数据结构里，6个顶点的有向图，最多有（）条边。

• A、30
• B、15
• C、14
• D、31

正确答案:A

第16题：

具有n个顶点的有向无环图最多有多少条边？

正确答案: 具有n个顶点的有向无环图最多有n×（n—1）/2条边。
这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。

第17题：

29条边的有向连通图，至少有（）个顶点，至多有（）个顶点，有29条边的有向非连通图，至少有（）个顶点。

正确答案:6,29,7

第18题：

数据结构里，有4个顶点的无向图，最多有（）条边。

• A、6
• B、5
• C、7
• D、4

正确答案:A

第19题：

设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

正确答案:0；n（n-1）/2；0；n（n-1）

第20题：

第21题：

第22题：

第23题：