9. G=<V, E>中所有顶点的度数之和等于边数的（ B ）倍。 A. 1 B. 2 C. 3 D. 4

答案是 B. 2。

根据握手定理，无向图中所有顶点的度数之和等于边数的两倍，即：

∑deg(v) = 2|E|

其中，deg(v) 表示顶点 v 的度数，|E| 表示图 G 的边数。

因此，所有顶点的度数之和等于边数的两倍，即：

∑deg(v) = 2|E| = 2 × (|E| / 1) = |E| × 2

所以，所有顶点的度数之和等于边数的 2 倍。答案是 B. 2。

相关问题

用张铭编写的《数据结构与算法》证明： 对于一个无向图 G=<V, E>，若 G 中各顶点度数都大于等于 2，则 G 中必有回路。

首先，我们需要明确一个概念，回路（Cycle）是指在图中存在至少一条边，能够从某个顶点出发，经过若干个不同的顶点后，再回到这个出发点。

接下来，我们使用反证法证明原命题。

假设 G 中不存在回路，即 G 是无环图。

由于 G 中各顶点度数都大于等于 2，那么对于任意一个顶点 v∈V，它至少有两条出边，连接着不同的顶点。我们从这个顶点 v 出发，依次沿着其中一条出边走到下一个顶点，然后再沿着其中一条出边走到下一个顶点，一直走下去，直到无法继续走下去为止，这时我们会停在一个度数为 1 的顶点 u 上。

由于 G 是无环图，我们不能再从顶点 u 出发继续往下走，因为如果我们能够继续往下走，那么我们就会形成一个回路，与假设矛盾。因此，顶点 u 只有一条入边与之相连，否则它的度数就大于等于 2。

现在我们考虑从顶点 u 出发，继续按照上述方法往下走，走到下一个度数为 1 的顶点 v 上。同样地，顶点 v 也只有一条入边与之相连。

继续往下走，我们会发现如果 G 是无环图，那么我们最终一定会走到某个度数为 1 的顶点 w 上，且顶点 w 的入边与顶点 v 的出边相同。如下图所示：

    v ----> w
    ^       |
    |       |
    +-------+

现在我们将这条边从图中删除，再将顶点 w 也从图中删除，得到新的图 G'。由于顶点 w 的入边和顶点 v 的出边相同，所以删除这条边对 G 的连通性没有影响。此时，顶点 v 的度数减少了 1，但仍然大于等于 1。同样地，对于顶点 u 和它的出边也是如此。因此，我们可以重复上述过程，每次都删除某个度数为 1 的顶点及其相连的边，直到剩余的图 G'' 中只剩下一个度数不为 0 的连通分量。

最终得到的图 G'' 中，所有顶点的度数都为 0，这是因为每次删除顶点和边时，总度数减少 2，而初始时总度数为偶数（因为每条边都被算了两次），因此经过若干次删除后，剩余的总度数为偶数，而每个顶点的度数又都是偶数，所以剩余的图中顶点的度数都为偶数，与总度数为偶数矛盾。

因此，假设不成立，原命题得证。即，对于一个无向图 G=<V, E>，若 G 中各顶点度数都大于等于 2，则 G 中必有回路。

设G=<V,E>为任意无向图,,它的关联矩阵为 则 ( ) A. 2 B. 3 C. 4 D. 5

在一个无向图中，每条边连接两个顶点，因此它的关联矩阵是一个n x m的矩阵，其中n是顶点数，m是边数。对于每个顶点i和每条边j，关联矩阵A的第(i,j)个元素定义为：

- 如果顶点i是边j的一个端点，则a(i,j) = 1；
- 如果顶点i不是边j的一个端点，则a(i,j) = 0。

因此，对于这个问题中的关联矩阵A，它有5行，3列，因此它的图G有5个顶点和3条边。

我们可以通过计算A的秩来确定矩阵A的列空间的维数，从而确定图G的连通分量的数量。因为矩阵A的秩等于它的列空间的维数，也等于图G的连通分量的数量。

通过高斯消元法，可以将A化简为行阶梯形式：

1  1  0
0  1  1
-1 0  1
0 -1 -1
1  0 -1

其中，前3行是主元行，其余两行是自由行。因此，矩阵A的秩为3，也就是它的列空间的维数为3。

因此，图G有3个连通分量，答案为 B. 3。