内容发布更新时间 : 2024/5/4 17:57:55星期一 下面是文章的全部内容请认真阅读。

第八章 图

PROBLEM 1

(1/1 分)

下图中的强连通分量的个数为多少个？

How many strongly connected graphs in the under graph?

3

3 - 正确

3

3

Explanation

有向图强连通的极大子图称为该有向图的强连通分支或者强连通分量。分别为最左边1个点组成的极大子图，中间4个点组成的极大子图和最右边1个点组成的极大子图。分别为最左边1个点，中间4个点和最右边1个点。 Maximal strongly connected subgraphs of a directed graph are called strongly connected components of this directed graph.They are the subgraph consist of the left-most vertex, the subgraph consist of 4 vertices in the middle， ,and the subgraph consist of the right-most vertex respectively.

PROBLEM 2

(1/1 分)

下面关于图的说法正确的有 (多选)

The right statements of graphs in the following are: （There are more than one correct answers）

对于无向图，所有结点的度数加起来一定是偶数。 As for undirected graphs, the sum of degrees of all vertices is definitely even number., 将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Reversion all the edges of a strongly connected component of a directed graph, then the subgraph is still a strongly connected component., - 正确

对于无向图，所有结点的度数加起来一定是偶数。 As for undirected graphs, the sum of degrees of all vertices is definitely even number.

将有向图的一个强

连通分量中的边全部反向仍然是强连通分量。Reversion all the edges of a strongly connected component of a directed graph, then the subgraph is still a strongly connected component.

对于有向图，每个结点的出度必须要等于入度。As for

对于一个连通

directed graph, each vertices’ out-degree is equal to its in-degree.

图，一定存在一种给边添加方向的方案使得这个图变成强连通图。For a connected graph, there must be a way of directing all the edges of the original graph to make the graph strongly connected graph. Explanation

结点度数是边数的2倍，故一定为偶数。

The sum of degrees of vertices is equal to the amount of edge times 2, so it must be even number.

原来强连通分量中的点必须能够互达，边全部反向后，仍然能够互达。而原来强连通分量外的点和强连通分量内的点之间的边没有变化，以前不能互达现在还是不能，这样保证了仍然是极大的强连通子图。

In the original strongly connected component, every pair of vertices in the subgraph is connected by a path.After reversion, this property doesn't change. And the

connectivity of the vertices outside of the subgraph and vertices in the subgraph don't change too. So we can guarantee it still be the maximal strongly connected subgraph. 所有结点的出度之和等于入度之和，但是每个结点并没有出度和入度相等的性质。

The sum of in-degrees of all nodes is equal to the sum of out-degrees of all nodes. But for each node, it doesn't work.

给两个结点新增一条边相连，能够形成一个连通图，但是不管怎么给边定向都不能使其成为强连通图。

Add an edge of two vertex, then we can get a connected graph. But we can't make it strongly connected graph however we direct the edges.