【数据结构】图的基础练习题目，及题解_在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要 条弧

1，有n个结点的无向图最多有 （）条边，有向图最多有（）条边（弧）

解：n(n-1)/2 , n(n-1)

无向图中两点之间连成一条直线；有向图中任意两个结点之间都有一对有向边（不允许自指）

（完全有/无向图的时候）

2，在有n个顶点的有向图中，每个顶点度最大可达（）。

解：2（n-1）

3,n个顶点的连通图的生成树含有（）条边。

解：n-1

一个极小连通子图可以构成一棵生成树。极小连通子图：该图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

所以连通图的生成树就可以看做是一棵普通的树，n个顶点构成的树含有n-1条边

4，在有n个顶点的有向图中，若要使任意两点间可以互相到达，则图中至少需要（）条弧。

解：n

任意两点都可以到达的有向图可以看做是强连通图。

当此有向图为构成环状时，弧最少。

5，设G为具有n个顶点的无向连通图，则G中至少有（）条边。

解：n-1

无向图中只要没有孤立的顶点时，都连通。

6，一个连通图的（）是一个极小连通子图。

解：生成树

7，具有10个顶点的无向图，边的总数最多为（）。

解：45

边数最多的情况是 无向完全图 的时候。所以根据公式 n(n-1)/2 可计算得出

8，如果含n个顶点的图形形成一个环，则它有（）棵生成树。

解：n

在环中删除任意一条边（弧）均可构成一个极小连通子图，从而可构成n棵生成树。

9，有n个顶点的有向图，至少需要（）条弧才能保证是连通的。

解：n

构成有向环状图的时候。

10，构造n个结点的强连通图，至少需要（）条弧。

解：n个。